如何检查有向图是否是非循环的？

如何检查有向图是否是非循环的？ algorithm如何被调用？ 我将不胜感激参考。

我会尝试sorting图拓扑 ，如果你不能，那么它有周期。

做一个简单的深度优先search不足以find一个循环。 可以在DFS中多次访问节点而不存在循环。 根据你开始的地方，你也可能不会访问整个图表。

您可以按照以下方式检查graphics的连接组件中的周期。 find只有传出边的节点。 如果没有这样的节点，那么就有一个循环。 在该节点启动DFS。 遍历每个边时，检查边是否指向已经在堆栈中的节点。 这表明存在一个循环。 如果您发现没有这样的边缘，那么连接的组件中就没有循环。

正如Rutger Prins所指出的那样，如果你的图表没有连接，你需要在每个连接的组件上重复search。

作为参考， Tarjan的强连通分量algorithm是密切相关的。 它也将帮助你find周期，而不仅仅是报告它们是否存在。

关于Introduction to Algorithms （第二版）的引理22.11指出：

当且仅当G的深度优先search不产生后沿时，有向图G是非循环的

解决scheme1 ： Kahnalgorithm来检查周期 。 主要思想：维护一个队列，将零度入节点join队列。 然后逐个剥离节点，直到队列为空。 检查是否存在任何节点的入边。

解决scheme2 ：检查强连接组件的Tarjanalgorithm 。

解决scheme3 ： DFS 。 使用整数数组标记节点的当前状态：即0 – 表示此节点之前没有被访问过。 -1表示该节点已被访问，其子节点正在访问。 1 – 表示这个节点已经被访问，并且已经完成。 所以如果在做DFS时节点的状态是-1，就意味着必须有一个循环存在。

ShuggyCoUk给出的解决scheme是不完整的，因为它可能不检查所有节点。 

 def isDAG(nodes V): while there is an unvisited node v in V: bool cycleFound = dfs(v) if cyclefound: return false return true

这具有时间复杂性O（n + m）或O（n ^ 2）

我知道这是一个古老的话题，但对于未来的search者来说，这里是我创build的C＃实现（不要求它是最有效的！）。 这被devise成使用简单的整数来标识每个节点。 你可以装饰，但是你喜欢提供你的节点对象散列和等于正确。

对于非常深的图，这可能会有很高的开销，因为它会在每个节点深度创build一个哈希集（它们在广度上被破坏）。

您input要从中search的节点，并将path带到该节点。

  • 对于具有单个根节点的图，您可以发送该节点和一个空的哈希集
  • 对于具有多个根节点的图，您可以在foreach中将其包装在这些节点上，并为每个迭代传递一个新的空hashset

  • 在检查给定节点下面的周期时，只需将该节点与空的哈希集一起传递 

     private bool FindCycle(int node, HashSet<int> path) { if (path.Contains(node)) return true; var extendedPath = new HashSet<int>(path) {node}; foreach (var child in GetChildren(node)) { if (FindCycle(child, extendedPath)) return true; } return false; }

在做DFS的时候，不应该有任何后台边缘。在做DFS的时候保持已经访问过的节点的轨迹，如果遇到当前节点和现有节点之间的边缘，那么graphics就有循环。

这里是一个快速的代码来查找graphics是否有循环： 

 func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool { if(breadCrumb[root] == true) { return true; } if(visited[root] == true) { return false; } visited[root] = true; breadCrumb[root] = true; if(G[root] != nil) { for child : Int in G[root]! { if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb)) { return true; } } } breadCrumb[root] = false; return false; } let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]]; var visited = [false,false,false,false,false,false,false,false,false]; var breadCrumb = [false,false,false,false,false,false,false,false,false]; var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

这个想法是这样的：一个正常的dfsalgorithm，带有一个数组来跟踪访问节点，以及一个附加数组作为通往当前节点的节点的标记，这样当我们为一个节点执行一个dfs我们在标记数组中将相应的项目设置为true，这样当遇到已经访问过的节点时，我们检查它在标记数组中的相应项是否为真，如果它是真的，那么它是让它自己的一个节点循环），诀窍是每当一个节点的dfs返回时，我们将其相应的标记设置为false，所以如果我们从另一个path再次访问它，我们不会被愚弄。

这里是我的ruby实现剥离叶节点algorithm 。 

 def detect_cycles(initial_graph, number_of_iterations=-1) # If we keep peeling off leaf nodes, one of two things will happen # A) We will eventually peel off all nodes: The graph is acyclic. # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic. graph = initial_graph iteration = 0 loop do iteration += 1 if number_of_iterations > 0 && iteration > number_of_iterations raise "prevented infinite loop" end if graph.nodes.empty? #puts "the graph is without cycles" return false end leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? } if leaf_nodes.empty? #puts "the graph contain cycles" return true end nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) } edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) } graph = Graph.new(nodes2, edges2) end raise "should not happen" end
Interesting Posts