JAVA学习 32

M的n次方即两点n步可达的矩阵，最多n-1步，所以用此判断是否可达。

先是根据连通性构造图

package datastructure.graph;

import matrix.IntMatrix;


public class Graph {

	
	IntMatrix collecionIntMatrix;

	
	public Graph(int paraNumNodes) {
		collecionIntMatrix = new IntMatrix(paraNumNodes, paraNumNodes);
	}// Of the first constructor

	
	public Graph(int[][] paraMatrix) {
		collecionIntMatrix = new IntMatrix(paraMatrix);
	}// Of the second constructor

	
	@Override
	public String toString() {
		String resultString = "This is the connectivity matrix of the graph.rn" + collecionIntMatrix;
		return resultString;
	}// Of toString

	
	public boolean getConnectivity() throws Exception {
		// Step 1. Initialize accumulated matrix: M_a = I.
		IntMatrix tempConnectivityMatrix = IntMatrix.getIdentityMatrix(collecionIntMatrix.getData().length);

		// Step 2. Initialize M^1.
		IntMatrix tempMultipliedMatrix = new IntMatrix(collecionIntMatrix);

		// Step 3. Determine the actual connectivity.
		for (int i = 0; i < collecionIntMatrix.getRows() - 1; i++) {
			tempConnectivityMatrix.add(tempMultipliedMatrix);

			tempMultipliedMatrix = tempMultipliedMatrix.multiply(tempMultipliedMatrix, collecionIntMatrix);
		} // 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() {
		int[][] tempMatrix = { { 0, 1, 0 }, { 1, 0, 1 }, { 0, 1, 0 } };
		Graph tempGraph = new Graph(tempMatrix);
		System.out.println(tempGraph);

		boolean tempConnected = false;
		try {
			tempConnected = tempGraph.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.
		tempGraph.collecionIntMatrix.setValue(1, 0, 0);
		tempConnected = false;
		try {
			tempConnected = tempGraph.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