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

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

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

Tarjan的强连通组件算法具有O(|E| + |V|)时间复杂性.

对于其他算法,请参阅Wikipedia上的强连接组件.

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

如果是这种情况,那么拓扑排序实现可以在任何情况下检测周期.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变小,每个依赖关系都可以检查为"已执行"加上当你找到一片叶子时你可以停止搜索(所以你永远不必检查每个节点 - > M也会很小).

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

如果您需要"仅测试"模式,只需添加一个"干运行"标志,该标志禁用实际作业的执行.

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

根据Cormen等人的引理22.11，算法简介（CLRS）：

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)

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