数据结构|数据结构 [Java版本] 图的遍历 DFS & BFS 数据结构[Java版本]图的遍历D

图遍历介绍所谓图的遍历，即是对结点的访问。一个图有那么多个结点，如何遍历这些结点，需要特定策略，一般有两种访问策略: (1)深度优先遍历 (2)广度优先遍历
深度优先遍历基本思想图的深度优先搜索(Depth First Search) 。深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。
【数据结构|数据结构 [Java版本] 图的遍历 DFS & BFS】我们可以看到，这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的所有邻接结点进行横向访问。
显然，深度优先搜索是一个递归的过程
深度优先遍历算法步骤 1.访问初始结点v，并标记结点v为已访问。
2.查找结点v的第一个邻接结点w。
3.若w存在，则继续执行4，如果w不存在，则回到第1步，将从v的下一个结点继续。
4.若w未被访问，对w进行深度优先遍历递归（即把w当做另一个v，然后进行步骤123）。
5.查找结点v的w邻接结点的下一个邻接结点，转到步骤3。
看一个具体案例分析:

文章图片
案例

ABCDE A01100 B10111 C11000 D01000 E01000//说明 //(1) 1 表示能够直接连接 //(2) 0 表示不能直接连接

代码实现

package cn.icanci.datastructure.graph; import com.sun.org.apache.bcel.internal.generic.ISHL; import com.sun.org.apache.bcel.internal.generic.RETURN; import java.sql.SQLOutput; import java.util.ArrayList; import java.util.Arrays; /** * @Author: icanci * @ProjectName: AlgorithmAndDataStructure * @PackageName: cn.icanci.datastructure.graph * @Date: Created in 2020/3/17 8:57 * @ClassAction: 图 */ public class Graph { //存储顶点集合 private ArrayList vertexList; //存储对应的邻接矩阵 private int[][] edges; //表示边的数目 private int numOfEdges; //定义一个数组 boolean[] 记录某个节点是否被访问过 private boolean[] visited; public static void main(String[] args) { //测试图 //节点的个数 int n = 5; String vertexValue[] = {"A", "B", "C", "D", "E"}; //创建图对象 Graph graph = new Graph(n); //循环添加节点 for (String value : vertexValue) { graph.insertVertex(value); } //添加边 graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); //显示 graph.showGraph(); //测试深度遍历 System.out.println("测试深度遍历"); graph.dfs(); }/** * 构造器 * * @param n */ public Graph(int n) { //初始化矩阵和 vertexList edges = new int[n][n]; vertexList = new ArrayList<>(n); this.numOfEdges = 0; visited = new boolean[n]; }//得到第一个邻接结点的下边 w public int getFirstNeighbor(int index) { for (int j = 0; j < vertexList.size(); j++) { if (edges[index][j] > 0) { return j; } } return -1; }//根据前一个节点的下标来获取下一个邻接结点 public int getNextNeighbor(int v1, int v2) { for (int j = v2 + 1; j < vertexList.size(); j++) { if (edges[v1][j] > 0) { return j; } } return -1; }//深度优先遍历算法 public void dfs(boolean[] isVisited, int i) { //首先访问改节点 System.out.print(getValueByIndex(i) + " -> "); //设置已经访问 isVisited[i] = true; int w = getFirstNeighbor(i); while (w != -1) { if (!isVisited[w]) { dfs(isVisited, w); } //如果当前节点已经被访问过 w = getNextNeighbor(i, w); } }//对 dfs 进行重载 public void dfs() { //遍历所有节点进行 dfs for (int i = 0; i < getNumOfVertex(); i++) { if (!visited[i]) { dfs(visited, i); } } }//图中常用的方法 public int getNumOfVertex() { return vertexList.size(); }//返回边 public int getNumOfEdges() { return numOfEdges; }//返回节点 i (下标) 对应的数据 public String getValueByIndex(int i) { return vertexList.get(i); }//返回v1 和 v2 的权值 public int getWeight(int v1, int v2) { return edges[v1][v2]; }//显示图对应的矩阵 public void showGraph() { for (int[] link : edges) { System.out.println(Arrays.toString(link)); } }//返回v1和v2的值/** * 插入节点 * * @param vertex */ public void insertVertex(String vertex) { vertexList.add(vertex); }/** * 添加边 * * @param v1点的下标第几个节点 * @param v2第二个节点的对应的下标 * @param weight */ public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } }

测试

[0, 1, 1, 0, 0] [1, 0, 1, 1, 1] [1, 1, 0, 0, 0] [0, 1, 0, 0, 0] [0, 1, 0, 0, 0] 测试深度遍历 A -> B -> C -> D -> E ->

图的广度优先算法广度优先遍历基本思想 (BFS) 图的广度优先搜索(Broad First Search) 。
类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点
广度优先遍历算法步骤
1.访问初始结点v并标记结点v为已访问。
2.结点v入队列
3.当队列非空时，继续执行，否则算法结束。
4.出队列，取得队头结点u。
5.查找结点u的第一个邻接结点w。
6.若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤：
6.1 若结点w尚未被访问，则访问结点w并标记为已访问。
6.2 结点w入队列
6.3 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。
代码实现

package cn.icanci.datastructure.graph; import com.sun.org.apache.bcel.internal.generic.ISHL; import com.sun.org.apache.bcel.internal.generic.RETURN; import java.sql.SQLOutput; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; /** * @Author: icanci * @ProjectName: AlgorithmAndDataStructure * @PackageName: cn.icanci.datastructure.graph * @Date: Created in 2020/3/17 8:57 * @ClassAction: 图 */ public class Graph { //存储顶点集合 private ArrayList vertexList; //存储对应的邻接矩阵 private int[][] edges; //表示边的数目 private int numOfEdges; //定义一个数组 boolean[] 记录某个节点是否被访问过 private boolean[] visited; public static void main(String[] args) { //测试图 //节点的个数 int n = 5; String[] vertexValue = https://www.it610.com/article/{"A", "B", "C", "D", "E"}; //创建图对象 Graph graph = new Graph(n); //循环添加节点 for (String value : vertexValue) { graph.insertVertex(value); } //添加边 graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); //显示 graph.showGraph(); //测试深度遍历 System.out.println("测试深度优先遍历"); //graph.dfs(); System.out.println(); System.out.println("测试广度优先遍历"); graph.bfs(); }/** * 构造器 * * @param n */ public Graph(int n) { //初始化矩阵和 vertexList edges = new int[n][n]; vertexList = new ArrayList<>(n); this.numOfEdges = 0; visited = new boolean[n]; }//得到第一个邻接结点的下边 w public int getFirstNeighbor(int index) { for (int j = 0; j < vertexList.size(); j++) { if (edges[index][j] > 0) { return j; } } return -1; }//根据前一个节点的下标来获取下一个邻接结点 public int getNextNeighbor(int v1, int v2) { for (int j = v2 + 1; j < vertexList.size(); j++) { if (edges[v1][j] > 0) { return j; } } return -1; }//对一个节点进行广度优先遍历 public void bfs(boolean[] visited, int i) { //表示队列的头节点的对应下标 int u; //邻接结点 int w; //队列节点访问顺序队列 LinkedList queue = new LinkedList<>(); //访问节点输出节点的信息 System.out.print(getValueByIndex(i) + " => "); visited[i] = true; //将节点加入队列 queue.addLast(i); while (!queue.isEmpty()) { u = (Integer) queue.removeFirst(); w = getFirstNeighbor(u); while (w != -1) { if (!visited[w]) { System.out.print(getValueByIndex(w) + " => "); //标记已经访问 visited[w] = true; //入队 queue.addLast(w); } //以 u 为前驱节点,找w后面的下一个临界点 w = getNextNeighbor(u, w); } } }//遍历所有 public void bfs() { for (int i = 0; i < getNumOfVertex(); i++) { if (!visited[i]) { bfs(visited, i); } } }//深度优先遍历算法 public void dfs(boolean[] isVisited, int i) { //首先访问改节点 System.out.print(getValueByIndex(i) + " -> "); //设置已经访问 isVisited[i] = true; int w = getFirstNeighbor(i); while (w != -1) { if (!isVisited[w]) { dfs(isVisited, w); } //如果当前节点已经被访问过 w = getNextNeighbor(i, w); } }//对 dfs 进行重载 public void dfs() { //遍历所有节点进行 dfs for (int i = 0; i < getNumOfVertex(); i++) { if (!visited[i]) { dfs(visited, i); } } }//图中常用的方法 public int getNumOfVertex() { return vertexList.size(); }//返回边 public int getNumOfEdges() { return numOfEdges; }//返回节点 i (下标) 对应的数据 public String getValueByIndex(int i) { return vertexList.get(i); }//返回v1 和 v2 的权值 public int getWeight(int v1, int v2) { return edges[v1][v2]; }//显示图对应的矩阵 public void showGraph() { for (int[] link : edges) { System.out.println(Arrays.toString(link)); } }//返回v1和v2的值/** * 插入节点 * * @param vertex */ public void insertVertex(String vertex) { vertexList.add(vertex); }/** * 添加边 * * @param v1点的下标第几个节点 * @param v2第二个节点的对应的下标 * @param weight */ public void insertEdge(int v1, int v2, int weight) { edges[v1][v2] = weight; edges[v2][v1] = weight; numOfEdges++; } }

打印

[0, 1, 1, 0, 0] [1, 0, 1, 1, 1] [1, 1, 0, 0, 0] [0, 1, 0, 0, 0] [0, 1, 0, 0, 0] 测试深度优先遍历测试广度优先遍历 A => B => C => D => E =>

图的深度优先VS 广度优先应用实例

文章图片
Demo

graph.insertEdge(0, 1, 1); graph.insertEdge(0, 2, 1); graph.insertEdge(1, 3, 1); graph.insertEdge(1, 4, 1); graph.insertEdge(3, 7, 1); graph.insertEdge(4, 7, 1); graph.insertEdge(2, 5, 1); graph.insertEdge(2, 6, 1); graph.insertEdge(5, 6, 1);