Kosaraju算法解析: 求解圖的強連通分量

1. 定義

連通分量：在無向圖中，即為連通子圖。

上圖中，總共有四個連通分量。頂點A、B、C、D構成了一個連通分量，頂點E構成了一個連通分量，頂點F，G和H，I分別構成了兩個連通分量。

強連通分量：有向圖中，盡可能多的若干頂點組成的子圖中，這些頂點都是相互可到達的，則這些頂點成為一個強連通分量。

上圖中有三個強連通分量，分別是a、b、e以及f、g和c、d、h。

2. 連通分量的求解方法

對于一個無向圖的連通分量，從連通分量的任意一個頂點開始，進行一次DFS，一定能遍歷這個連通分量的所有頂點。所以，整個圖的連通分量數應該等價于遍歷整個圖進行了幾次（最外層的）DFS。一次DFS中遍歷的所有頂點屬于同一個連通分量。

下面我們將介紹有向圖的強連通分量的求解方法。

3. Kosaraju算法的基本原理

我們用一個最簡單的例子講解Kosaraju算法

顯然上圖中有兩個強連通分量，即強連通分量A和強連通分量B，分別由頂點A0-A1-A2和頂點B3-B4-B5構成。每個連通分量中有若干個可以相互訪問的頂點（這里都是3個），強連通分量與強連通分量之間不會形成環，否則應該將這些連通分量看成一個整體，即看成同一個強連通分量。

我們現在試想能否按照無向圖中求連通分量的思路求解有向圖的強連通分量。我們假設，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 人民郵電出版社