3

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

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

4

4 回答 4

6

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

于 2009-05-14T10:31:25.200 回答
4

这是你的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

希望你喜欢这个答案,虽然有点晚了!

于 2009-06-12T10:00:52.990 回答
1

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

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

于 2009-05-14T10:52:14.527 回答
0

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

C = E − N + P

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

C = E - N + 1
于 2012-05-01T07:22:37.597 回答