欢迎探讨，若有错误敬请指正html

如需转载，请注明出处 http://www.cnblogs.com/nullzx/java

1. 定义

连通份量：在无向图中，即为连通子图。算法

上图中，总共有四个连通份量。顶点A、B、C、D构成了一个连通份量，顶点E构成了一个连通份量，顶点F，G和H，I分别构成了两个连通份量。ide

强连通份量：有向图中，尽量多的若干顶点组成的子图中，这些顶点都是相互可到达的，则这些顶点成为一个强连通份量。函数

上图中有三个强连通份量，分别是a、b、e以及f、g和c、d、h。测试

2. 连通份量的求解方法

对于一个无向图的连通份量，从连通份量的任意一个顶点开始，进行一次DFS，必定能遍历这个连通份量的全部顶点。因此，整个图的连通份量数应该等价于遍历整个图进行了几回（最外层的）DFS。一次DFS中遍历的全部顶点属于同一个连通份量。this

下面咱们将介绍有向图的强连通份量的求解方法。spa

3. Kosaraju算法的基本原理

咱们用一个最简单的例子讲解Kosaraju算法3d

显然上图中有两个强连通份量，即强连通份量A和强连通份量B，分别由顶点A0-A1-A2和顶点B3-B4-B5构成。每一个连通份量中有若干个能够相互访问的顶点（这里都是3个），强连通份量与强连通份量之间不会造成环，不然应该将这些连通份量当作一个总体，即当作同一个强连通份量。orm

咱们如今试想可否按照无向图中求连通份量的思路求解有向图的强连通份量。咱们假设，DFS从强连通份量B的任意一个顶点开始，那么刚好遍历整个图须要2次DFS，和连通份量的数量相等，并且每次DFS遍历的顶点刚好属于同一个连通份量。可是，咱们若从连通份量A中任意一个顶点开始DFS，就不能获得正确的结果，由于此时咱们只须要一次DFS就访问了全部的顶点。因此，咱们不该该按照顶点编号的天然顺序（0,1,2，……）或者任意其它顺序进行DFS，而是应该按照被指向的强连通份量的顶点排在前面的顺序进行DFS。上图中由强连通份量A指向了强连通份量B。因此，咱们按照

B3, B4, B5, A0, A1, A2

的顺序进行DFS，这样就能够达到咱们的目的。但事实上这样的顺序太过严格，咱们只须要保证被指向的强连通份量的至少一个顶点排在指向这个连通份量的全部顶点前面便可，好比

B3, A0, A1, A2, B4, B5

B3排在了强连通份量A全部顶点的前面。

如今咱们的关键问题就是如何获得这样一个知足要求的顶点顺序，Kosaraju给出了这解决办法：对原图取反，而后从反向图的任意节点开始进行DFS的逆后序遍历，逆后序获得的顺序必定知足咱们的要求。

DFS的逆后序遍历是指：若是当前顶点未访问，先遍历完与当前顶点相连的且未被访问的全部其它顶点，而后将当前顶点加入栈中，最后栈中从栈顶到栈底的顺序就是咱们须要的顶点顺序。

上图表示原图的反向。

咱们如今进行第一种假设：假设DFS从位于强连通份量A中的任意一个节点开始。那么第一次DFS完成后，栈中所有都是强连通份量A的顶点，第二次DFS完成后，栈顶必定是强连通份量B的顶点。保证了从栈顶到栈底的排序强连通份量B的顶点所有都在强连通份量A顶点以前。

咱们如今进行第二种假设：假设DFS从位于强连通份量B中的任意一个顶点开始。显然咱们只须要进行一次DFS就能够遍历整个图，因为是逆后续遍历，那么起始顶点必定最后完成，因此栈顶的顶点必定是强连通份量B中的顶点，这显然是咱们但愿获得的顶点排序的结果。

上面使用了最简单的例子说明Kosaraju算法的原理，对于有多个强连通份量，链接复杂的状况，仍然适用。你们能够自行举例验证。

