图－传递闭包

图的传递闭包是指修正后的邻接矩阵表示的图。(见Graph 图－邻接矩阵法 )

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

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

下面是代码：

class WarShall {
	private boolean[][] adjMat;

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

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

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

	void warshall() { //warshall算法
		for(int y=0; y<adjMat.length; y++) //查找每一行
			for(int x=0; x<adjMat.length; x++) // 查找每个单元格
				if(adjMat[y][x])	//如果 y 可以到达 x
					for(int z=0; z<adjMat.length; z++)	//查找所有行的y列
						//如果 z 可以到达y ，说明z 可以直接到达x
						if(adjMat[z][y]) adjMat[z][x] = 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);
	}
}