如何检查有向图是否是非循环的？

Question

如何检查有向图是否是非循环的？算法如何调用？我很感激参考.

Answer 1

我会尝试在拓扑上对图进行排序,如果你不能,那么它有周期.

Answer 2

做一个简单的深度优先搜索不是不够好,找一个周期.可以在DFS中多次访问节点而不存在循环.根据您的起点,您也可能无法访问整个图表.

您可以按如下方式检查图形的连接组件中的循环.查找仅具有传出边的节点.如果没有这样的节点,那么就有一个循环.在该节点上启动DFS.遍历每条边时,检查边是否指向堆栈上已有的节点.这表明存在一个循环.如果没有找到此类边缘,则该连接组件中没有循环.

正如Rutger Prins指出的那样,如果您的图表未连接,则需要在每个连接的组件上重复搜索.

作为参考,Tarjan的强连通分量算法密切相关.它还可以帮助您找到周期,而不仅仅是报告它们是否存在.

Answer 3

本书Introduction to Algorithms(第二版)上的引理22.11 指出:

当且仅当G的深度优先搜索不产生后沿时,有向图G是非循环的

Answer 4

解决方案1:Kahn算法检查周期.主要思想:维护一个队列,其中具有零度的节点将被添加到队列中.然后逐个剥离节点,直到队列为空.检查是否存在任何节点的入边.

解决方案2:Tarjan算法检查强连通组件.

解决方案3:DFS.使用整数数组来标记节点的当前状态:即0 - 表示此节点之前未被访问过.-1 - 表示已访问此节点,并且正在访问其子节点.1 - 表示已访问此节点,并且已完成.因此,如果在执行DFS时节点的状态为-1,则意味着必须存在循环.

Answer 5

刚刚在谷歌面试中遇到了这个问题。

拓扑排序

您可以尝试按拓扑排序，即 O(V + E)，其中 V 是顶点数，E 是边数。当且仅当可以做到这一点时，有向图才是无环的。

递归叶子去除

递归地删除叶节点，直到没有剩下，如果剩下多个节点，则有一个循环。除非我弄错了，否则这是 O(V^2 + VE)。

DFS 式 ~ O(n + m)

然而，一种高效的 DFS 式算法，最坏情况 O(V + E) 是：

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(node) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}