是否有一种有效的算法来检测有向图中的循环？
我有一个有向图，表示需要执行的作业计划，作业是节点，依赖项是边。我需要在该图中检测导致循环依赖的循环错误情况。
Peauters
问问题
358694 次
14 回答
205
Tarjan 的强连通分量算法具有O(|E| + |V|)时间复杂度。
有关其他算法，请参阅Wikipedia 上的强连接组件。
于 2008-11-04T11:35:04.593 回答
81
鉴于这是一个作业时间表，我怀疑在某些时候您会将它们分类为建议的执行顺序。
如果是这种情况，那么拓扑排序实现无论如何都可以检测循环。UNIXtsort当然可以。我认为因此在 tsorting 的同时检测周期可能比在单独的步骤中更有效。
所以问题可能变成“我如何最有效地进行排序”，而不是“我如何最有效地检测循环”。答案可能是“使用图书馆”，但没有以下维基百科文章：
有一种算法的伪代码，以及来自 Tarjan 的另一种算法的简要描述。两者都有O(|V| + |E|)时间复杂度。
于 2008-11-04T11:50:46.980 回答
54
根据Cormen 等人的引理 22.11，算法简介(CLRS)：
有向图 G 是非循环的当且仅当 G 的深度优先搜索不产生后边。
这已经在几个答案中提到过；这里我还将提供一个基于 CLRS 第 22 章的代码示例。示例图如下所示。
CLRS 的深度优先搜索伪代码如下：
在 CLRS 图 22.4 的示例中，该图由两棵 DFS 树组成：一棵由节点u、v、x和y组成，另一棵由节点w和z组成。每棵树都包含一个后边：一个从x到v，另一个从z到z（自循环）。
DFS-VISIT关键实现是，当在函数中迭代 的邻居v时u遇到带有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}.")
# 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)
请注意，在此示例中，time未捕获 CLRS 的伪代码，因为我们只对检测周期感兴趣。还有一些样板代码用于从边列表构建图的邻接表表示。
执行此脚本时，它会打印以下输出：
Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.
这些正是 CLRS 图 22.4 示例中的后边缘。
于 2019-01-01T13:02:03.033 回答
35
最简单的方法是对图进行深度优先遍历（DFT）。
如果图有n顶点，这是一种O(n)时间复杂度算法。由于您可能必须从每个顶点开始进行 DFT，因此总复杂度变为O(n^2).
您必须维护一个包含当前深度优先遍历中所有顶点的堆栈，其第一个元素是根节点。如果你在 DFT 期间遇到一个已经在堆栈中的元素，那么你就有了一个循环。
于 2009-04-21T01:14:14.680 回答
32
在我看来，在有向图中检测循环最容易理解的算法是图形着色算法。
基本上，图着色算法以 DFS 方式遍历图（深度优先搜索，这意味着它在探索另一条路径之前完全探索一条路径）。当它找到一个后边时，它将图形标记为包含一个循环。
有关图形着色算法的深入解释，请阅读本文：http ://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
另外，我在 JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js中提供了图形着色的实现
于 2016-05-26T08:16:56.627 回答
29
从 DFS 开始：当且仅当在 DFS 期间发现后沿时才存在循环。这是白路径定理的结果。
于 2010-12-30T20:02:16.603 回答
9
如果您无法向节点添加“已访问”属性，请使用集合（或映射）并将所有已访问节点添加到集合中，除非它们已经在集合中。使用唯一键或对象的地址作为“键”。
这也为您提供了有关循环依赖项的“根”节点的信息，当用户必须解决问题时，这些信息将派上用场。
另一种解决方案是尝试找到下一个要执行的依赖项。为此，您必须有一些堆栈，您可以记住您现在在哪里以及接下来需要做什么。在执行之前检查依赖项是否已经在此堆栈上。如果是，你已经找到了一个循环。
虽然这似乎具有 O(N*M) 的复杂性，但您必须记住，堆栈的深度非常有限（因此 N 很小），并且 M 会随着您可以检查为“已执行”的每个依赖项而变小加上您可以在找到叶子时停止搜索（因此您不必检查每个节点 -> M 也会很小）。
在 MetaMake 中，我将图表创建为列表列表，然后在执行它们时删除每个节点，这自然会减少搜索量。我实际上从来不需要运行独立检查，这一切都是在正常执行期间自动发生的。
如果您需要“仅测试”模式，只需添加一个“空运行”标志即可禁用实际作业的执行。
于 2008-11-04T12:15:46.370 回答
7
没有一种算法可以在多项式时间内找到有向图中的所有循环。假设有向图有 n 个节点，每对节点之间都有连接，这意味着你有一个完整的图。因此，这 n 个节点的任何非空子集都表示一个循环，并且有 2^n-1 个这样的子集。所以不存在多项式时间算法。因此，假设您有一个高效（非愚蠢）算法，可以告诉您图中有向循环的数量，您可以首先找到强连通分量，然后将您的算法应用于这些连通分量。因为循环只存在于组件内而不存在于它们之间。
于 2013-04-13T03:30:12.347 回答
4
我已经在 sml（命令式编程）中实现了这个问题。这是大纲。查找入度或出度为 0 的所有节点。这样的节点不能成为循环的一部分（所以删除它们）。接下来从这些节点中删除所有传入或传出边。递归地将此过程应用于结果图。如果最后您没有留下任何节点或边，则该图没有任何环，否则它有。
于 2013-01-24T01:49:29.213 回答
2
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length我最喜欢这个解决方案，特别适合 4 长度:)
物理向导也说你必须做 O(V^2)。我相信我们只需要 O(V)/O(V+E)。如果图是连接的，那么 DFS 将访问所有节点。如果该图具有连接的子图，那么每次我们在该子图的顶点上运行 DFS 时，我们都会找到连接的顶点，并且不必在下一次运行 DFS 时考虑这些。因此，为每个顶点运行的可能性是不正确的。
于 2013-02-16T12:05:38.397 回答
1
我这样做的方法是进行拓扑排序，计算访问的顶点数。如果该数字小于 DAG 中的顶点总数，则您有一个循环。
于 2008-11-04T13:35:57.050 回答
0
如果 DFS 找到指向已经访问过的顶点的边，则那里有一个循环。
于 2013-05-12T07:16:29.210 回答
0
正如你所说，你有一套工作，它需要按一定的顺序执行。Topological sort给定您安排作业所需的顺序（或者如果是 a ，则用于依赖性问题direct acyclic graph）。运行dfs并维护一个列表，并开始在列表的开头添加节点，如果遇到已经访问过的节点。然后你在给定的图中找到了一个循环。
于 2017-04-12T05:48:45.427 回答
-12
如果一个图满足这个性质
|e| > |v| - 1
那么该图至少包含一个循环。
于 2010-10-28T10:33:15.100 回答