代码来自闵老师”日撸 Java 三百行（21-30天）“，链接：https://blog.csdn.net/minfanphd/article/details/116975772

package datastructure.graph;
import matrix.IntMatrix;/*** * Directed graph. Note that undirected graphs are a special * case of directed graphs.* * @author WX873**/public class Graph {/*** The connectivity matrix.*/IntMatrix connectivityMatrix;/*** ********************************************************************** The first constructor.* @param paraNumNodes Rows and columns of the connectivity matrix.* **********************************************************************/public Graph(int paraNumNodes) {// TODO Auto-generated constructor stubconnectivityMatrix = new IntMatrix(paraNumNodes, paraNumNodes);}//of the first constructor/******************************************************************** The second constructor.* * @param paraMatrix*            The data matrix.******************************************************************/public Graph(int[][] paraMatrix) {// TODO Auto-generated constructor stubconnectivityMatrix = new IntMatrix(paraMatrix);}//The second constructor/*** *************************************************************** Overrides the method claimed in Object, the superclass of any class.* ***************************************************************/public String toString() {String resultString = "This is the connectivity matrix of the graph.\r\n" + connectivityMatrix;return resultString;}//of toString/*** ************************************************************** Get the connectivity of graph.* @return  Whether the vertices are connected?* @throws Exception   The detection of arrays operation.* ************************************************************* */public boolean getConnectivity() throws Exception {// Step 1. Initialize accumulated matrix: M_a = I.IntMatrix tempConnectiveMatrix = new IntMatrix(IntMatrix.getIdentityMatrix(connectivityMatrix.getData().length));// Step 2. Initialize M^1.IntMatrix tempMultipliedMatrix = new IntMatrix(connectivityMatrix);// Step 3. Determine the actual connectivity.for (int i = 0; i < connectivityMatrix.getData().length - 1; i++) {//Matrix accumulationtempConnectiveMatrix.add(tempMultipliedMatrix);//Calculate M^ktempMultipliedMatrix = tempMultipliedMatrix.multiply(tempMultipliedMatrix, connectivityMatrix);}//of for i// Step 4. Check the connectivity.System.out.println("The connectivity matrix is: " + tempConnectiveMatrix);int[][] tempData = tempConnectiveMatrix.getData();for (int i = 0; i < tempData.length; i++) {for (int j = 0; j < tempData[0].length; j++) {if (tempData[i][j] == 0) {System.out.println("Node " + i + " cannot reach " + j);return false;}//of if}//of for j}//of for ireturn true;}//of getConnectivity/*** ************************************************************** 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 e) {// TODO: handle exceptionSystem.out.println(e);}//of trySystem.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 e) {// TODO: handle exceptionSystem.out.println(e);}//of trySystem.out.println("Is the graph connected? " + tempConnected);}//of getConnectivityTest/*** ***************************************************************** The entrance of program.* @param args   Not used now.* *****************************************************************/public static void main(String args[]) {Graph tempGraph = new Graph(3);System.out.println(tempGraph);getConnectivityTest();}//of main}//of class Graph

今天的代码倒是好理解，开始之前还专门去搜了一下图的相关知识（无向图、有向图、连接矩阵、关联矩阵等）。
刚开始一直没搞懂的问题是，为什么检测连通性需要计算
其中 n是节点个数。且Ma中第i行第j列元素为0的话，就表示从节点i到节点j不可达？
网上搜了邻接矩阵n次方的含义：1次方表示两个顶点之间有无可行长度为1的通路；2次方表示两个顶点之间有无可行长度为2的通路；……；以此类推，n次方表示两个顶点之间有无可行长度为n的通路。（理解参考：https://blog.csdn.net/qq_40008198/article/details/103541485）
据此就可以解释上面的问题了，从1次方邻接矩阵加到n-1次方邻接矩阵。如果对应元素为0，证明两点之间可行长度从0至n-1（最大可行长度）均无通路，也就是说此时两点之间没有通路。
可是为什么要加上单位阵呢？默认节点到自身有通路？