首页 > 代码库 > 深度优先搜索检测有向图有无环路算法
深度优先搜索检测有向图有无环路算法
给定有向图 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 trees100 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 stack113 visited[v] = true;114 recursionStack[v] = true;115 116 // recur for all the vertices adjacent to this vertex117 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 stack131 recursionStack[v] = false;132 133 return false;134 }135 }136 }137 }
本篇文章《DFS 检测有向图有无环算法》由 Dennis Gao 发表自博客园，未经作者本人同意禁止任何形式的转载，任何自动或人为的爬虫转载行为均为耍流氓。
深度优先搜索检测有向图有无环路算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。