图－传递闭包
图的传递闭包是指修正后的邻接矩阵表示的图。(见Graph 图－邻接矩阵法)在多个顶点的有向图中，每个顶点可以到按照方向到达一定的节点，这叫图的连通性。有种方法直接告诉我们，图中的两个节点是否可以联通，这里说的是WarShall算法。
WarShall的基本原理是，如果A可以到达B，且C可以到达A，则C可以到达B。通过对邻接矩阵的修正可以做到这点。随然这里举例是将两步可并成一步，但数学上可以证明这种修正可以达到任意步骤。
下面是代码：
class WarShall {private boolean[][] adjMat;WarShall(int size) {adjMat = new boolean;}void connect(int from, int to) {adjMat = true;}boolean isConnect(int from, int to) {return adjMat;}void warshall() { //warshall算法for(int y=0; y<adjMat.length; y++) //查找每一行for(int x=0; x<adjMat.length; x++) // 查找每个单元格if(adjMat)//如果 y 可以到达 xfor(int z=0; z<adjMat.length; z++)//查找所有行的y列//如果 z 可以到达y ，说明z 可以直接到达xif(adjMat) adjMat = true;}boolean[][] getConnections() {return adjMat;}public static void main(String[] args) {WarShall w = new 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) System.out.print(b + " ");System.out.println();}w.warshall();System.out.println("==================");for(boolean[] a: w.getConnections()) {for(boolean b: a) System.out.print(b + " ");System.out.println();}assert w.isConnect(3,2);}}
页:
[1]