说明

闵老师的文章链接： 日撸 Java 三百行（总述）_minfanphd的博客-CSDN博客
自己也把手敲的代码放在了github上维护：https://github.com/fulisha-ok/sampledata

day33 图的广度优先遍历

1.思路

结合下图，广度优先遍历假设从a节点出发，a访问后，访问领接点b/c,b访问了再访问c,又接着访问b的领接点，c的领接点，这样一层一层的访问，这就好比树的层次遍历一样。在访问图时要借助一个队列来实现.如图广度优先遍历的一种顺序是：a->b->c->d->e

根据上图，所结点所存储的矩阵值：
Δ a b c d e a 0 1 1 0 0 b 1 0 0 1 0 c 0 0 0 1 1 d 0 0 0 0 1 e 0 0 0 0 0 \\begin{array}{c} % 总表格 \\begin{array}{c|cccc} % 第二行 Delta 值数组 \\Delta & a & b & c & d & e \\\\ \\hline a & 0 & 1 & 1 & 0 & 0 \\\\ b & 1 & 0 & 0 & 1 & 0 \\\\ c & 0 & 0 & 0 & 1 & 1 \\\\ d & 0 & 0 & 0 & 0 & 1 \\\\ e & 0 & 0 & 0 & 0 & 0 \\\\ \\end{array} % 第二行表格结束 \\end{array} % 总表格结束 Δabcde​a01000​b10000​c10000​d01100​e00110​​​
通过上图的实现 可以知道，当我们出队一个结点，如a，就需要把a结点相应邻结点入队（这里我们采用的数据结构是矩阵，可以通过矩阵的行列值是否为1来判断是否与出结点是否相邻）则发现a行b列和a行c列是连接的，则说明b,c是a的领结点，则将b，c入队列。其他一样。

//代码中判断相邻结点
if (connectivityMatrix.getData()[tempIndex][i] == 0) {//Not directly connected.continue;
}

2.多个连通分量

在今天的文章中，这个遍历只能遍历只有一个连通分量的图(有向图)，若有多个连通分量，则会漏一些节点数据（需要加一个循环来验证节点是否访问完）。在代码中有一个布尔类型数组：boolean[] tempVisitedArray = new boolean[tempNumNodes];若我们在一次广度遍历完遍历这个tempVisitedArray数组，再循环遍历是否有false，若有则说明图有多个连通分量，这是我们还需要把未遍历的节点再遍历完。

    /* Judge connectivity* @param tempVisitedArray* @return*/public boolean isConnectivity(int paraStartIndex){int tempNumNodes = connectivityMatrix.getRows();breadthFirstTraversal(paraStartIndex);for (int i = 0; i < tempNumNodes; i++){if (!tempVisitedArray[i]){breadthFirstTraversal(i);return false;}}return true;}

2 代码实现

我在原来的基础上做了一些小的改动，来遍历所有的结点。加了一个方法isConnectivity， 来遍历所有的结点，将tempVisitedArray， resultString作为成员变量。

