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

StackOverflow https://stackoverflow.com/questions/261573

题

检测有向图中所有周期的最有效算法是什么？

我有一个有向图，表示需要执行的作业计划，作业是节点，依赖是边缘。我需要检测此图中循环的错误情况，从而导致循环依赖。

有帮助吗？

解决方案

Tarjan的强连接组件算法具有 O（| E | + | V |）时间复杂度。

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

其他提示

鉴于这是一份工作计划，我怀疑在某些时候你会将它们排序成为一个建议的执行顺序。

如果是这种情况，则 拓扑排序 实施可能在任何情况下检测周期。 UNIX tsort 当然可以。因此，我认为在tsorting的同时检测周期更有效，而不是单独一步。

因此，问题可能变成“我如何最有效地进行切割”，而不是“如何最有效地检测循环”。答案可能是“使用图书馆”，但未通过以下维基百科文章：

  

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

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

从DFS开始：当且仅当在DFS 期间发现后沿时，才存在循环。这被证明是白路理论的结果。

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

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

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

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

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

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

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

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

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

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

虽然这似乎具有O（N * M）的复杂性，但您必须记住堆栈的深度非常有限（因此N很小）并且M变得更小，每个依赖关系都可以检查为“ ;执行＆QUOT;另外，你可以在找到一片叶子时停止搜索（所以从不必须检查每个节点 - ＆gt; M也会很小）。

在MetaMake中，我将图形创建为列表列表，然后在执行时删除每个节点，这自然会减少搜索量。我从来没有必要进行独立检查，这一切都是在正常执行期间自动发生的。

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

没有算法可以在多项式时间内找到有向图中的所有周期。假设有向图有n个节点，每对节点都有相互连接，这意味着你有一个完整的图。因此，这n个节点的任何非空子集指示一个周期，并且存在2 ^ n-1个这样的子集。因此不存在多项式时间算法。     因此，假设您有一个有效的（非愚蠢的）算法，它可以告诉您图中的定向循环数，您可以先找到强连接组件，然后在这些连接的组件上应用算法。由于循环仅存在于组件中而不存在于它们之间。

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

根据 Cormen et al。，算法导论 （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])
        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 discovered and 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中示例的后沿。

我这样做的方法是进行拓扑排序，计算所访问的顶点数。如果该数字小于DAG中的顶点总数，则表示您有一个循环。

我在sml中实现了这个问题（命令式编程）。这是大纲。找到具有0的indegree或outdegree的所有节点。这样的节点不能是循环的一部分（因此删除它们）。接下来，从这些节点中删除所有传入或传出边缘。 递归地将此过程应用于结果图。如果最后你没有留下任何节点或边缘，那么图表没有任何周期，否则就有。

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

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

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

如果图表满足此属性

|e| > |v| - 1

然后图表至少包含循环。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top