欢迎移步博主CSDN：[CSDN博客](https://blog.csdn.net/weixin_42327790/article/details/103120803) # 无向图的两种遍历算法的实现 ## 简介 图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为 $$ G = (V,E) $$ 如果图的任意两个顶点之间的边都是无向边，则称该图为**无向图**,否则称该图为**有向图**。 ## 图的两种遍历算法思想 * 深度优先遍历算法思想 （1）访问顶点v； （2）从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历； （3）重复上述两步，直至图中所有和v有路径相通的顶点都被访问到 * 广度优先遍历算法思想 （1）访问顶点v； （2）依次访问v的各个未被访问的邻接点v1，v2，v3...... （3）分别从v1，v2，v3......出发依次访问它们未被访问的邻接点，并使先被访问顶点的邻接点先于后被访问顶点的邻接点被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。 ## 采用邻接矩阵存储 图的邻接矩阵存储也称为数组表示法，其方法是用一个以为数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间临界关系的二维数组称为邻接矩阵。 --- 以下面这个无向图为例进行实现  * 该无向图的`DFS`访问顺序：V0->V1->V4->V5->V2->V3 * 该无向图的`BFS`访问顺序：V0->V1->V2->V3->V4->V5 为了省时间（~~其实是自己懒~~ ），此处省略邻接矩阵的构造过程，采用手动写入边集和点集构建该无向图。 ```java //手动构造图的点集和边集 //点集 int[] vector = { 0,1,2,3,4,5 }; //边集 int[][] arc ={ {0,1,1,1,1,0}, {1,0,0,0,1,0}, {1,0,0,0,1,0}, {1,0,0,0,0,0}, {1,1,1,0,0,1}, {0,0,0,0,1,1} }; //记录是否访问 int[] visited = { 0,0,0,0,0,0 }; ``` ### 深度优先遍历（递归实现） ```java //图的深搜DFS,递归 public static void DFS(int[] vector, int[] visited, int[][] arc,int i){ //访问结点并标记 System.out.println(vector[i]); visited[i]=1; for (int j = 0;j<vector.length; ++j){ if (visited[j]==0 && arc[i][j]==1) DFS(vector,visited,arc,j); } } ``` ### 深度优先遍历 （非递归实现） ```java //图的深搜DFS ,非递归 public static void DFS(int[] vector, int[] visited, int[][] arc){ //访问第一个顶点并入栈 System.out.println(vector[0]); Stack<Integer> stack = new Stack<Integer>(); stack.push(0); visited[0] = 1; while(!stack.isEmpty()){ //获取栈顶元素 int x = stack.peek(); //标志位 boolean flag = false; for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ System.out.println(vector[i]); //入栈 stack.push(i); //更改访问位,标志位 visited[i] = 1; flag = true; break; } } //出栈 if (!flag) stack.pop(); } } ``` ### 广度优先遍历 ```java //图的广搜BFS,非递归 public static void BFS(int[] vector, int[] visited, int[][] arc){ Queue<Integer> queue = new LinkedList<Integer>(); //第一个顶点入队 queue.offer(0); while (!queue.isEmpty()){ //出队 int x = queue.poll(); //访问结点并标记 System.out.println(vector[x]); visited[x] = 1; //寻找连通的结点并入队 for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ queue.offer(i); visited[i] = 1; } } } } ``` ## 采用邻接表存储 图的邻接表存储是一种顺序存储与链接存储相结合的存储方法，类似于数的孩子链表表示法。对于图的每个顶点v，将所有邻接于v的顶点链成一个单链表，称为顶点v的边表（对于有向图则称为出边表）。 顶点类： ```java /** * @Author zbl * @Date: 2019/11/18/ 17:59 * @Description */ //顶点结点 public class VertexNode{ public int vertex; public ArcNode firstEdge; } ``` 边表类： ```java /** * @Author zbl * @Date: 2019/11/18/ 17:12 * @Description */ //边结点 public class ArcNode { //邻接点域 public int adjvex; public ArcNode next; public ArcNode(){} public ArcNode(int adjvex,ArcNode arcNode) {this.adjvex=adjvex;this.next=arcNode;} } ``` --- 以下面这个无向图为例进行实现  * 该无向图的`DFS`访问顺序：V0->V1->V4->V2->V3 * 该无向图的`BFS`访问顺序：V0->V1->V2->V3->V4 为了省时间（~~其实是自己懒~~ ），此处省略邻接表的构造过程，采用手动写入边集和点集构建该无向图。 ```java //手动构造图的点集和边集 //手动构造点集和边集 VertexNode[] vertex = new VertexNode[5]; for (int i = 0;i<vertex.length;++i){ vertex[i] = new VertexNode(); vertex[i].vertex=i; } ArcNode V03 = new ArcNode(3,null); ArcNode V02 = new ArcNode(2,V03); ArcNode V01 = new ArcNode(1,V02); ArcNode V12 = new ArcNode(4,null); ArcNode V11 = new ArcNode(0,V12); ArcNode V22 = new ArcNode(3,null); ArcNode V21 = new ArcNode(0,V22); ArcNode V32 = new ArcNode(2,null); ArcNode V31 = new ArcNode(0,V32); ArcNode V41 = new ArcNode(1,null); vertex[0].firstEdge=V01; vertex[1].firstEdge=V11; vertex[2].firstEdge=V21; vertex[3].firstEdge=V31; vertex[4].firstEdge=V41; for(int i = 0; i<visited.length; ++i) visited[i] = 0; ``` ### 深度优先遍历（递归实现） ```java /** * @Description: 图的深搜DFS，邻接矩阵存储，递归 * @Param: [vertex, visited, i] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void DFS(VertexNode[] vertex,int[] visited,int i){ System.out.println(vertex[i].vertex); visited[i]=1; ArcNode tmp = vertex[i].firstEdge; while(tmp != null){ int j = tmp.adjvex; if(visited[j]==0) DFS(vertex,visited,j); tmp = tmp.next; } } ``` ### 深度优先遍历 （非递归实现） ```java /** * @Description: 图的深搜DFS，邻接矩阵存储，非递归 * @Param: [vertex, visited] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void DFS(VertexNode[] vertex,int[] visited){ Stack<Integer> stack = new Stack<Integer>(); //访问第一个顶点并入栈 System.out.println(vertex[0].vertex); stack.push(0); visited[0]=1; //栈不为空 while(!stack.isEmpty()){ boolean flag = false; //获取栈顶但不弹栈 int i = stack.peek(); ArcNode tmp = vertex[i].firstEdge; //遍历边表 while(tmp!=null){ if (visited[tmp.adjvex]==0){ //访问并入栈 System.out.println(vertex[tmp.adjvex].vertex); stack.push(tmp.adjvex); //更改访问位,标志位 visited[tmp.adjvex]=1; flag = true; break; } tmp = tmp.next; } //弹栈 if(!flag) stack.pop(); } } ``` ### 广度优先遍历 ```java /** * @Description: 图的广搜BFS，邻接矩阵存储，非递归 * @Param: [vertex, visited] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void BFS(VertexNode[] vertex,int[] visited){ for (int i = 0; i<vertex.length; ++i){ ArcNode tmp = vertex[i].firstEdge; //若未访问,则访问并标记 if (visited[i]==0){ System.out.println(vertex[i].vertex); visited[i]=1; } while(tmp!=null){ //若未访问,则访问并标记 if (visited[tmp.adjvex]==0){ System.out.println(vertex[tmp.adjvex].vertex); visited[tmp.adjvex]=1; } tmp = tmp.next; } } } ``` ## 完整函数代码 顶点类和边表类在上面已经给出，在此就不重复放出来了。 ```java import javafx.scene.shape.Arc; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * author zbl * * datetime 2019.11.18 * */ public class Main { //图的深搜DFS ,非递归 public static void DFS(int[] vector, int[] visited, int[][] arc){ //访问第一个顶点并入栈 System.out.println(vector[0]); Stack<Integer> stack = new Stack<Integer>(); stack.push(0); visited[0] = 1; while(!stack.isEmpty()){ //获取栈顶元素 int x = stack.peek(); //标志位 boolean flag = false; for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ System.out.println(vector[i]); //入栈 stack.push(i); //更改访问位,标志位 visited[i] = 1; flag = true; break; } } //出栈 if (!flag) stack.pop(); } } //图的深搜DFS,递归 public static void DFS(int[] vector, int[] visited, int[][] arc,int i){ //访问结点并标记 System.out.println(vector[i]); visited[i]=1; for (int j = 0;j<vector.length; ++j){ if (visited[j]==0 && arc[i][j]==1) DFS(vector,visited,arc,j); } } //图的广搜BFS,非递归 public static void BFS(int[] vector, int[] visited, int[][] arc){ Queue<Integer> queue = new LinkedList<Integer>(); //第一个顶点入队 queue.offer(0); while (!queue.isEmpty()){ //出队 int x = queue.poll(); //访问结点并标记 System.out.println(vector[x]); visited[x] = 1; //寻找连通的结点并入队 for (int i = 0; i<vector.length;++i){ if (visited[i]==0 && arc[x][i]==1){ queue.offer(i); visited[i] = 1; } } } } /** * @Description: 图的深搜DFS，邻接矩阵存储，非递归 * @Param: [vertex, visited] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void DFS(VertexNode[] vertex,int[] visited){ Stack<Integer> stack = new Stack<Integer>(); //访问第一个顶点并入栈 System.out.println(vertex[0].vertex); stack.push(0); visited[0]=1; //栈不为空 while(!stack.isEmpty()){ boolean flag = false; //获取栈顶但不弹栈 int i = stack.peek(); ArcNode tmp = vertex[i].firstEdge; //遍历边表 while(tmp!=null){ if (visited[tmp.adjvex]==0){ //访问并入栈 System.out.println(vertex[tmp.adjvex].vertex); stack.push(tmp.adjvex); //更改访问位,标志位 visited[tmp.adjvex]=1; flag = true; break; } tmp = tmp.next; } //弹栈 if(!flag) stack.pop(); } } /** * @Description: 图的深搜DFS，邻接矩阵存储，递归 * @Param: [vertex, visited, i] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void DFS(VertexNode[] vertex,int[] visited,int i){ System.out.println(vertex[i].vertex); visited[i]=1; ArcNode tmp = vertex[i].firstEdge; while(tmp != null){ int j = tmp.adjvex; if(visited[j]==0) DFS(vertex,visited,j); tmp = tmp.next; } } /** * @Description: 图的广搜BFS，邻接矩阵存储，非递归 * @Param: [vertex, visited] * @return: void * @Author: zbl * @Date: 2019/11/18 */ public static void BFS(VertexNode[] vertex,int[] visited){ for (int i = 0; i<vertex.length; ++i){ ArcNode tmp = vertex[i].firstEdge; //若未访问,则访问并标记 if (visited[i]==0){ System.out.println(vertex[i].vertex); visited[i]=1; } while(tmp!=null){ //若未访问,则访问并标记 if (visited[tmp.adjvex]==0){ System.out.println(vertex[tmp.adjvex].vertex); visited[tmp.adjvex]=1; } tmp = tmp.next; } } } public static void main(String[] args) { //手动构造点集和边集 //点集 int[] vector = { 0,1,2,3,4,5 }; //边集 int[][] arc ={ {0,1,1,1,1,0}, {1,0,0,0,1,0}, {1,0,0,0,1,0}, {1,0,0,0,0,0}, {1,1,1,0,0,1}, {0,0,0,0,1,1} }; //记录是否访问 int[] visited = { 0,0,0,0,0,0 }; System.out.println("===============邻接矩阵Start==============="); System.out.println("Start DFS:"); DFS(vector,visited,arc); System.out.println("End DFS\n"); for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start DFS:"); DFS(vector,visited,arc,0); System.out.println("End DFS\n"); for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start BFS:"); BFS(vector,visited,arc); System.out.println("End BFS"); System.out.println("===============邻接矩阵End===============\n"); System.out.println("===============邻接表Start==============="); //手动构造点集和边集 VertexNode[] vertex = new VertexNode[5]; for (int i = 0;i<vertex.length;++i){ vertex[i] = new VertexNode(); vertex[i].vertex=i; } ArcNode V03 = new ArcNode(3,null); ArcNode V02 = new ArcNode(2,V03); ArcNode V01 = new ArcNode(1,V02); ArcNode V12 = new ArcNode(4,null); ArcNode V11 = new ArcNode(0,V12); ArcNode V22 = new ArcNode(3,null); ArcNode V21 = new ArcNode(0,V22); ArcNode V32 = new ArcNode(2,null); ArcNode V31 = new ArcNode(0,V32); ArcNode V41 = new ArcNode(1,null); vertex[0].firstEdge=V01; vertex[1].firstEdge=V11; vertex[2].firstEdge=V21; vertex[3].firstEdge=V31; vertex[4].firstEdge=V41; for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start DFS:"); DFS(vertex,visited); System.out.println("End DFS\n"); for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start DFS:"); DFS(vertex,visited,0); System.out.println("End DFS\n"); for(int i = 0; i<visited.length; ++i) visited[i] = 0; System.out.println("Start BFS:"); BFS(vertex,visited); System.out.println("End BFS"); System.out.println("===============邻接表End==============="); } } ``` ## 注意事项 以上代码只适用于强连通图！！！ 以上代码只适用于强连通图！！！ 以上代码只适用于强连通图！！！ ~~重要的事说三遍。~~ ## 参考文献 * 王红梅，胡明，王涛编著. 数据结构（C++版）（第二版）[M]. 清华大学出版社. 最后修改：2020 年 03 月 14 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用，请随意赞赏
1 条评论
文章结构紧凑，层次分明，逻辑严密，让人一读即懂。