Kosaraju 算法检测有向图的强连通性

  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 }