检测有向图中循环的最佳算法

Question

有没有一种高效的算法可以检测有向图中的循环？

我有一个表示需要执行的作业安排的有向图，其中作业是节点，依赖关系是边。我需要检测出图中存在循环依赖导致错误的情况。

- Peauters

---

你说你想要检测所有的循环，但是你的应用场景表明只需要检测是否存在任何循环即可。 - Steve Jessop

最好检测出所有的循环，这样可以一次性修复，而不是检查、修复、检查、修复等。 - Peauters

你应该阅读Donald B. Johnson的论文《寻找有向图中的所有基本电路》。它将仅找到基本电路，但这对你的情况应该足够了。这是我实现该算法的Java代码，可以直接使用：https://github.com/1123/johnson - user152468

运行DFS算法，对其进行额外修改：标记您访问的每个节点。如果您访问已经被访问过的节点，则说明存在环。当您从路径撤退时，请取消标记已访问的节点。 - Hesham Yassin

@HeshamYassin，如果你访问了一个已经访问过的节点，并不一定意味着出现了循环。请阅读我的评论http://cs.stackexchange.com/questions/9676/the-purpose-of-grey-node-in-graph-depth-first-search#comment140072_9681。 - Maksim Dmitriev

Answer 1

塔杨强连通分量算法（Tarjan's strongly connected components algorithm）的时间复杂度为O(|E| + |V|)。

其他相关算法请参见维基百科上的强连通分量。

- aku

---

寻找强连通分量如何告诉你关于图中存在的循环？ - Peter

或许有人可以确认，但Tarjan算法不支持节点直接指向自身的循环，例如A->A。 - Cédric Guillemette

@Cedrik 对的，不是直接找到环。这并不是Tarjan算法的缺陷，而是在本题中使用该算法的方式。Tarjan算法并不直接找到环，它找到的是强连通分量（SCC）。当然，任何具有大于1个大小的SCC都意味着存在一个环。非循环组件自己拥有单例SCC。问题在于自环也会单独进入SCC。因此，您需要针对自环进行单独检查，这是非常简单的。 - mgiuca

所有强连通分量并不等同于图中的所有环。 - optimusfrenk

一个三色DFS也具有相同的运行时间'O（|E|+|V|）'。使用白色（从未访问过），灰色（当前节点已被访问，但所有可达节点尚未被访问）和黑色（所有可达节点都已经访问，并包括当前节点）着色编码，如果一个灰色节点发现另一个灰色节点，则我们有一个环。（与Cormen算法书中描述的差不多）。想知道“Tarjan算法”是否比这种DFS更有优势！！ - KGhatak

Answer 2

鉴于这是一个作业列表，我猜测你最终会将它们排序成一个执行顺序的建议。

如果是这样的话，那么实现拓扑排序可能在任何情况下检测到循环。UNIX tsort肯定会检测到。因此，最好同时检测循环和对任务进行排序，而不是分开进行。

所以问题可能变成了“如何最有效地进行拓扑排序”，而不是“如何最有效地检测循环”。答案可能是“使用库”，但如果没有，可以参考以下维基百科文章：

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

其中包含一种算法的伪代码以及Tarjan的另一种算法的简要描述。两种算法的时间复杂度均为O（| V | + | E |）。

- onebyone.livejournal.com

---

拓扑排序可以检测循环，因为它依赖于深度优先搜索算法，但您需要额外的记录来实际检测循环。请参见Kurt Peek的正确答案。 - Luke Hutchison

Answer 3

根据Cormen et al.，《算法导论》（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])
            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中示例的反向边。

- Kurt Peek

---

我在这段代码中遇到了“RecursionError: maximum recursion depth exceeded while calling a Python object”的错误。 - zino

看起来在检测到循环后应该加上一个“break”。我尝试添加它，但编辑队列已满。 - A_P

提示：discovered, finished = dfs_visit(G, u, discovered, finished) 可以替换为：dfs_visit(G, u, discovered, finished)，并且 dfs-visit 可以返回 None。 - Sanandrea

@zino @A_P 我编辑了这个示例，在检测到循环后添加了缺失的 break 语句。 - Christian Long

然而，在其他图上运行时，我得到了RuntimeError: dictionary changed size during iteration。这是因为G.adj是一个默认字典，并且在for v in G.adj[u]中的查找正在添加它。 - Christian Long

