みなさん、ハッピーイースト。
私は現在、トポロジカルソートを学習しており、トポロジカルソートが実際にどのようにソートしようとしているのかについて質問しています。
アルゴリズム設計マニュアルでは、トポロジカルソートについて次のように説明しています。
トポロジカルソートは、有向非巡回グラフ(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)が有効なソートであると考えることはできますか?
ありがとう