图传递闭包是指修正后邻接矩阵表示图

在多个顶点有向图中每个顶点可以到按照方向到达定节点这叫图连通性有种思路方法直接告诉我们图中两个节点是否可以联通这里说是WarShall算法

WarShall基本原理是如果A可以到达B且C可以到达A则C可以到达B通过对邻接矩阵修正可以做到这点随然这里举例是将两步可并成步但数学上可以证明这种修正可以达到任意步骤

下面是代码:

Java代码
WarShall {
private boolean adjMat;

WarShall( size) {
adjMat = boolean[size][size];
}

void connect( from, to) {
adjMat[from][to] = true;
}

boolean isConnect( from, to) {
adjMat[from][to];
}

void warshall { //warshall算法
for( y=0; y<adjMat.length; y) //查找每行
for( x=0; x<adjMat.length; x) // 查找每个单元格
(adjMat[y][x]) //如果 y 可以到达 x
for( z=0; z<adjMat.length; z) //查找所有行y列
//如果 z 可以到达y 介绍说明z 可以直接到达x
(adjMat[z][y]) adjMat[z][x] = true;

}

boolean getConnections {
adjMat;
}

public void (String args) {
WarShall w = WarShall(5);
w.connect(0,2);
w.connect(1,0);
w.connect(1,4);
w.connect(3,4);
w.connect(4,2);
for(boolean a: w.getConnections) {
for(boolean b: a) .out.pr(b + " ");
.out.prln;
}
w.warshall;
.out.prln("");
for(boolean a: w.getConnections) {
for(boolean b: a) .out.pr(b + " ");
.out.prln;
}

assert w.isConnect(3,2);
}
}