2

次の非常に単純な有向グラフ ツリーがあります (コードは 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}]

これは、ルート頂点を見つける最も効率的な方法ですか、つまり、エッジのない頂点を見つけることですか?

4

1 に答える 1