文章出處

給定一個有向圖 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 遍歷,算法步驟如下:

  1. 初始化設置所有的頂點為未訪問的;
  2. 從任意頂點 v 開始進行 DFS 遍歷,如果遍歷結果沒有訪問到所有頂點,則說明圖不是強連通的;
  3. 置換整個圖(Reverse Graph);
  4. 設置置換后的圖中的所有頂點為未訪問過的;
  5. 從與步驟 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 }

參考資料

本篇文章《Kosaraju 算法檢測有向圖的強連通性》由 Dennis Gao 發表自博客園,未經作者本人同意禁止任何形式的轉載,任何自動或人為的爬蟲轉載行為均為耍流氓。


文章列表


不含病毒。www.avast.com
arrow
arrow
    全站熱搜
    創作者介紹
    創作者 大師兄 的頭像
    大師兄

    IT工程師數位筆記本

    大師兄 發表在 痞客邦 留言(0) 人氣()