2

グラフGのすべてのノードのリスト、すべての既存の接続（エッジ）のリスト、およびすべてのノードの隣接リストのリストが与えられた場合、特定のノードのドミネーターのリストを見つけるにはどうすればよいですか？ ？

私が考えていた1つの方法は、次のとおりです。

与えられたノードNについて、ルートノードからNまでのすべてのパスを見つけます。これらのパスの交差により、Nを支配するノードのセットが得られます。しかし、ここでの落とし穴は、実際にパスを見つける方法です。特に、JAVAでコーディングしている間。

具体的には、役立つ回答をいただければ幸いです。

ありがとうございました！

4

1 に答える 1

2

Tarjanのアルゴリズムを正常に実装しました。

FWIW、それは次のようになります：

nが支配的なノードのセットを見つけるには、開始ノードから残りのノードまでのすべてのパス（すべてのノードの隣接リストがあれば簡単に処理できます）を計算して、nを回避します。この到達可能なノードのセットをRとします。nが支配するノードは、 Rに存在しないノードです。つまり、Uが特定のグラフのすべてのノードのセットである場合、nはセットURに属するノードを支配します。

于 2012-12-06T06:23:27.763 に答える