综上可得，不论从哪一个顶点开始，图中有多少个强连通份量，逆后续遍历的栈中顶点的顺序必定会保证：被指向的强连通份量的至少一个顶点排在指向这个连通份量的全部顶点前面。因此，咱们求解强连通份量的步骤能够分为两步：

（1）对原图取反，从任意一个顶点开始对反向图进行逆后续DFS遍历

（2）按照逆后续遍历中栈中的顶点出栈顺序，对原图进行DFS遍历，一次DFS遍历中访问的全部顶点都属于同一强连通份量。

4. 求解连通份量和强连通份量的代码实现

测试数据

运行结果

ConnectedComponents 包含了无向图求连通份量以及Kosaraju算法的实现

package datastruct;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.LinkedList;
import java.util.List;

import datastruct.Graph.Edge;

public class ConnectedComponents {
	private boolean[] marked;
	/*用于标记每一个顶点属于哪个（强）连通份量
                 同一（强）连通份量顶点的（强）连通份量编号值相同*/
	private int[] id;
	private int count;//（强）连通份量的编号，也表示（强）连通份量的个数
	private Graph g;
	
	public ConnectedComponents(Graph g){
		this.g = g;
		marked = new boolean[g.V()];
		id = new int[g.V()];
		
		if(g.isDirect()){//有向图求强连通份量的方法
			//反向图DFS的逆后序,从0号顶点开始,能够从任意顶点开始
			LinkedList<Integer> stack = g.reverse().reversePostOrder(0);
			marked = new boolean[g.V()];
			while(!stack.isEmpty()){
				int v = stack.pop();
				if(!marked[v]){
					dfs(v);
					count++;
				}
			}
		}else{//无向图的连通份量
			for(int i = 0; i < g.V(); i++){
				if(!marked[i]){
					dfs(i);
					count++;
				}
			}
		}
	}
	
	private void dfs(int v){
		if(!marked[v]){
			marked[v] = true;
			id[v] = count;
			for(Edge e : g.adjEdge(v)){
				int w = e.other(v);
				dfs(w);
			}
		}
	}
	
	
	public int count(){
		return count;
	}
	
	//与顶点v属于同一连通份量的全部顶点
	public List<Integer> allConnected(int v){
		LinkedList<Integer> list = new LinkedList<Integer>();
		int k = id[v];
		for(int i = 0; i < g.V(); i++){
			if(id[i] == k){
				list.add(i);
			}
		}
		return list;
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		File path = new File(System.getProperty("user.dir")).getParentFile();
		File f = new File(path,"algs4-data/tinyDG2.txt");
		FileReader fr = new FileReader(f);
		Graph graph = new Graph(fr, true, false);
		
		System.out.println("图的表示");
		System.out.println(graph);
		
		ConnectedComponents cc = new ConnectedComponents(graph);
		
		System.out.println("连通份量数：  " + cc.count());
		System.out.println("\n");
		
		System.out.println("和顶点 0 共属于同一个连通份量的顶点");
		for(int i : cc.allConnected(0)){
			System.out.printf("%-3d", i);
		}
		System.out.println("\n");
		
		System.out.println("和顶点 3 共属于同一个连通份量的顶点");
		for(int i : cc.allConnected(3)){
			System.out.printf("%-3d", i);
		}
		System.out.println("\n");
		
		System.out.println("和顶点 9 共属于同一个连通份量的顶点");
		for(int i : cc.allConnected(9)){
			System.out.printf("%-3d", i);
		}
		System.out.println("\n");
		
		System.out.println("和顶点 6 共属于同一个连通份量的顶点");
		for(int i : cc.allConnected(6)){
			System.out.printf("%-3d", i);
		}
		System.out.println();
	}
}

图的临接表示，包含了不少实用的方法，可是此处主要使用经过原图构造它的反方向图和逆后序

package datastruct;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StringWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;


public class Graph{
	private int v;//顶点数量
	private int e;//边数量
	private boolean isWeight;  //时候是带权重的图
	private boolean isDirect;  //是不是有向图
	private boolean hasCycle;  //图中时候含有环
	private LinkedList<Edge>[] adj;//临接表
	
