logo标签列表

如何检查有向图是否为无环图？

algorithmtheorydirected-graphdirected-acyclic-graphs
91

我如何检查有向图是否为无环图？该算法名称是什么？如果有参考资料将不胜感激。

另一个支持在SO上“修复”错误答案的情况。 - Sparr
2
所以，嗯，我主要关心找到它所需的时间。因此，我只需要抽象算法。 - nes1983
你必须遍历所有边并检查所有顶点，因此下限是 O（|V| + |E|）。DFS 和 BFS 的复杂度相同，但如果有递归，则 DFS 更容易编码，因为它可以为您管理堆栈... - ShuggyCoUk
2
DFS永远不是O(n!)。它只访问每个节点一次，每条边最多访问两次。因此，时间复杂度为O（|V|+|E|）或O(n)。 - Jay Conrod
我的DFS注释是我愚蠢地以无向图的方式思考。 - ShuggyCoUk
显示剩余2条评论
12个回答
0

这是我的 Ruby 实现 剥离叶节点算法。

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end
-1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接