基于java的图(四) 强连通组件

有向图中, u可达v不一定意味着v可达u. 相互可达则属于同一个强连通分量
最关键通用部分：强连通分量一定是图的深搜树的一个子树。



算法步骤：

    1）对图G进行深度搜索生成森林（树）

    2）生成图G的转置图G’ 
    3）用1）中生成的顶点到转置图中查找相关联的节点，返回的即为一个强连通分量

 

代码：

    

/**
	 * 返回图的强连通组件
	 * @param <T>
	 * @param graph
	 * @return
	 */
	public static<T> List<List<T>> getStrongComponents(Graph<T> graph){
		List<T> vList = visitGraph(graph);
		Collections.reverse(vList);
		Graph<T> graphT = transpose(graph);
		List<List<T>> components = new ArrayList<List<T>>();
		List<T> component = null;
		graphT.allUnVisted();
		for(T v : vList){
			if(graphT.getState(v) == VertexState.UNVISITED){
				component = new ArrayList<T>();
				dfsHandler(graphT, v, false, component);
				components.add(component);
			}
			
		}
		
		return components;
	}
	/**
	 * 得到图的转置图
	 * @param <T>
	 * @param graph
	 * @return
	 */
	private static<T> Graph<T> transpose(Graph<T> graph){
		Graph<T> graphT = new EGraph<T>();
		Set<T> vSet = graph.vertexSet();//得到顶点数
		Set<T> neighbors = null;
		for(T v : vSet){//加入顶点
			graphT.addVertex(v);
		}
		for(T v : vSet){//转向
			neighbors = graph.getNeighbors(v);
			for(T neighbor : neighbors){
				graphT.addEdge(neighbor, v, graph.getWeight(v, neighbor));
			}
		}
		return graphT;
	}