目录

图的存储深度优先遍历广度优先遍历疑问

图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图：

图的存储

在考虑代码实现中，我们可以通过一个列表来存储所有的结点，数组来存储所有边。

package com.hong.graph; import java.util.ArrayList; import java.util.Arrays; public class Graph { private ArrayList<String> vertexList; //存储顶点集合 private int[][] edges; //存储图对应的邻结矩阵 private int numOfEdges; //表示边的数目 //定义给数组boolean[], 记录某个结点是否被访问 private boolean[] isVisited; //构造器 public Graph(int n) { //初始化矩阵和vertexList edges = new int[n][n]; vertexList = new ArrayList<String>(n); numOfEdges = 0; } //图中常用的方法 //显示图对应的矩阵 public void showGraph() { for(int[] link : edges) { System.out.println(Arrays.toString(link)); } } //插入结点 public void insertVertex(String vertex) { vertexList.add(vertex); } //添加边 /** * * @param v1 表示点的下标即使第几个顶点 "A"-"B" "A"->0 "B"->1 * @param v2 第二个顶点对应的下标 * @param weight 表示 */ public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } }

深度优先遍历

我们以上面的图来举例说明图的深度优先遍历是怎么样的一个过程。

以A为起始节点，找到它的第一个邻接节点B；接着以B为起始节点（这里其实是对B的一个递归过程），找到它的第一个邻接节点C；然后，以B为起始节点（对C的一个递归过程），发现它的邻接节点A和B都已经被访问过了，退出C的递归；这时候，需要对B进行回溯，找到B的第二个邻接节点D；再接着，以D为起始节点（对D的一个递归过程），发现它的邻接节点B已经被访问过了，退出D的递归；继续对B进行回溯，找到B的第三个邻接节点E；再接着，以E为起始节点（对E的一个递归过程），发现它的邻接节点B已经被访问过了，退出E的递归；继续对B进行回溯，发现没有其他的邻接节点了，退出B的递归；此时，就需要对A进行回溯了，找到它的第二个邻接点D，发现它的邻接节点B已经被访问过了，退出D的递归；最后，又对A进行回溯， 没有其他的邻接节点了，完成对A的整个深度优先遍历；下面，就是对其他剩下的所有节点，都执行以上10步的操作（但其实很多节点都已经被访问过了，所以很多节点都是跳过的）。 /** * 深度优先遍历主方法 */ public void deepTraversing(){ isVisited = new boolean[vertexList.size()]; for (int i=0; i<vertexList.size(); i++){ if (!isVisited[i]){ deepTraversing(i); } } } /** * 以vertex为起点，进行深度遍历递归 * @param vertex */ private void deepTraversing(int vertex){ System.out.print(vertexList.get(vertex) + "->"); isVisited[vertex] = true; // 获取vertex的第一个邻接节点 int next = getNextEdges(vertex, 0); while (next != -1){ if (!isVisited[next]){ deepTraversing(next); } else{ // 如果该邻接节点已经被访问过，则获取下一个邻接节点 next = getNextEdges(vertex, next+1); } } } /** * 获取vertex从初始位置为start的下一个邻接节点 * @param vertex * @param start * @return */ private int getNextEdges(int vertex, int start){ for (int j=start; j<vertexList.size(); j++){ if (edges[vertex][j] == 1){ return j; } } return -1; }

广度优先遍历

广度优先遍历比深度优先遍历简单很多，比较容易理解。仍然以上面的图为例子：

从第一个节点A开始，依次找到它的所有邻接节点；然后，轮到第二个节点B，依次找到它的所有邻接节点（未被访问的）；剩下的节点类似… /** * 广度优先遍历方法 */ private void breadthTraversing(){ isVisited = new boolean[vertexList.size()]; int w; for (int v=0; v<vertexList.size(); v++){ // 打印顶点v的所有邻接节点(未被访问过的) if (!isVisited[v]){ System.out.print(vertexList.get(v) + "->"); isVisited[v] = true; } w = getNextEdges(v, 0); // 获取v的第一个邻接节点 while (w != -1){ if (!isVisited[w]){ System.out.print(vertexList.get(w) + "->"); isVisited[w] = true; } w = getNextEdges(v, w+1); } } }

完整代码已上传至GitHub

疑问

为什么很多人对图的广度优先遍历，都是通过队列来实现的。就感觉是对前面的节点进行循环操作时，先帮后面的一些节点完成遍历； 但，其实不用队列的话，就是每个节点完成自己的遍历。 有大神看到的帮忙解答一下！！！

欢迎关注同名公众号：“我就算饿死也不做程序员”。 交个朋友，一起交流，一起学习，一起进步。