algorithm - トポロジカル探索と幅優先探索

Question

幅優先検索ロジックを使用して、DAG のトポロジカル ソートを行うことは可能ですか? Cormen のソリューションは深さ優先検索を利用していますが、BFS を使用する方が簡単ではないでしょうか?

理由: BFS は、次の深さの値を持つノードを訪問する前に、特定の深さのすべてのノードを訪問します。これは当然、BFS を実行すると、親が子の前にリストされることを意味します。これはまさにトポロジーソートに必要なものではないでしょうか?

Answer 1

ウィキペディアでさえBFSに基づくアルゴリズムを説明している可能性があります。

基本的に、入力エッジのないすべてのノードを挿入するキューを使用します。次に、ノードを抽出するときに、その出力エッジをすべて削除し、他の入力エッジがないノードから到達可能なノードを挿入します。

Answer 2

BFS では、実際に歩くすべてのエッジが正しい方向になります。しかし、あなたが歩いていないすべてのエッジ (同じ深さのノード間のエッジ、またはより深いノードから以前のノードに戻るエッジ) は、グラフを BFS 順序でレイアウトすると、間違った方向に進んでしまいます。

はい、それには本当に DFS が必要です。