给定有向图 G = (V, E)，需要判断该图中是否存在环路（Cycle）。例如，下面的图 G 中包含 4 个顶点和 6 条边。
实际上，上图中存在 3 个环路：0->2->0, 0->1->2->0, 3->3。
深度优先搜索（DFS：Depth-First Search）可以用于检测图中是否存在环。DFS 会对一个连通的图构造一颗树，如果在构造树的过程中出现反向边（Back Edge），则认为图中存在环路。
对于非连通图，可以对图中的不同部分分别进行 DFS 构造树结构，对于每棵树分别检测反向边的存在。
在 DFS 对图进行遍历时，将遍历过的顶点放入递归栈中，如果新遍历的顶点已经存在于递归栈中，则说明存在一个反向边，即存在一个环。
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(6); 12 g.AddEdge(0, 1, 16); 13 g.AddEdge(0, 2, 13); 14 g.AddEdge(1, 2, 10); 15 g.AddEdge(1, 3, 12); 16 g.AddEdge(2, 1, 4); 17 g.AddEdge(2, 4, 14); 18 //g.AddEdge(3, 2, 9); 19 g.AddEdge(3, 5, 20); 20 //g.AddEdge(4, 3, 7); 21 //g.AddEdge(4, 5, 4); 22 23 Console.WriteLine(); 24 Console.WriteLine("Graph Vertex Count : {0}", g.VertexCount); 25 Console.WriteLine("Graph Edge Count : {0}", g.EdgeCount); 26 Console.WriteLine(); 27 28 Console.WriteLine("Is there cycle in graph: {0}", g.HasCycle()); 29 30 Console.ReadKey(); 31 } 32 33 class Edge 34 { 35 public Edge(int begin, int end, int weight) 36 { 37 this.Begin = begin; 38 this.End = end; 39 this.Weight = weight; 40 } 41 42 public int Begin { get; private set; } 43 public int End { get; private set; } 44 public int Weight { get; private set; } 45 46 public override string ToString() 47 { 48 return string.Format( 49 "Begin[{0}], End[{1}], Weight[{2}]", 50 Begin, End, Weight); 51 } 52 } 53 54 class Graph 55 { 56 private Dictionary<int, List<Edge>> _adjacentEdges 57 = new Dictionary<int, List<Edge>>(); 58 59 public Graph(int vertexCount) 60 { 61 this.VertexCount = vertexCount; 62 } 63 64 public int VertexCount { get; private set; } 65 66 public IEnumerable<int> Vertices { get { return _adjacentEdges.Keys; } } 67 68 public IEnumerable<Edge> Edges 69 { 70 get { return _adjacentEdges.Values.SelectMany(e => e); } 71 } 72 73 public int EdgeCount { get { return this.Edges.Count(); } } 74 75 public void AddEdge(int begin, int end, int weight) 76 { 77 if (!_adjacentEdges.ContainsKey(begin)) 78 { 79 var edges = new List<Edge>(); 80 _adjacentEdges.Add(begin, edges); 81 } 82 83 _adjacentEdges[begin].Add(new Edge(begin, end, weight)); 84 } 85 86 public bool HasCycle() 87 { 88 // mark all the vertices as not visited 89 // and not part of recursion stack 90 bool[] visited = new bool[VertexCount]; 91 bool[] recursionStack = new bool[VertexCount]; 92 for (int i = 0; i < VertexCount; i++) 93 { 94 visited[i] = false; 95 recursionStack[i] = false; 96 } 97 98 // call the recursive helper function to 99 // detect cycle in different DFS trees 100 for (int i = 0; i < VertexCount; i++) 101 if (CheckCyclic(i, visited, recursionStack)) 102 return true; 103 104 return false; 105 } 106 107 private bool CheckCyclic(int v, bool[] visited, bool[] recursionStack) 108 { 109 if (!visited[v]) 110 { 111 // mark the current node as visited 112 // and part of recursion stack 113 visited[v] = true; 114 recursionStack[v] = true; 115 116 // recur for all the vertices adjacent to this vertex 117 if (_adjacentEdges.ContainsKey(v)) 118 { 119 foreach (var edge in _adjacentEdges[v]) 120 { 121 if (!visited[edge.End] 122 && CheckCyclic(edge.End, visited, recursionStack)) 123 return true; 124 else if (recursionStack[edge.End]) 125 return true; 126 } 127 } 128 } 129 130 // remove the vertex from recursion stack 131 recursionStack[v] = false; 132 133 return false; 134 } 135 } 136 } 137 }
