有没有一种有效的算法来检测有向图中的循环?

我有一个有向图,表示需要执行的作业计划,作业是一个节点,依赖项是一个边。我需要检测这个图中导致循环依赖关系的循环的错误情况。


当前回答

从DFS开始:当且仅当DFS期间发现后边缘时,循环存在。这是白径定理的结果。

其他回答

如果你不能给节点添加一个“被访问过”的属性,使用一个集合(或者映射),把所有被访问过的节点添加到集合中,除非它们已经在集合中。使用唯一的键或对象的地址作为“键”。

这还为您提供了关于循环依赖项的“根”节点的信息,当用户必须修复问题时,这些信息将派上用场。

另一个解决方案是尝试找到下一个要执行的依赖项。为此,您必须有一个可以记住您现在在哪里以及接下来需要做什么的堆栈。在执行依赖项之前,检查它是否已经在此堆栈上。如果是,你就找到了一个循环。

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

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

如果你需要一个“仅测试”模式,只需添加一个“干运行”标志,它禁止实际作业的执行。

我的方法是做一个拓扑排序,计算访问顶点的数量。如果这个数字小于DAG中的顶点总数,那么就有一个循环。

根据Cormen et al., Introduction to Algorithms (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上迭代时,遇到一个带有灰色的节点时,就会遇到后边缘。

下面的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伪代码中的时间没有被捕获,因为我们只对检测周期感兴趣。还有一些样板代码,用于从边列表构建图的邻接表表示。

当这个脚本执行时,它输出如下:

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

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

There is no algorithm which can find all the cycles in a directed graph in polynomial time. Suppose, the directed graph has n nodes and every pair of the nodes has connections to each other which means you have a complete graph. So any non-empty subset of these n nodes indicates a cycle and there are 2^n-1 number of such subsets. So no polynomial time algorithm exists. So suppose you have an efficient (non-stupid) algorithm which can tell you the number of directed cycles in a graph, you can first find the strong connected components, then applying your algorithm on these connected components. Since cycles only exist within the components and not between them.

如果一个图满足这个性质

|e| > |v| - 1

那么图至少包含一个周期。