有没有一种有效的算法来检测有向图中的循环?
我有一个有向图,表示需要执行的作业计划,作业是一个节点,依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。
有没有一种有效的算法来检测有向图中的循环?
我有一个有向图,表示需要执行的作业计划,作业是一个节点,依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。
当前回答
我的方法是做一个拓扑排序,计算访问顶点的数量。如果这个数字小于DAG中的顶点总数,那么就有一个循环。
其他回答
Tarjan的强连通分量算法的时间复杂度为O(|E| + |V|)。
有关其他算法,请参见维基百科上的强连接组件。
我的方法是做一个拓扑排序,计算访问顶点的数量。如果这个数字小于DAG中的顶点总数,那么就有一个循环。
最简单的方法是对图进行深度优先遍历(DFT)。
如果图有n个顶点,这是一个O(n)时间复杂度算法。因为你可能必须从每个顶点开始进行DFT,所以总复杂度变成O(n^2)。
您必须维护一个包含当前深度第一次遍历的所有顶点的堆栈,其第一个元素是根节点。如果在DFT期间遇到一个元素已经在堆栈中,那么就有一个循环。
根据Cormen et al., Introduction to Algorithms (CLRS)引理22.11:
有向图G是无环的当且仅当深度优先搜索G没有得到后边。
在几个回答中已经提到了这一点;在这里,我还将提供一个基于CLRS第22章的代码示例。示例图如下所示。
CLRS深度优先搜索的伪代码如下:
在CLRS图22.4中的示例中,图由两棵DFS树组成:一棵由节点u、v、x和y组成,另一棵由节点w和z组成。每棵树都包含一条后边:一条从x到v,另一条从z到z(一个自循环)。
关键的实现是,在DFS-VISIT函数中,当在u的邻居v上迭代时,遇到一个带有灰色的节点时,就会遇到后边缘。
下面的Python代码是CLRS伪代码的改编,添加了一个if子句,用于检测周期:
import collections
class Graph(object):
def __init__(self, edges):
self.edges = edges
self.adj = Graph._build_adjacency_list(edges)
@staticmethod
def _build_adjacency_list(edges):
adj = collections.defaultdict(list)
for edge in edges:
adj[edge[0]].append(edge[1])
adj[edge[1]] # side effect only
return adj
def dfs(G):
discovered = set()
finished = set()
for u in G.adj:
if u not in discovered and u not in finished:
discovered, finished = dfs_visit(G, u, discovered, finished)
def dfs_visit(G, u, discovered, finished):
discovered.add(u)
for v in G.adj[u]:
# Detect cycles
if v in discovered:
print(f"Cycle detected: found a back edge from {u} to {v}.")
break
# Recurse into DFS tree
if v not in finished:
dfs_visit(G, v, discovered, finished)
discovered.remove(u)
finished.add(u)
return discovered, finished
if __name__ == "__main__":
G = Graph([
('u', 'v'),
('u', 'x'),
('v', 'y'),
('w', 'y'),
('w', 'z'),
('x', 'v'),
('y', 'x'),
('z', 'z')])
dfs(G)
注意,在本例中,CLRS伪代码中的时间没有被捕获,因为我们只对检测周期感兴趣。还有一些样板代码,用于从边列表构建图的邻接表表示。
当这个脚本执行时,它输出如下:
Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.
这些正是CLRS图22.4示例中的后边缘。
在我看来,在有向图中检测周期最容易理解的算法是图着色算法。
基本上,图着色算法以DFS方式(深度优先搜索,这意味着它在探索另一条路径之前完全探索一条路径)遍历图。当它找到后边缘时,它将图形标记为包含循环。
有关图着色算法的深入解释,请阅读这篇文章:http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外,我在JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js中提供了一个图形着色的实现