今天花了一上午时间实现这个算法，一开始一直没有理解，加上好久不动算法，结果效率很低。下面将从中学到的一些东西总结在这里吧。
一、算法的步骤及图解
Kosaraju 算法也许最容易理解的一个算法是Kosaraju 于80 年代提
出的，它执行两次DFS。第一次DFS 得到了关于各个SCC 拓扑顺序的有关信息，而第二次DFS 按照这个拓扑顺序的逆序进行DFS，从而把每个SCC 分开。算法步骤如下：第1 步：对有向图进行DFS，记录下顶点变黑的时间A[i]；遍历结果构建一个森林W1，我们对森林中的每棵树做②、③步操作；第2 步：改变图G 的每一条边的方向Gr；第3 步：按上次DFS 顶点变黑的时间A[i]由大到小的顺序对Gr 进行DFS，遍历的结果构成森林W2，W2 中每棵树的结点构成了有向图的一个SCC。算法的时间复杂度为O(n+m)，下面我们来举例说明为什么经过上面的操作可以得到连通分支：
有上面可得到如下结论：
●在每个生成树中，根的时间戳最大；●根可以到达该树的任何一个结点（其他结点不一定能到达根）；●每棵子树的根的时间戳都大于其后代结点；他也可以到达它的所有后代；第2 步：现在我们对图进行反向，然后按时间戳由大到小进行dfs得到森林如下： 
通俗讲，这个原理就是：第一次dfs 的生成树中若存在回边，那么
边反方向后仍然可以相互到达，于是就是一个连通分量。
二、算法的证明
假设在后来转置后的图中从x dfs到了 y处，说明存在路径x->y。因为这是在转置图中，所以说明原图中存在路径y->x。
然后另外一个信息就是x的序号在y之后。这有两种可能：
1、以y为根先DFS出了一棵搜索树(可以认为是整个搜索树的一棵子树)，但是这棵子树里不包含x，并且此时x还未被dfs到。（利用反证法，如果这棵子树里包含了x，那么x的序号会在y之前）
2、y是x扩展出来的搜索树中的一个结点。
综合两个条件，综合两个条件取交。那么上面两种可能中的第一种不成立。因为存在路径y->x，所以如果x未被dfs到，一定会被y为根的搜索树包含的。于是只剩下第二种可能，那么第二种情况表明存在路径x->y。所以x,y可以互相到达。至此证明了该算法求出的都是强连通分量。命题1得证。
三、算法实现
1 import java.io.BufferedReader; 2 import java.io.FileNotFoundException; 3 import java.io.FileReader; 4 import java.io.IOException; 5 import java.util.ArrayList; 6 import java.util.HashMap; 7 import java.util.Vector; 8 9 public class Kosaraju { 10 public static HashMap G = new HashMap (), 11 GR = new HashMap (); 12 public static int cnt = 0, cntR = 0; 13 public static int[] pre = new int[1000000], postR = new int[1000000], 14 sc = new int[1000000]; 15 16 public static void main(String args[]) { 17 initializeGraph(); 18 for (int i = 1; i < 1000000; i++) { 19 pre[i] = -1; 20 postR[i] = -1; 21 sc[i] = -1; 22 } 23 System.out.println("Begin DFS 1"); 24 for (int i = 1; i < 1000000; i++) { 25 if (pre[i] == -1) { 26 dfsR(i); 27 } 28 } 29 cnt = 0; 30 System.out.println("Begin DFS 2"); 31 for (int i = 900000; i >= 0; i--) { 32 if (sc[postR[i]] == -1) { 33 if (G.get(i+1) != null){ 34 dfsSc(postR[i]); 35 cnt++; 36 } 37 // System.out.println("DFS2 " + cnt); 38 } 39 } 40 System.out.println(cnt); 41 } 42 43 public static void initializeGraph() { 44 try { 45 FileReader fr = new FileReader( 46 "C:\\Users\\waruzhi\\Desktop\\SCC.txt"); 47 BufferedReader br = new BufferedReader(fr); 48 String tmp; 49 int nodeA, nodeB; 50 while ((tmp = br.readLine()) != null) { 51 nodeA = Integer.parseInt(tmp.substring(0, tmp.indexOf(" "))); 52 nodeB = Integer.parseInt(tmp.substring(tmp.indexOf(" ") + 1, 53 tmp.length() - 1)); 54 Node tA = G.get(nodeA), tB = G.get(nodeB), tAR = GR.get(nodeA), tBR = GR 55 .get(nodeB); 56 if (tA == null) { 57 Node newNode = new Node(nodeA); 58 G.put(nodeA, newNode); 59 tA = newNode; 60 newNode = new Node(nodeA); 61 GR.put(nodeA, newNode); 62 tAR = newNode; 63 } 64 if (tB == null) { 65 Node newNode = new Node(nodeB); 66 G.put(nodeB, newNode); 67 tB = newNode; 68 newNode = new Node(nodeB); 69 GR.put(nodeB, newNode); 70 tBR = newNode; 71 } 72 if (tA != tB) { 73 tA.out.add(tB); 74 tBR.out.add(tAR); 75 } 76 } 77 } catch (FileNotFoundException e) { 78 // TODO Auto-generated catch block 79 e.printStackTrace(); 80 } catch (IOException e) { 81 // TODO Auto-generated catch block 82 e.printStackTrace(); 83 } 84 } 85 86 public static void dfsR(int num) { 87 Node tmp = GR.get(num); 88 if (tmp != null) { 89 pre[num] = cnt++; 90 // System.out.println("DFS1: " + num + ";cnt = " + cnt); 91 for (Node aNode : tmp.out) { 92 if (pre[aNode.num] == -1) { 93 dfsR(aNode.num); 94 } 95 } 96 } 97 postR[cntR++] = num; 98 } 99 100 public static void dfsSc(int num) {101 Node tmp = G.get(num);102 if (tmp != null) {103 sc[num] = cnt;104 for (Node aNode : tmp.out) {105 if (sc[aNode.num] == -1) {106 dfsSc(aNode.num);107 }108 }109 }110 }111 }
四、参考代码
1 // Kosaraju算法邻接矩阵实现 2 3 static int cnt, cntR, pre[MAXV], postR[MAXV]; 4 int Kosaraju(Graph G) { 5 int v; 6 // 初始化全局变量 7 cnt = cntR = 0; 8 for (v = 0; v < G->V; ++v) 9 pre[v] = postR[v] = -1;10 // 第一次DFS，计算逆图的后序编号11 for (v = 0; v < G->V; ++v)12 if (pre[v] == -1)13 dfsPostR(G, v);14 cnt = 0;15 for (v = 0; v < G->V; ++v)16 G->sc[v] = -1; // G->sv[v]表示顶点v的强连通分量编号17 // 第二次DFS，强连通分量编号18 for (v = G->V - 1; v >= 0; --v) {19 // 注意搜索的顶点顺序是逆图后序编号的逆序20 if (G->sc[postR[v]] == -1) {21 dfsSC(G, postR[v]);22 ++cnt; // 对一棵树编号之后计数器值加123 }24 }25 return cnt; // 返回强连通分量的个数26 }27 28 void dfsPostR(Graph G, int v) {29 // 对逆图后序编号30 int t;31 pre[v] = cnt++;32 for (t = 0; t < G->V; ++t)33 if (G->adj[t][v] == 1) // 注意!!!邻接矩阵引用逆图,因此是G->adj[t][v]34 if (pre[t] == -1)35 dfsPostR(G, t);36 postR[cntR++] = v; // 后序编号,注意是计数器做数组下标37 }38 39 void dfsSC(Graph G, int v) {40 int t;41 G->sc[v] = cnt; // 计数器作为编号42 for (t = 0; t < G->V; ++t)43 if (G->adj[v][t] == 1)44 if (G->sc[t] == -1)45 dfsSC(G, t);46 }47 48 int GraphSC(Graph G, int s, int t) {49 // 比较顶点的强连通分量编号即可判断是否强连通50 return G->sc[s] == G->sc[t];51 }