	//图中边的表示
	public static class Edge implements Comparable<Edge>{
		private final int from;//边起始顶点
		private final int to;//边终结顶点
		private final double w; //权值
		public Edge(int from, int to, double w){
			this.from = from;
			this.to = to;
			this.w = w;
		}
		
		//返回任意一个顶点
		public int either(){
			return from;
		}
		
		//返回另外一个顶点
		public int other(int v){
			return v == this.from ? to : from;
		}
		
		//用于有向图
		public int from(){
			return from;
		}
		
		//用于有向图
		public int to(){
			return to;
		}
		
		public double weight(){
			return w;
		}

		//边比较器，已权重为依据
		@Override
		public int compareTo(Edge that) {
			if(this.w > that.w){
				return 1;
			}else
			if(this.w < that.w){
				return -1;
			}else{
				return 0;
			}
		}
		
		//边的显示方法
		@Override
		public String toString(){
			return new String(String.format("%-2d", from) + "  "
							  + String.format("%-2d", to) + "  " 
					          + String.format("%-4.2f", w));
		}
	}
	
//	public static class Cmp implements Comparator<Edge>{
//		@Override
//		public int compare(Edge e1, Edge e2) {
//			return e1.compareTo(e2);
//		}
//	}
	
	//从文件流中读入图的txt文件来构造图
	@SuppressWarnings("unchecked")
	public Graph(Reader r, boolean isDirect, boolean isWeight){
		BufferedReader br = new BufferedReader(r);
		Scanner scn = new Scanner(br);
		v = scn.nextInt();
		e = scn.nextInt();
		this.isWeight = isWeight;
		this.isDirect = isDirect;
		
		adj = (LinkedList<Edge>[])new LinkedList[v];
		
		for(int i = 0; i < v; i++){
			adj[i] = new LinkedList<Edge>();
		}
		
		for(int i = 0; i < e; i++){
			int from = scn.nextInt();
			int to = scn.nextInt();
			double w;
			if(isWeight){
				w = scn.nextDouble();
			}else{//若是不是带权重的图，默认权重是1
				w = 1;
			}
			Edge e = new Edge(from, to, w);
			adj[from].add(e);
			if(!isDirect){
				adj[to].add(e);
			}
		}
		scn.close();
	}
	
	//当前图的反向图构造函数
	@SuppressWarnings("unchecked")
	private Graph(Graph g){
		v = g.V();
		e = g.E();
		this.isWeight = g.isWeight;
		this.isDirect = g.isDirect;
		hasCycle = g.hasCycle;
		
		adj = (LinkedList<Edge>[]) new LinkedList[v];
		for(int i = 0; i < v; i++){
			adj[i] = new LinkedList<Edge>();
		}
		
		for(int from = 0; from < v; from++){
			for(Edge e : g.adj[from]){
				int to = e.other(from);
				double 	w = e.weight();
				adj[to].add(new Edge(to, from, w));
			}
		}
	}
	
	//返回当前图的反向图
	public Graph reverse(){
		if(this.isDirect){
			return new Graph(this);
		}else{
			throw new IllegalArgumentException("Graph is not Directed");
		}
	}
	
	//经过添加边来构造图的构造函数
	@SuppressWarnings("unchecked")
	public Graph(int v, boolean isDirect, boolean isWeight){
		adj = (LinkedList<Edge>[])new LinkedList[v];
		for(int i = 0; i < v; i++){
			adj[i] = new LinkedList<Edge>();
		}
		this.isDirect = isDirect;
		this.isWeight = isWeight;
		this.v = v;
	}
	
	//添加一条边
	public void addEdge(Edge e){
		adj[e.from].add(e);
		this.e++;
		if(!isDirect){
			this.e++;
			adj[e.to()].add(e);
		}
	}
	
	//返回图中顶点个数
	public int V(){
		return v;
	}
	
	//返回图中边的数量
	public int E(){
		return e;
	}
	
