graph - 有向非巡回グラフの最長パスにトポロジカルソートが必要なのはなぜですか?

Question

問題: 加重有向非巡回グラフ (DAG) とその中のソース頂点 s が与えられた場合、与えられたグラフ内の s から他のすべての頂点までの最長距離を見つけます。

参照グラフを見つけてください:リンク

なぜトポロジカルソートが必要なのですか? ソース頂点から変更された BFS を単純に使用できないでしょうか。なぜ私たちは線形順序付けをそれほど気にするのでしょうか。

これが繰り返しの場合は、親切に関連する回答にリダイレクトしてください。

ありがとう

Answer 1

「変更された BFS」でそれを行う方法を知っている場合は、その方法で行うことができます。ところで、「変更されたBFS」でそれを行うことをどのように提案しますか?

一方、リンクに示されているアルゴリズムは、最初にグラフをソートすることでそれを行います。それがまさにそのアルゴリズムの設計方法です。

現在、トポソート順序は、バックトラッキング段階で DFS アルゴリズムによって生成されます。残念ながら、DFS はトポソート順を逆方向に生成します。このため、Longest Path アルゴリズムの特定の処理を直接 DFS に「埋め込む」ことはできません。(このアルゴリズムは順方向の処理を必要とします。) したがって、2 パス アプローチを採用する必要があります。最初に純粋な DFS を実行して完全なトポソート シーケンスを構築し、次に 2 番目のパスを作成して最長パスを見つけます。

DAG の頂点はすでにトポソートされた順序で格納されている可能性があるため、実際の多くの状況では、トポソートに基づくアルゴリズムが役立ちます。つまり、トポソーティングは、前処理段階で 1 回だけ行われます。その後、さまざまな toposort ベースのアルゴリズムが、(スタックやキューなどに追加のメモリを必要とする BFS や DFS などのアルゴリズムとは対照的に) 追加のメモリを必要としない非常に効率的なワンパス アルゴリズムに効果的に変わります。