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