@ChristianLong 在 _build_adjacency_list 的 for 循环中添加对 adj[edge[1]] 的调用，这将初始化节点的键，这些节点在至少某个边缘中不出现为 edge[0]（通常发生在没有循环的图形中）（刚刚添加到答案中）。 - Jthorpe

Answer 4

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

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

您必须维护一个包含当前深度优先遍历中所有顶点的堆栈，其第一个元素为根节点。如果在DFT期间遇到已经在堆栈中的元素，则表示存在环。

- phys wizard

---

这对于“常规”的图形是正确的，但对于有向图则不是。例如，考虑具有四个节点的“菱形依赖图”：A与指向B和C的边缘相连，每个B和C都有一条指向D的边缘。从A开始的深度优先遍历会错误地得出这个“循环”实际上是一个环 - 尽管存在一个循环，但它不是一个环，因为不能通过按箭头遵循路径来遍历它。 - Peter

Peter，请问能否解释一下从A开始的DFT如何错误地得出存在循环的结论？ - Deepak

@Deepak - 事实上，我误读了“phys wizard”的回答：他写的“in the stack”，我理解成“已经被找到了”。实际上，在执行深度优先遍历（DFT）期间，仅需检查“堆栈中”的重复项就足以检测有向循环。给你们每个人点赞。 - Peter

为什么你说时间复杂度是 O(n)，同时建议检查堆栈以查看它是否已包含访问过的节点？扫描堆栈会增加 O(n) 运行时的时间，因为它必须在每个新节点上扫描堆栈。如果标记节点已访问，则可以实现 O(n)。 - James Wierzba

正如Peter所说，这对于有向图来说是不完整的。请参考Kurt Peek的正确答案。 - Luke Hutchison

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

- Armin Primadi

Answer 6

从DFS开始：当且仅当在DFS过程中发现反向边时，存在一个环。这是白路径定理的结果。

- Ajay Garg

---

好的，我会尽力进行翻译。下面是需要翻译的内容：Yes, i think the same, but this isn't enough, I post my way cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph - Jonathan Prieto-Cubides

真的。Ajay Garg只是在讲述如何找到“一个循环”，这是该问题的部分答案。您提供的链接涉及根据所提出的问题查找所有循环，但似乎它使用了与Ajay Garg相同的方法，但也执行了所有可能的dfs-trees。 - Manohar Reddy Poreddy

这对于有向图来说是不完整的。请参考Kurt Peek的正确答案。 - Luke Hutchison

它并不回答问题，问题是要求解决方案以找到所有循环。 - sia

Answer 7

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

这还可以为您提供关于循环依赖的“根”节点的信息，在用户需要修复问题时非常有用。

另一个解决方案是尝试查找要执行的下一个依赖项。为此，必须有一些堆栈，可以记住当前位置和下一步需要执行的操作。在执行之前检查依赖项是否已在此堆栈上，如果是，则找到了一个循环。

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

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

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

- Aaron Digulla

Answer 8

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

- Yuwen

---

如果将节点数视为输入大小，则返回True。您还可以根据边数甚至循环次数或这些度量的组合来描述运行时复杂性。Donald B. Johnson的算法“查找有向图的所有基本电路”具有多项式运行时间，其时间复杂度为O（（n + e）（c + 1）），其中n是节点数，e是边数，c是图的基本电路数。这是我实现该算法的Java代码：https://github.com/1123/johnson。 - user152468

Answer 9

我曾经用sml（命令式编程）实现过这个问题。以下是大纲：找到所有入度或出度为0的节点，这些节点不能成为循环的一部分（因此要删除它们）。接下来删除这些节点的所有入边或出边。然后递归地将此过程应用于结果图。如果最终没有留下任何节点或边，则该图没有任何循环；否则就存在循环。

- Rpant

Answer 10

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

此外，物理巫师说你必须执行O（V ^ 2）。我相信我们只需要O（V）/ O（V + E）即可。

如果图是连通的，则DFS将访问所有节点。如果图具有连接的子图，则每次在该子图的顶点上运行DFS时，我们将找到已连接的顶点，并且不必考虑下一次运行DFS时的这些顶点。 因此，为每个顶点运行的可能性是不正确的。

- amitgoswami