Kosaraju 算法查找强连通分支

浏览数：38 / 时间：2015年06月08日

有向图 G = (V, E) 的一个强连通分支（SCC：Strongly Connected Components）是一个最大的顶点集合 C，C 是 V 的子集，对于 C 中的每一对顶点 u 和 v，有 u --> v 和 v --> u，亦即，顶点 u 和 v 是互相可达的。

实际上，强连通分支 SCC 将有向图分割为多个内部强连通的子图。如下图中，整个图不是强连通的，但可以被分割成 3 个强连通分支。

技术分享

通过 Kosaraju 算法，可以在 O(V+E) 运行时间内找到所有的强连通分支。Kosaraju 算法是基于深度优先搜索（DFS），算法的描述如下：

创建一个空的栈 S，并做一次 DFS 遍历。在 DFS 遍历中，当在递归调用 DSF 访问邻接顶点时，将当前顶点压入栈中；
置换图（Transpose Graph）；
从栈 S 中逐个弹出顶点 v，以 v 为源点进行 DFS 遍历。从 v 开始的 DFS 遍历将输出 v 关联的强连通分支。

例如，对于上面的图做第一次 DFS 遍历，然后反转图，则可理解为整个图中的边的方向均反转了。

技术分享

下面是 Kosaraju 算法的 C# 实现。

  1 using System;
  2 using System.Collections.Generic;
  3 using System.Linq;
  4 
  5 namespace GraphAlgorithmTesting
  6 {
  7   class Program
  8   {
  9     static void Main(string[] args)
 10     {
 11       Graph g = new Graph(5);
 12       g.AddEdge(1, 0, 11);
 13       g.AddEdge(0, 3, 13);
 14       g.AddEdge(2, 1, 10);
 15       g.AddEdge(3, 4, 12);
 16       g.AddEdge(0, 2, 4);
 17 
 18       Console.WriteLine();
 19       Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount);
 20       Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount);
 21       Console.WriteLine();
 22 
 23       List<List<int>> sccs = g.Kosaraju();
 24       foreach (var scc in sccs)
 25       {
 26         foreach (var vertex in scc)
 27         {
 28           Console.Write("{0} ", vertex);
 29         }
 30         Console.WriteLine();
 31       }
 32 
 33       Console.ReadKey();
 34     }
 35 
 36     class Edge
 37     {
 38       public Edge(int begin, int end, int weight)
 39       {
 40         this.Begin = begin;
 41         this.End = end;
 42         this.Weight = weight;
 43       }
 44 
 45       public int Begin { get; private set; }
 46       public int End { get; private set; }
 47       public int Weight { get; private set; }
 48 
 49       public override string ToString()
 50       {
 51         return string.Format(
 52           "Begin[{0}], End[{1}], Weight[{2}]",
 53           Begin, End, Weight);
 54       }
 55     }
 56 
 57     class Graph
 58     {
 59       private Dictionary<int, List<Edge>> _adjacentEdges
 60         = new Dictionary<int, List<Edge>>();
 61 
 62       public Graph(int vertexCount)
 63       {
 64         this.VertexCount = vertexCount;
 65       }
 66 
 67       public int VertexCount { get; private set; }
 68 
 69       public IEnumerable<int> Vertices { get { return _adjacentEdges.Keys; } }
 70 
 71       public IEnumerable<Edge> Edges
 72       {
 73         get { return _adjacentEdges.Values.SelectMany(e => e); }
 74       }
 75 
 76       public int EdgeCount { get { return this.Edges.Count(); } }
 77 
 78       public void AddEdge(int begin, int end, int weight)
 79       {
 80         if (!_adjacentEdges.ContainsKey(begin))
 81         {
 82           var edges = new List<Edge>();
 83           _adjacentEdges.Add(begin, edges);
 84         }
 85 
 86         _adjacentEdges[begin].Add(new Edge(begin, end, weight));
 87       }
 88 
 89       public List<List<int>> Kosaraju()
 90       {
 91         Stack<int> stack = new Stack<int>();
 92 
 93         // Mark all the vertices as not visited (For first DFS)
 94         bool[] visited = new bool[VertexCount];
 95         for (int i = 0; i < visited.Length; i++)
 96           visited[i] = false;
 97 
 98         // Fill vertices in stack according to their finishing times
 99         for (int i = 0; i < visited.Length; i++)
100           if (!visited[i])
101             FillOrder(i, visited, stack);
102 
103         // Create a reversed graph
104         Graph reversedGraph = Transpose();
105 
106         // Mark all the vertices as not visited (For second DFS)
107         for (int i = 0; i < visited.Length; i++)
108           visited[i] = false;
109 
110         List<List<int>> sccs = new List<List<int>>();
111 
112         // Now process all vertices in order defined by Stack
113         while (stack.Count > 0)
114         {
115           // Pop a vertex from stack
116           int v = stack.Pop();
117 
118           // Print Strongly connected component of the popped vertex
119           if (!visited[v])
120           {
121             List<int> scc = new List<int>();
122             reversedGraph.DFS(v, visited, scc);
123             sccs.Add(scc);
124           }
125         }
126 
127         return sccs;
128       }
129 
130       void DFS(int v, bool[] visited, List<int> scc)
131       {
132         visited[v] = true;
133         scc.Add(v);
134 
135         if (_adjacentEdges.ContainsKey(v))
136         {
137           foreach (var edge in _adjacentEdges[v])
138           {
139             if (!visited[edge.End])
140               DFS(edge.End, visited, scc);
141           }
142         }
143       }
144 
145       void FillOrder(int v, bool[] visited, Stack<int> stack)
146       {
147         // Mark the current node as visited and print it
148         visited[v] = true;
149 
150         // Recur for all the vertices adjacent to this vertex
151         if (_adjacentEdges.ContainsKey(v))
152         {
153           foreach (var edge in _adjacentEdges[v])
154           {
155             if (!visited[edge.End])
156               FillOrder(edge.End, visited, stack);
157           }
158         }
159 
160         // All vertices reachable from v are processed by now, 
161         // push v to Stack
162         stack.Push(v);
163       }
164 
165       Graph Transpose()
166       {
167         Graph g = new Graph(this.VertexCount);
168 
169         foreach (var edge in this.Edges)
170         {
171           g.AddEdge(edge.End, edge.Begin, edge.Weight);
172         }
173 
174         return g;
175       }
176     }
177   }
178 }