首页 文章

用于检测图中循环的最快算法

提问于
浏览
2

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

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

4 回答

  • 5

    给定图G(V,E)的BFS和DFS算法具有O(| V | | E |)的时间复杂度 . 所以你可以看到它使用DFS并不是那么糟糕 . 您可以查看一些信息here . 无论如何,你必须遍历整个图表 .

  • 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)日志,这将使整个算法 O(min(E,V))+logs .

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

  • 0

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

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

  • 1

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

    C = E − N + P
    

    其中C是循环数,E是边数,N是节点数,P是组件数 . 如果图表已连接,则为:

    C = E - N + 1
    

相关问题