用于检测有向图中循环的有效算法

Question

是否有一种有效的算法来检测有向图中的循环？

我有一个有向图，表示需要执行的作业的时间表，作业是节点，依赖项是边。 我需要检测该图中导致循环依赖的循环错误情况。

最好检测所有周期，以便一次性修复它们。

Answer 1

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

对于其他算法，请参阅 Wikipedia 上的强连通分量。

Answer 2

鉴于这是一个作业计划，我怀疑在某个时候您会将它们按建议的执行顺序进行排序。

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

因此，问题可能会变成“如何最有效地进行排序”，而不是“如何最有效地检测循环”。 答案可能是“使用库”，但以下维基百科文章却未能做到这一点：

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

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

Answer 3

根据Cormen 等人，算法简介 (CLRS)：

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

执行此脚本时，它会打印以下输出：

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

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

Answer 4

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

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

您必须维护一个包含当前深度优先遍历中所有顶点的堆栈，其中第一个元素是根节点。 如果在 DFT 过程中遇到一个已经在堆栈中的元素，那么就会出现循环。

Answer 5

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

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

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

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

Answer 6

从 DFS 开始：当且仅当在 DFS 期间发现后沿时，循环才存在。 这由白路定理得到证明。

Answer 7

如果无法向节点添加“已访问”属性，请使用集合（或映射）并将所有已访问节点添加到集合中，除非它们已经在集合中。 使用唯一的键或对象的地址作为“键”。

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

另一种解决方案是尝试找到下一个要执行的依赖项。 为此，您必须有一些堆栈，可以让您记住您现在所在的位置以及下一步需要做什么。 在执行之前检查依赖项是否已在此堆栈上。 如果是的话，你就找到了一个循环。

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

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

如果您需要“仅测试”模式，只需添加一个“空运行”标志即可禁用实际作业的执行。

Answer 8

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

Answer 9

我已经在 sml （命令式编程）中实现了这个问题。 这是概要。 查找所有入度或出度为 0 的节点。 这些节点不能成为循环的一部分（因此将其删除）。 接下来删除这些节点的所有传入或传出边。
将此过程递归地应用于结果图。 如果最后没有留下任何节点或边，则该图没有任何循环，否则它有。

Answer 10

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

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

Answer 11

我这样做的方法是进行拓扑排序，计算访问的顶点数量。 如果该数字小于 DAG 中的顶点总数，则存在循环。

Answer 12

正如您所说，您有一组作业，需要按一定顺序执行。 拓扑排序为您提供了作业调度所需的顺序（或者如果是直接无环图，则用于依赖性问题）。 运行 dfs 并维护一个列表，并开始在列表的开头添加节点，如果遇到已经访问过的节点。 然后你在给定的图中找到了一个循环。

Answer 13

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

Answer 14

如果一个图满足这个属性

|e| > |v| - 1

，那么该图至少包含一个循环。