代码之家  ›  专栏  ›  技术社区  ›  Thomas Browne

在二郎/长生不老药有向图中寻找树根

  •  2
  • Thomas Browne  · 技术社区  · 7 年前

    我有以下超简单的有向图树(代码是Elixir):

    digraph = :digraph.new()
    coords = [{0.0, 0.0}, {1.0, 0.0}, {1.0, 1.0}]
    [v0, v1, v2] = (for c <- coords, do:   :digraph.add_vertex(digraph, c))
    :digraph.add_edge(digraph, v0, v1)
    :digraph.add_edge(digraph, v1, v2)
    

    iex(82)> :digraph_utils.is_tree(digraph)
    true
    

    但是如何有效地找到树的顶点根呢?目前我正在做:

    iex(83)> Enum.filter(:digraph.vertices(digraph), fn x -> :digraph.in_degree(digraph, x) == 0 end)
    [{0.0, 0.0}]
    

    这是找到根顶点最有效的方法吗?也就是说,找到没有边的顶点?

    1 回复  |  直到 7 年前
        1
  •  3
  •   Alex de Sousa    7 年前

    有一个函数叫做 :digraph_utils.arborescence_root/1 这也许能奏效。

    iex(7)> :digraph_utils.arborescence_root(digraph)
    {:yes, {0.0, 0.0}}
    

    请注意,如果我们添加另一条边,从第一个顶点到最后一个顶点循环,则它将松开其根:

    iex(8)> :digraph.add_edge(digraph, v2, v0)
    iex(9)> :digraph_utils.arborescence_root(digraph)
    :no
    

    在效率方面, this built-in function does the same as your code 所以我想你的问题的答案是 .