首页 > 代码库 > Kosaraju 算法检测有向图的强连通性
Kosaraju 算法检测有向图的强连通性
给定一个有向图 G = (V, E) ，对于任意一对顶点 u 和 v，有 u --> v 和 v --> u，亦即，顶点 u 和 v 是互相可达的，则说明该图 G 是强连通的（Strongly Connected）。如下图中，任意两个顶点都是互相可达的。
对于无向图，判断图是否是强连通的，可以直接使用深度优先搜索（DFS）或广度优先搜索（BFS），从任意一个顶点出发，如果遍历的结果包含所有的顶点，则说明图是强连通的。
而对于有向图，则不能使用 DFS 或 BFS 进行直接遍历来判断。如下图中，如果从顶点 0 开始遍历则可判断是强连通的，而如果从其它顶点开始遍历则无法抵达所有节点。
那么，该如何判断有向图的强连通性呢？
实际上，解决该问题的较好的方式就是使用强连通分支算法（SCC：Strongly Connected Components），可以在 O(V+E) 时间内找到所有的 SCC。如果 SCC 的数量是 1，则说明整个图是强连通的。
有向图 G = (V, E) 的一个强连通分支是一个最大的顶点集合 C，C 是 V 的子集，对于 C 中的每一对顶点 u 和 v，有 u --> v 和 v --> u，亦即，顶点 u 和 v 是互相可达的。
实现 SCC 的一种算法就是 Kosaraju 算法。Kosaraju 算法基于深度优先搜索（DFS），并对图进行两次 DFS 遍历，算法步骤如下：
- 初始化设置所有的顶点为未访问的；
- 从任意顶点 v 开始进行 DFS 遍历，如果遍历结果没有访问到所有顶点，则说明图不是强连通的；
- 置换整个图（Reverse Graph）；
- 设置置换后的图中的所有顶点为未访问过的；
- 从与步骤 2 中相同的顶点 v 开始做 DFS 遍历，如果遍历没有访问到所有顶点，则说明图不是强连通的，否则说明图是强连通的。
Kosaraju 算法的思想就是，如果从顶点 v 可以抵达所有顶点，并且所有顶点都可以抵达 v，则说明图是强连通的。
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(0, 1, 11); 13 g.AddEdge(1, 2, 13); 14 g.AddEdge(2, 3, 10); 15 g.AddEdge(3, 0, 12); 16 g.AddEdge(2, 4, 4); 17 g.AddEdge(4, 2, 14); 18 19 Console.WriteLine(); 20 Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount); 21 Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount); 22 Console.WriteLine(); 23 24 Console.WriteLine("Is graph strongly connected: {0}", g.Kosaraju()); 25 26 Console.ReadKey(); 27 } 28 29 class Edge 30 { 31 public Edge(int begin, int end, int weight) 32 { 33 this.Begin = begin; 34 this.End = end; 35 this.Weight = weight; 36 } 37 38 public int Begin { get; private set; } 39 public int End { get; private set; } 40 public int Weight { get; private set; } 41 42 public override string ToString() 43 { 44 return string.Format( 45 "Begin[{0}], End[{1}], Weight[{2}]", 46 Begin, End, Weight); 47 } 48 } 49 50 class Graph 51 { 52 private Dictionary<int, List<Edge>> _adjacentEdges 53 = new Dictionary<int, List<Edge>>(); 54 55 public Graph(int vertexCount) 56 { 57 this.VertexCount = vertexCount; 58 } 59 60 public int VertexCount { get; private set; } 61 62 public IEnumerable<int> Vertices { get { return _adjacentEdges.Keys; } } 63 64 public IEnumerable<Edge> Edges 65 { 66 get { return _adjacentEdges.Values.SelectMany(e => e); } 67 } 68 69 public int EdgeCount { get { return this.Edges.Count(); } } 70 71 public void AddEdge(int begin, int end, int weight) 72 { 73 if (!_adjacentEdges.ContainsKey(begin)) 74 { 75 var edges = new List<Edge>(); 76 _adjacentEdges.Add(begin, edges); 77 } 78 79 _adjacentEdges[begin].Add(new Edge(begin, end, weight)); 80 } 81 82 public bool Kosaraju() 83 { 84 // Step 1: Mark all the vertices as not visited (For first DFS) 85 bool[] visited = new bool[VertexCount]; 86 for (int i = 0; i < visited.Length; i++) 87 visited[i] = false; 88 89 // Step 2: Do DFS traversal starting from first vertex. 90 DFS(0, visited); 91 92 // If DFS traversal doesn’t visit all vertices, then return false. 93 for (int i = 0; i < VertexCount; i++) 94 if (visited[i] == false) 95 return false; 96 97 // Step 3: Create a reversed graph 98 Graph reversedGraph = Transpose(); 99 100 // Step 4: Mark all the vertices as not visited (For second DFS)101 for (int i = 0; i < visited.Length; i++)102 visited[i] = false;103 104 // Step 5: Do DFS for reversed graph starting from first vertex.105 // Staring Vertex must be same starting point of first DFS106 reversedGraph.DFS(0, visited);107 108 // If all vertices are not visited in second DFS, then109 // return false110 for (int i = 0; i < VertexCount; i++)111 if (visited[i] == false)112 return false;113 114 return true;115 }116 117 void DFS(int v, bool[] visited)118 {119 visited[v] = true;120 121 if (_adjacentEdges.ContainsKey(v))122 {123 foreach (var edge in _adjacentEdges[v])124 {125 if (!visited[edge.End])126 DFS(edge.End, visited);127 }128 }129 }130 131 Graph Transpose()132 {133 Graph g = new Graph(this.VertexCount);134 135 foreach (var edge in this.Edges)136 {137 g.AddEdge(edge.End, edge.Begin, edge.Weight);138 }139 140 return g;141 }142 }143 }144 }
参考资料
- Connectivity in a directed graph
- Strongly Connected Components
- Tarjan‘s Algorithm to find Strongly Connected Components
本篇文章《Kosaraju 算法检测有向图的强连通性》由 Dennis Gao 发表自博客园，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。
Kosaraju 算法检测有向图的强连通性
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。