1.引言
图的连通性问题是图论研究的重要问题之一，在实际中有着广泛的应用。例如在通信网络的联通问题中，运输路线的规划问题等等都涉及图的连通性。因此传递闭包的计算需要一个高效率的算法，一个著名的算法就是warshall在1962年提出的WarShall算法。
2.算法描述
使用n阶布尔矩阵\(R^{(k)}(0\leq k\leq n)\)来表示有向图中任意一对节点 是否含有路径的信息。因此，可将原问题划分为如下决策阶段：
\[R^{(0)},R^{(1)},\cdots，R^{(k)},\cdots ,R^{(n)}
\]
\]
具体来说，当且仅当从节点i到节点j存在一条有向路径，且该路径上的每一个中间节点的编号都不大于k时，矩阵\(R^{(k)}\)的第i行，第j列的元素\(r_{ij}^{(k)}=1\)。
对于\(R^{(k)}\)的计算我们可以由它的前趋\(R^{(k-1)}\) 计算得到（分级推进计算）。
- \(R^{(0)}\) ——该矩阵不允许它的路径中包含任何中间顶点，即从该矩阵的任意顶点出发的路径不含有中间顶点，此即邻接矩阵。
- \(R^{(1)}\) ——允许路径中包含第1个顶点（本例编号1）作为中间顶点。
- \(R^{(2)}\) ——允许路径中包含前2个顶点（本例编号1、2）作为中间顶点。
- \(R^{(k)}\) ——允许路径中包含前k个顶点作为中间顶点。
-
\(R^{(n)}\) ——允许路径中包含全部 n 个顶点作为中间顶点。
所以综上所述我们得到\(R^{(k)}\)的计算方式如下：
\[R^{k}[i,j]\leftarrow R^{k-1}[i,j]+R^{k-1}[i,k]\cdot R^{k-1}[k,j]
\]
\]
3.算法实现
for(int k=0;k<N;k++){
for(int i=0;i<N;i++){
for(int j=0;j<N;j++){
t[i][j]=t[i][j]||(t[i][k]&&t[k][j]);//由文中公式可得
}
}
}
算法优化
```
for(int k=0;k
参考资料：
离散数学（第三版），清华大学出版社