7

みなさん、ハッピーイースト。

私は現在、トポロジカルソートを学習しており、トポロジカルソートが実際にどのようにソートしようとしているのかについて質問しています。

アルゴリズム設計マニュアルでは、トポロジカルソートについて次のように説明しています。

トポロジカルソートは、有向非巡回グラフ(DAG)で最も重要な操作です。有向エッジがすべて左から右になるように、ライン上の頂点を並べ替えます。

この大胆な部分は私を混乱させます。では、トポロジカルソートは頂点またはすべての有向エッジをソートしますか?

本にもある例を見てみましょう。

DAG

したがって、上記のDAGの場合、トポロジカルソート(G、A、B、C、F、E、D)を取得できます。

こういうのがわかります。頂点が並べ替えられるだけでなく、エッジも並べ替えられます。つまり、G-> A-> B-> C-> F-> E-> Dであり、これは上記のADMブックの説明と一致します。all directed edges go from left to right

しかし、B-> Cの端を削除するとどうなりますか?結果のグラフはまだDAGですが、トポロジカルソートは(G、A、B、C、F、E、D)のままですか?

「はい」の場合、A-> B-> Cはもう存在しないため、エッジはソートされていないと思います。代わりに、A->BおよびA->Cです。それで、この場合はまだ有効なトポロジカルソートですか?AがBとCの親であっても、(G、A、B、C、F、E、D)が有効なソートであると考えることはできますか?

ありがとう

4

1 に答える 1

9

要素の順序付けと考えることができます。

v1,v2,...,vn を要素とする。そしてエッジ(vi,vj)がそれを表すとしましょうvi<vj。トポロジカル ソートは、ソート後に次のことを保証しviます。vji < jvjvi

または、他の表記法では、が に依存し(vi,vj)ていることを示していると仮定します。トポロジカル ソートは、各要素が、ソートの後に現れる要素に「依存しない」ことを保証します。vjvi

では、トポロジカル ソートは頂点またはすべての有向辺をソートしますか?

トポロジカル ソートは、エッジではなく頂点をソートします。頂点をソートするための制約としてエッジを使用します。

しかし、B->C のエッジを削除するとどうなるでしょうか?

はい、追加するすべてのエッジに、制約を追加するだけです。トポロジカル ソートには複数の実行可能な解が存在する可能性があることに注意してください [たとえば、エッジのないグラフの場合、任意の順列が実行可能な解です]。制約を取り除くことで、「より難しい問題を解決する」以前の解決策が実行可能になります。

A が B と C の親であっても、(G、A、B、C、F、E、D) は有効な並べ替えであると考えることができますか?

それで問題ありません!A はトポロジカル ソートで B,C の前に表示されるので、父親であることは問題ありません。

それがもう少し明確になることを願っています。

于 2012-04-08T11:44:26.190 に答える