4

トポロジカル ソートを実行する必要がある一連のデータがあり、いくつかの仮定と制約があり、これに適した既存の効率的なアルゴリズムを誰かが知っているかどうか疑問に思っていました。

  • データの関係は、DAG を形成することが知られています (したがって、心配する循環はありません)。
  • A から B へのエッジは、A が B に依存していることを示しているため、B はトポロジー順序で A の前に表示される必要があります。
  • グラフは必ずしも接続されているわけではありません。つまり、任意の 2 つのノード N と M について、エッジをたどって N から M に到達する方法がない場合があります (エッジの方向を無視しても)。
  • データの関係は単独でリンクされています。これは、A から B に向かうエッジがある場合、A ノードだけがエッジの存在に関する情報を含むことを意味します。

問題は次のように定式化できます。

入ってくるエッジを持つ場合と持たない場合があるSグラフG内のノードのセットが与えられた場合、セット内の任意のノードから到達可能な(エッジ方向に従う)内のすべてのノードで構成されるサブグラフのトポロジー順序を見つけます。G'GS

Sこれは、セット内のノードに着信エッジがないことを必要とするため、トポロジカルソートの通常のアプローチを混乱させます。これは、私の場合には当てはまりません。病理学的ケースは次のとおりです。

A --> B --> D
|     ^     ^
|     |     |
\---> C ----/

どこでS = {B, C}。適切な順序付けは になりますD, B, Cが、通常のトポロジカル ソート アルゴリズムがたまたまB前に考慮した場合、C最終的には になりC, D, Bます。これは完全に間違っています。A(は から到達できないため、結果の順序には表示されないことに注意してくださいS。これは、 のすべてのノードにS着信エッジがある可能性がある例を示すためにあります)

さて、これは長い間解決されてきた問題であると想像しなければなりません。なぜなら、これは本質的に、1 つのインストール コマンドで複数のパッケージを指定するときにプログラムが好むものであり、実行しなければならないaptものだからです。yumただし、「依存関係解決アルゴリズム」などのキーフレーズを検索すると、この特定のケースを処理しない通常のトポロジカル ソートを説明する結果が得られます。

これを行う方法はいくつか考えられますが、どれも特に洗練されているとは思えません。誰かが適切なアルゴリズムへのポインタを持っているかどうか、できればデータを 1 回のパスで操作できるアルゴリズムを持っているかどうか疑問に思っていました。

4

2 に答える 2

3

データを 1 回パスするだけでこれを実行できるアルゴリズムは見つからないと思います。S のノードから始めて幅優先検索を実行し、結果のサブグラフでトポロジカル ソートを実行します。

于 2010-07-22T13:33:39.390 に答える
1

グラフ全体のトポロジカルソートを実行してから、ノードのセットから到達可能なノードのみを選択できると思います（ソート後の順序で、セット内のノードから深さ優先検索を実行できます。以前にアクセスしたことがない場合は、ノードのサブツリーに入ります)。

于 2010-07-22T13:28:45.903 に答える