给定一个有向图 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 DFS
106 reversedGraph.DFS(0, visited);
107
108 // If all vertices are not visited in second DFS, then
109 // return false
110 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 }
共同學習，寫下你的評論
評論加載中...
作者其他優質文章
