java - 有向グラフの葉の要素を取り除く

Question

有向グラフとそのいくつかのノードが与えられた場合、指定されたノードのいずれにも到達できないノードをプルーニングする方法。(私はそれをリーフコンポーネントと呼んでいますが、これが正しい用語かどうかはわかりません)

これを効率的に解決する既知のアルゴリズムはありますか?

そのためのJavaオープンソースコードをいくつか指摘していただければ完璧です。

ありがとう。

Answer 1

指定された一連のノードから開始して幅優先検索または深さ優先検索を開始し、検索が通過するすべてのノードをマークします。その後、マークされていないすべてのノードは、指定されたノードのセットから到達できず、プルーニングできます。nが頂点の数でmがエッジの数である場合、これはO(n + m)の問題を解決します。

個人的には、JVM/Java/Scala でグラフを処理するためのメイン ライブラリとして、Tinkerpop Blueprintsを好みます。

Answer 2

私の理解が正しければ、 Strongly Connected Componentsを見つける必要があります。これは、深さ優先検索を 2 回実行することで O(n + m) 時間で見つけることができます。