本文共 5083 字，大约阅读时间需要 16 分钟。

JAVA学习—图的连通性检测—2021-06-27

基本概念

无向图 连通图和非联通图： 如果无向图 G 中任意一对顶点都是连通的，则称此图是连通图（connected graph）；相反，如 果一个无向图不是连通图，则称为非连通图（disconnected graph）。对非连通图G，其极大连通子图称为连通分量（connected component，或连通分支），连通分支数记为w(G)。 割顶集与连通度： 设V’是连通图G 的一个顶点子集，在G 中删去V’及与V’关联的边后图不连通，则称 V’ 是 G 的割顶集（vertex-cut set）。如果割顶集V’的任何真子集都不是割顶集，则称V’为极小割顶 集。顶点个数最小的极小割顶集称为最小割顶集。最小割顶集中顶点的个数，称作图G 的顶点连通度（vertex connectivity degree），记做κ(G)，且称图G 是κ–连通图（κ–connected graph）。

割点：如果割顶集中只有一个顶点，则该顶点可以称为割点（cut-vertex），或关节点。

点双连通图：如果一个无向连通图 G 没有关节点，或者说点连通度κ(G) > 1，则称 G 为点双 连通图，或者称为重连通图。

点双连通分量：一个连通图 G 如果不是点双连通图，那么它可以包括几个点双连通分量，也 称为重连通分量（或块）。一个连通图的重连通分量是该图的极大重连通子图，在重连通分量中不存在关节点。

割边集与边连通度：设 E’ 是连通图 G 的边集的子集，在 G 中删去E’后图不连通，则称E’是G 的割边集 （edge-cut set）。如果割边集 E’ 的任何真子集都不是割边集，则称 E’ 为极小割边集。边数最小的极 小割边集称为最小割边集。最小割边集中边的个数，称作图G 的边连通度（edge connectivity degree），记做λ(G)，且称图G 是λ–边连通图（λ–edge–connected graph）。

割边：如果割边集中只有一条边，则该边可以称为割边（bridge），或桥。

边双连通图：如果一个无向连通图 G 没有割边，或者说边连通度λ(G) > 1，则称G 为边双连通图。

边双连通分量：边双连通分量：一个连通图 G 如果不是边双连通图，那么它可以包括几个边双连通分量。一 个连通图的边双连通分量是该图的极大重连通子图，在边双连通分量中不存在割边。在连通图中， 把割边删除，则连通图变成了多个连通分量，每个连通分量就是一个边双连通分量。

顶点连通性与边连通性的关系：（顶点连通度、边连通度与图的最小度的关系） 设G 为无向连通图，则存在关系式：κ(G)≤λ(G)≤δ(G)

割边和割点的联系：（割边和割点的联系）设 v 是图 G 中与一条割边相关联的顶点，则 v 是 G 的割点当且仅当deg(v)≥2

有向图

强连通（strongly connected）：若 G 是有向图，如果对图 G 中任意两个顶点 u 和 v，既存在从 u 到 v 的路径，也存在从 v 到 u 的路径，则称该有向图为强连通有向图。对于非强连通图，其极 大强连通子图称为其强连通分量。

单连通（simply connected）：若 G 是有向图，如果对图 G 中任意两个顶点 u 和 v，存在从 u 到 v 的路径或从 v 到 u 的路径，则称该有向图为单连通有向图。

弱连通（weak connected）：若 G 是有向图，如果忽略图 G 中每条有向边的方向，得到的无向 图（即有向图的基图）连通，则称该有向图为弱连通有向图。

代码

package datastructure.graph;import matrix.IntMatrix;/** * Directed graph. Note that undirected graphs are a special case of directed * graphs. *  * @author hengyuzuo. */public class Graph {
   	/**	 * The connectivity matrix.	 */	IntMatrix connectivityMatrix;	/**	 *********************	 * The first constructor.	 * 	 * @param paraNumNodes	 *            The number of nodes in the graph.	 *********************	 */	public Graph(int paraNumNodes) {
   		connectivityMatrix = new IntMatrix(paraNumNodes, paraNumNodes);	}// Of the first constructor	/**	 *********************	 * The second constructor.	 * 	 * @param paraMatrix	 *            The data matrix.	 *********************	 */	public Graph(int[][] paraMatrix) {
   		connectivityMatrix = new IntMatrix(paraMatrix);	}// Of the second constructor	/**	 *********************	 * Overrides the method claimed in Object, the superclass of any class.	 *********************	 */	public String toString() {
   		String resultString = "This is the connectivity matrix of the graph.\r\n"				+ connectivityMatrix;		return resultString;	}// Of toString	/**	 *********************	 * Get the connectivity of the graph.	 * 	 * @throws Exception	 *             for internal error.	 *********************	 */	public boolean getConnectivity() throws Exception {
   		// Step 1. Initialize accumulated matrix: M_a = I.		IntMatrix tempConnectivityMatrix = IntMatrix				.getIdentityMatrix(connectivityMatrix.getData().length);		// Step 2. Initialize M^1.		IntMatrix tempMultipliedMatrix = new IntMatrix(connectivityMatrix);		// Step 3. Determine the actual connectivity.		for (int i = 0; i < connectivityMatrix.getData().length - 1; i++) {
   			// M_a = M_a + M^k			tempConnectivityMatrix.add(tempMultipliedMatrix);			// M^k			tempMultipliedMatrix = IntMatrix.multiply(tempMultipliedMatrix, connectivityMatrix);		} // 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	/**	 *********************	 * Unit test for getConnectivity.	 *********************	 */	public static void getConnectivityTest() {
   		// Test an undirected graph.		int[][] tempMatrix = {
    {
    0, 1, 0 }, {
    1, 0, 1 }, {
    0, 1, 0 } };		Graph tempGraph2 = new Graph(tempMatrix);		System.out.println(tempGraph2);		boolean tempConnected = false;		try {
   			tempConnected = tempGraph2.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.		tempGraph2.connectivityMatrix.setValue(1, 0, 0);		tempConnected = false;		try {
   			tempConnected = tempGraph2.getConnectivity();		} catch (Exception ee) {
   			System.out.println(ee);		} // Of try.		System.out.println("Is the graph connected? " + tempConnected);	}// Of getConnectivityTest	/**	 *********************	 * The entrance of the program.	 * 	 * @param args	 *            Not used now.	 *********************	 */	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

运行结果

转载地址：http://ulmdi.baihongyu.com/