	//邻接顶点，返回与顶点v相邻的全部顶点的编号
	public List<Integer> adjVertex(int v){
		ArrayList<Integer> list = new ArrayList<Integer>(adj[v].size());
		for(Edge e : adj[v]){
			list.add(e.other(v));
		}
		return list;
	}
	
	//返回与顶点v相邻的边，对于位于同一包中的类，这个方法效率更高
	public List<Edge> adjEdge(int v){
		return adj[v];
	}
	
	//返回一条边
	public Edge getEdge(int from, int to){
		for(Edge e : adj[from]){
			if(e.other(from) == to){
				return e;
			}
		}
		return null;
	}
	
	//是不是有向图
	public boolean isDirect(){
		return isDirect;
	}
	
	//是不是带权重的图
	public boolean isWeight(){
		return isWeight;
	}
	
	//是不是有向无有环图
	public boolean isDAG(){
		if(!isDirect){
			return false;
		}
		
		boolean[] marked = new boolean[v];
		boolean[] onStack = new boolean[v];
		
		for(int i = 0; i < v; i++){
			if(!marked[i]){
				dfs(i, marked, onStack);
			}
		}
		return !hasCycle;
	}
	
	//用于判断DAG的深度优先遍历
	private void dfs(int v, boolean[] marked, boolean[] onStack){
		if(hasCycle){
			return;
		}
		
		marked[v] = true;
		onStack[v] = true;
		for(Edge e : adj[v]){
			int w = e.other(v);
			if(!marked[w]){
				dfs(w, marked, onStack);
			}else
			if(onStack[w]){
				hasCycle = true;
				return;
			}
		}
		onStack[v] = false;
	}
	
	//图的显示方法
	public String toString(){
		StringWriter sw = new StringWriter(5*v + 10*e);//长度不是一个准确值，是尽可能往大估计的
		PrintWriter pw = new PrintWriter(sw);
		for(int i = 0; i < v; i++){
			pw.printf("%-3d: ", i);
			for(Edge e : adj[i]){
				if(isWeight){
					pw.printf("[%-3d, %-4.2f]  ", e.other(i), e.w);
				}else{					
					pw.printf("%-3d ", e.other(i));
				}
			}
			pw.println();
		}
		return sw.getBuffer().toString();
	}
	
//是否存在从from到to的边
//	public boolean hasEdge(int from, int to){
//		boolean[] marked = new boolean[v];
//		hasEdge0(from, to, marked);
//		return marked[to];
//	}
//	
//	private void hasEdge0(int from, int to, boolean[] marked){
//		if(!marked[from]){
//			marked[from] = true;
//			for(Edge e : adj[from]){
//				if(!marked[to]){
//					hasEdge0(e.other(from), to, marked);
//				}else{
//					return;
//				}
//			}
//		}
//	}
	
	//从from节点开始逆后序遍历,返回逆后序的栈
	public LinkedList<Integer> reversePostOrder(int from){
		LinkedList<Integer> stack = new LinkedList<Integer>();
		boolean[] marked = new boolean[v];
		for(int i = 0; i < v; i++){
			reversePostOrderTar(i, stack, marked);
		}
		return stack;
	}
	
	//用于逆后序的深度优先遍历
	private void reversePostOrderTar(int from, LinkedList<Integer> stack, boolean[] marked){
		if(!marked[from]){
			marked[from] = true;
			for(Edge e : adj[from]){
				reversePostOrderTar(e.other(from), stack, marked);
			}
			stack.push(from);
		}
	}
	
	public static void main(String[] args) throws FileNotFoundException{
		File path = new File(System.getProperty("user.dir")).getParentFile();
		File f = new File(path, "algs4-data/tinyDG.txt");
		FileReader fr = new FileReader(f);
		Graph g = new Graph(fr, true, false);
		System.out.println(g.toString());
		System.out.println(g.reverse().toString());
//		System.out.println(g.hasEdge(0, 7));
	}
	
}

5. 参考内容

[1]. 算法（第4版）Robert Sedgewick 人民邮电出版社