algorithm - 检测图中循环的最快算法

Question

给定一个无向图，检测它是否包含循环的最佳算法是什么？

在跟踪访问节点的同时进行广度优先或深度优先搜索是一种方法，但它是 O(n^2)。有什么更快的吗？

score 6 · Accepted Answer

给定图 G(V,E) 的 BFS 和 DFS 算法的时间复杂度为 O(|V|+|E|)。所以你可以看到它是输入的线性依赖。如果您有非常专业的图，您可以执行一些启发式方法，但通常使用 DFS 并没有那么糟糕。您可以在此处查看一些信息。无论如何，您必须遍历整个图表。

score 4 · Accepted Answer

这是你的O(V)算法：

def hasCycles(G, V, E): 
    if E>=V:
        return True
    else:
        # here E<V
        # perform O(E+V) = O(V) algorithm 
        ...

... 可以使用 DFS 执行。如果你有E<V并且边缘以有意义的方式存储（作为列表），你可能会做 O(E)+logs 这将使整个算法O(min(E,V))+logs。

希望你喜欢这个答案，虽然有点晚了！

score 1 · Accepted Answer

如果使用邻接表表示图，则使用深度优先搜索测试图 G(V,E) 中是否存在循环是 O(|V|,|E|)。

有必要遍历整个图以显示没有循环。如果您只是对循环的存在/不存在感兴趣，那么您显然可以在发现循环时完成。

score 0 · Accepted Answer

如果你有一个简单的图形，你可以计算圈数：

C = E − N + P

其中 C 是循环数，E 是边数，N 是节点数，P 是组件数。如果你的图表是连接的，它是：

C = E - N + 1

4 回答 4