在有向图中检测周期的最佳算法

小开

最佳答案

Tarjan的强连接分量算法具有O(|E| + |V|)时间复杂度。

关于其他算法，请参见维基百科上的强连接组件。

小开

鉴于这是一个作业计划，我怀疑在某些时候你会排序它们到建议的执行顺序中。

如果是这种情况，那么< em >拓扑排序< / em >实现在任何情况下都可以检测周期。UNIX tsort当然可以。因此，我认为在三步排序的同时检测循环比在单独的步骤中检测更有效。

因此，问题可能变成“我如何最有效地进行tsort”，而不是“我如何最有效地检测循环”。答案可能是“使用图书馆”，但如果没有下面的维基百科文章:

http://en.wikipedia.org/wiki/Topological_sorting

有一种算法的伪代码，以及来自Tarjan的另一种算法的简要描述。两者都具有O(|V| + |E|)时间复杂度。

小开

如果你不能给节点添加一个“被访问过”的属性，使用一个集合(或者映射)，把所有被访问过的节点添加到集合中，除非它们已经在集合中。使用唯一的键或对象的地址作为“键”。

这还为您提供了关于循环依赖项的“根”节点的信息，当用户必须修复问题时，这些信息将派上用场。

另一个解决方案是尝试找到下一个要执行的依赖项。为此，您必须有一个可以记住您现在在哪里以及接下来需要做什么的堆栈。在执行依赖项之前，检查它是否已经在此堆栈上。如果是，你就找到了一个循环。

虽然这看起来可能有O(N*M)的复杂性，但你必须记住，堆栈的深度非常有限(所以N很小)，而且M随着你可以检查为“已执行”的每个依赖项而变小，加上你可以在找到叶子时停止搜索(所以你从来没有必须检查每个节点-> M也会很小)。

在MetaMake中，我将图表创建为列表列表，然后在执行它们时删除每个节点，这自然地减少了搜索量。实际上，我从来不需要运行一个独立的检查，这一切都是在正常执行过程中自动发生的。

如果你需要一个“仅测试”模式，只需添加一个“干运行”标志，它禁止实际作业的执行。

小开

我的方法是做一个拓扑排序，计算访问顶点的数量。如果这个数字小于DAG中的顶点总数，那么就有一个循环。

小开

最简单的方法是对图进行深度优先遍历(DFT)。

如果图有n个顶点，这是一个O(n)时间复杂度算法。因为你可能必须从每个顶点开始进行DFT，所以总复杂度变成O(n^2)。

你必须维护一个堆栈中包含当前深度第一次遍历的所有顶点，它的第一个元素是根节点。如果在DFT期间遇到一个元素已经在堆栈中，那么就有一个循环。

小开

如果一个图满足这个性质

|e| > |v| - 1

那么图至少包含一个周期。

小开

从DFS开始:循环存在时且仅当在DFS期间发现后边缘. d这是白径定理的结果。

小开

我已经在sml(命令式编程)中实现了这个问题。这是大纲。找到所有入度或出度为0的节点。这样的节点不能成为循环的一部分(因此将它们删除)。接下来，从这些节点中删除所有传入或传出边。递归地将此过程应用于结果图。如果在最后你没有剩下任何节点或边，图就没有任何循环，否则它有

小开

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我最喜欢这个解决方案，特别是4个长度:)

phys向导还说你必须做O(V^2)。我相信我们只需要O(V)/O(V+E)。如果图是连通的，那么DFS将访问所有节点。如果图有连通的子图，那么每次我们在这个子图的顶点上运行DFS时，我们都会找到连通的顶点，并且不必为下一次运行DFS考虑这些。因此，对每个顶点运行的可能性是不正确的

小开

没有一种算法能在多项式时间内找到有向图中的所有循环。假设有向图有n个节点每对节点之间都有连接这意味着你有一个完整的图。所以这n个节点的任何非空子集都表示一个周期并且有2^n-1个这样的子集。所以不存在多项式时间算法。所以假设你有一个有效的(非愚蠢的)算法，它可以告诉你图中有向循环的数量，你可以首先找到强连通分量，然后将你的算法应用到这些连通分量上。因为循环只存在于组件内部，而不存在于组件之间

小开

如果DFS发现一条边指向一个已经访问过的顶点，那么这里就有一个循环。

小开

在我看来，在有向图中检测周期最容易理解的算法是图着色算法。

基本上，图着色算法以DFS方式(深度优先搜索，这意味着它在探索另一条路径之前完全探索一条路径)遍历图。当它找到后边缘时，它将图形标记为包含循环。

有关图着色算法的深入解释，请阅读这篇文章:http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

另外，我在JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js中提供了一个图形着色的实现

小开

正如你所说，你有一组作业，它需要按一定的顺序执行。Topological sort给出了作业调度所需的顺序(如果是direct acyclic graph，则用于解决依赖问题)。运行dfs并维护一个列表，并在列表的开头开始添加node，如果您遇到一个已经访问过的节点。然后在给定的图中找到一个循环。

小开

根据Cormen等，算法介绍 (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时，遇到一个带有GRAY颜色的节点时，会遇到后边。

下面的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])
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伪代码中的time没有被捕获，因为我们只对检测周期感兴趣。还有一些样板代码，用于从边列表构建图的邻接表表示。

当这个脚本执行时，它输出如下:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

这些正是CLRS图22.4示例中的后边缘。