给定一个无向图,检测它是否包含循环的最佳算法是什么?
在跟踪访问节点的同时进行广度优先或深度优先搜索是一种方法,但它是 O(n^2)。有什么更快的吗?
给定一个无向图,检测它是否包含循环的最佳算法是什么?
在跟踪访问节点的同时进行广度优先或深度优先搜索是一种方法,但它是 O(n^2)。有什么更快的吗?
给定图 G(V,E) 的 BFS 和 DFS 算法的时间复杂度为 O(|V|+|E|)。所以你可以看到它是输入的线性依赖。如果您有非常专业的图,您可以执行一些启发式方法,但通常使用 DFS 并没有那么糟糕。您可以在此处查看一些信息。无论如何,您必须遍历整个图表。
这是你的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
。
希望你喜欢这个答案,虽然有点晚了!
如果使用邻接表表示图,则使用深度优先搜索测试图 G(V,E) 中是否存在循环是 O(|V|,|E|)。
有必要遍历整个图以显示没有循环。如果您只是对循环的存在/不存在感兴趣,那么您显然可以在发现循环时完成。
如果你有一个简单的图形,你可以计算圈数:
C = E − N + P
其中 C 是循环数,E 是边数,N 是节点数,P 是组件数。如果你的图表是连接的,它是:
C = E - N + 1