package graph;import datastructure.queue.CircleObjectQueue;
import matrix.IntMatrix;/* @author： fulisha* @date： 2023/4/18 15:43* @description：*/
public class Graph {IntMatrix connectivityMatrix;/* The first constructor.* @param paraNumNodes The number of nodes in the graph.*/public Graph(int paraNumNodes){connectivityMatrix = new IntMatrix(paraNumNodes, paraNumNodes);}/* The second constructor.* @param paraMatrix The data matrix.*/public Graph(int[][] paraMatrix){connectivityMatrix = new IntMatrix(paraMatrix);}@Overridepublic String toString(){return "This is the connectivity matrix of the graph.\\r\\n" + connectivityMatrix;}/* Get the connectivity of the graph.* @return*/public boolean getConnectivity() throws Exception {// Step 1. Initialize accumulated matrix.IntMatrix tempConnectivityMatrix = IntMatrix.getIdentityMatrix(connectivityMatrix.getData().length);//Step 2. InitializeIntMatrix tempMultipliedMatrix = new IntMatrix(connectivityMatrix);//Step 3. Determine the actual connectivity.for (int i = 0; i < connectivityMatrix.getData().length - 1; i++){// M_a = M_a + M^ktempConnectivityMatrix.add(tempMultipliedMatrix);// M^ktempMultipliedMatrix = IntMatrix.multiply(tempMultipliedMatrix, connectivityMatrix);}// Step 4. Check the connectivity.System.out.println("The connectivity matrix is: " + tempConnectivityMatrix);int[][] tempData = tempConnectivityMatrix.getData();for (int i = 0; i < tempData.length; i++) {for (int j = 0; j < tempData.length; j++){if (tempData[i][j] == 0){System.out.println("Node " + i + " cannot reach " + j);return false;}}}return true;}/* Unit test for getConnectivity.*/public static void getConnectivityTest(){int[][] tempMatrix = { { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 } };Graph tempGraph2 = new Graph(tempMatrix);System.out.println(tempGraph2);boolean tempConnected = false;try {tempConnected = tempGraph2.getConnectivity();} catch (Exception ee) {System.out.println(ee.getMessage());}System.out.println("Is the graph connected? " + tempConnected);//Test a directed graph. Remove one arc to form a directed graph.tempGraph2.connectivityMatrix.setValue(1, 0, 0);tempConnected = false;try {tempConnected = tempGraph2.getConnectivity();} catch (Exception ee) {System.out.println(ee);}System.out.println("Is the graph connected? " + tempConnected);}/* Breadth first Traversal* @param paraStartIndex The start index.* @return The sequence of the visit.*/boolean[] tempVisitedArray;String resultString = "";public String breadthFirstTraversal(int paraStartIndex) {CircleObjectQueue tempQueue = new CircleObjectQueue();int tempNumNodes = connectivityMatrix.getRows();tempVisitedArray = new boolean[tempNumNodes];// Initialize the queuetempVisitedArray[paraStartIndex] = true;resultString += paraStartIndex;tempQueue.enqueue(paraStartIndex);//Now visit the rest of the graph.int tempIndex;Integer tempInteger = (Integer) tempQueue.dequeue();while (tempInteger != null){tempIndex = tempInteger.intValue();//Enqueue all its unvisited neighbors.for (int i = 0; i < tempNumNodes; i++){if (tempVisitedArray[i]){// Already visited.continue;}if (connectivityMatrix.getData()[tempIndex][i] == 0) {//Not directly connected.continue;}tempVisitedArray[i] = true;resultString += i;tempQueue.enqueue(i);}//Take out one from the head.tempInteger = (Integer)tempQueue.dequeue();}return resultString;}/* Judge connectivity* @param* @return*/public boolean isConnectivity(int paraStartIndex){int tempNumNodes = connectivityMatrix.getRows();breadthFirstTraversal(paraStartIndex);for (int i = 0; i < tempNumNodes; i++){if (!tempVisitedArray[i]){breadthFirstTraversal(i);return false;}}return true;}public static void breadthFirstTraversalTest() {// Test an undirected graph.//int[][] tempMatrix = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 1}, { 0, 1, 1, 0} };//int[][] tempMatrix = { { 0, 1, 1, 0 , 0}, { 1, 0, 0, 1, 0 }, { 1, 0, 0, 1, 0}, { 0, 1, 1, 0, 0}, { 0, 0, 0, 0, 0} };int[][] tempMatrix = { { 0, 1, 1, 0 , 0, 0, 0}, { 1, 0, 0, 1, 0, 0, 0 }, { 1, 0, 0, 1, 0, 0, 0}, { 0, 1, 1, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 1, 1}, { 0, 0, 0, 0, 1, 0, 0}, { 0, 0, 0, 0, 0, 0, 0} };Graph tempGraph = new Graph(tempMatrix);System.out.println(tempGraph);String tempSequence = "";try {tempGraph.isConnectivity(2);//tempSequence = tempGraph.breadthFirstTraversal(2);} catch (Exception ee) {System.out.println(ee.getMessage());return;}System.out.println("The breadth first order of visit: " + tempGraph.resultString);}public static void main(String[] args) {System.out.println("Hello!");Graph tempGraph = new Graph(3);System.out.println(tempGraph);// Unit test.getConnectivityTest();breadthFirstTraversalTest();}}

• 单元测试1
  

• 单元测试2
  
  
• 单元测试3