- 一.使用矩阵表示连通性
- 二.代码展示
- 三.总结
- 使用矩阵表示连通性
- 二.代码展示
- 三.总结
首先我们说一下图的定义
图是由顶点的有穷非空集合和顶点之间边的集合组成， 通常表示为: G（V，E）， 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
因此我们可以看出图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关，那么就无法以数据元素在内存中的物理位置来表示元素之间的关系，也就是说，图不可能用简单的顺序存储结构来表示。而多重链表的方式，要么会造成很多存储单元的浪费，要么又带来操作的不便。因此，对于图来说，如何对它实现物理存储是个难题，在这里我们将会用到邻接矩阵。
图的邻接矩阵(Adjacency Matrix) 存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。
设图G有n个顶点，则邻接矩阵A 是一个n*n的方阵，定义为:
下图是一个无向图和它的邻接矩阵：
下面是一个有向图和它的邻接矩阵：
那我们就利用邻接矩阵来判断图的连通性问题。
先给出公式:
Mx=
M
0
M^0
M0+
M
1
M^1
M1+
M
2
M^2
M2+…+
M
(
n
−
1
)
M^(n-1)
M(n−1)
其中 M代表图的邻接矩阵,n代表顶点数
如果矩阵Mx中某元素aij==0，则表示该图为非连通图。
连通图和非连通图
在无向图中，若从顶点v到顶点w有路径存在，则称v和vv是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。
在有向图中，若从顶点v到顶点w和从顶点w到顶点之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。
理解公式
矩阵
M
0
M^0
M0
表示与M同型的单位阵，表示结点可以自己到达其自身；
// Step 1. Initialize accumulated matrix: M_a = I.
IntMatrix tempConnectivityMatrix = IntMatrix
.getIdentityMatrix(connectivityMatrix.getData().length);
矩阵 M 1 M^1 M1就是我们常说的邻接矩阵，也是代码中最初赋值的connectivityMatrix. mij表示从顶点i到顶点j是否存在一条边。（即直接相连）
// Step 2. Initialize M^1.
IntMatrix tempMultipliedMatrix = new IntMatrix(connectivityMatrix);
矩阵
M
2
M^2
M2
mik表示从顶点i到顶点k是否存在一条边，mkj表示从顶点k到顶点j是否存在一条边，两个值相乘，若值=1,则表示从顶点i到顶点j存在连通,若值=0，则表示从从顶点i到顶点j不存在连通。
再联系求和符号：
表示顶点 i 经过任意一个顶点到达顶点 j 的路径方式的和。假设顶点i可经过顶点a到达顶点j，也可以经过顶点b到达顶点b，则mij求和结果为2.
以此类推：
M
i
j
k
Mij^k
Mijk表示顶点 i 能否经过k条边到达顶点 j
关键代码
public boolean getConnectivity() throws Exception {
// Step 1. Initialize accumulated matrix: M_a = I.
IntMatrix tempConnectivityMatrix = 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++) {
// M_a = M_a + M^k
tempConnectivityMatrix.add(tempMultipliedMatrix);
// M^k
tempMultipliedMatrix = IntMatrix.multiply(tempMultipliedMatrix, connectivityMatrix);
} // Of for i
// 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;
} // Of if
} // Of for j
} // Of for i
return true;
}// Of getConnectivity
add方法中我们用了resultMatrix来copy第一个矩阵，因此resultMatrix在每次循环中不断被更新，最后返回即可。因此 tempConnectivityMatrix矩阵即为我们需要的矩阵Mx。
public void add(IntMatrix paramMatrix) throws Exception
{
//step1 get the data of the given matrix.
int[][] tempData=paramMatrix.getData();
//step2 check size.
if(data.length!=tempData.length)
{
throw new Exception("the row is not match");
}//of if
if(data[0].length!=tempData[0].length)
{
throw new Exception("the col is not match");
}//of if
//step3. add to mine.
for(int i=0;i
整体代码
package graph;
import matrix.IntMatrix;
public class Graph {
IntMatrix connectivityMatrix;
public Graph(int paraNumNodes) {
connectivityMatrix = new IntMatrix(paraNumNodes, paraNumNodes);
}// Of the first constructor
public Graph(int[][] paraMatrix) {
connectivityMatrix = new IntMatrix(paraMatrix);
}// Of the second constructor
public String toString() {
String resultString = "This is the connectivity matrix of the graph.rn"
+ connectivityMatrix;
return resultString;
}// Of toString
public boolean getConnectivity() throws Exception {
// Step 1. Initialize accumulated matrix: M_a = I.
IntMatrix tempConnectivityMatrix = 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++) {
// M_a = M_a + M^k
tempConnectivityMatrix.add(tempMultipliedMatrix);
// M^k
tempMultipliedMatrix = IntMatrix.multiply(tempMultipliedMatrix, connectivityMatrix);
} // Of for i
// 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;
} // Of if
} // Of for j
} // Of for i
return true;
}// Of getConnectivity
public static void getConnectivityTest() {
// Test an undirected graph.
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);
} // Of try.
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);
} // Of try.
System.out.println("Is the graph connected? " + tempConnected);
}// Of getConnectivityTest
public static void main(String args[]) {
System.out.println("Hello!");
Graph tempGraph = new Graph(3);
System.out.println(tempGraph);
// Unit test.
getConnectivityTest();
}// Of main
}// Of class Graph
运行结果
Hello!
This is the connectivity matrix of the graph.
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
This is the connectivity matrix of the graph.
[[0, 1, 0], [1, 0, 1], [0, 1, 0]]
The connectivity matrix is: [[2, 1, 1], [1, 3, 1], [1, 1, 2]]
Is the graph connected? true
The connectivity matrix is: [[4, 2, 1], [2, 3, 1], [1, 1, 2]]
Is the graph connected? true
三.总结
利用Mx=
M
0
M^0
M0+
M
1
M^1
M1+
M
2
M^2
M2+…+
M
(
n
−
1
)
M^(n-1)
M(n−1)能将矩阵的运算与图很好的联系起来，感觉发现了矩阵作用的新大陆。关于该公式的理解也需要加深，其中的巧妙之处在于把求和符号看成是从某顶点i到顶点j能有多少条不同的边。这里的知识其实应该用到了离散数学里的图论知识，但目前还没有学到该内容,所以得查阅相关资料来了解相关知识。
