グラフアルゴリズムの可視化
グラフには別々の問いがあります。どの依存から処理するか。一つの始点から各頂点へ最小費用でどう行くか。全体を最小総費用でどうつなぐか。順序はトポロジカルソート、単一始点最短路は Dijkstra と Bellman-Ford、全体の接続は最小全域木が扱います。
最短路木は始点からの経路を最短にしますが、選んだ辺の総和が最小とは限りません。最小全域木は総辺重みを最小にしても、特定の二点間の経路を長くする場合があります。
目標の比較
| アルゴリズム | 目標 | 次の選択 | 主な条件 | 典型時間 |
|---|---|---|---|---|
| トポロジカルソート | 依存順の配列 | Kahn は入次数ゼロ、DFS は復帰時の完了点 | 有向非巡回グラフ | O(V + E) |
| Dijkstra | 単一始点の最短距離 | 仮距離が最小の未確定頂点 | 非負辺重み | O((V + E) log V) |
| Bellman-Ford | 単一始点の最短距離 | 毎回すべての辺を緩和 | 始点から到達可能な負閉路がない | O(V · E) |
| Prim | 最小全域木 | 現在の木から外へ渡る最軽辺 | 無向で連結 | O((V + E) log V) |
| Kruskal | 最小全域木 | 異なる成分をつなぐ次の最軽辺 | 無向で連結 | O(E log E) |
Dijkstra と Prim は最小ヒープを使えても、優先値が異なります。前者は始点からの経路全体、後者はカットを渡る一辺の重みです。Kruskal は始点を中心にせず全辺をソートし、Union-Find の根で接続を判定します。
推奨する学習順序
DFS と BFS の後でトポロジカルソートを学びます。Kahn は入次数ゼロから依存を取り除き、DFS は戻り際に完了順を記録します。同じ DAG でも別の有効順序が得られ、巡回プリセットでは両者とも部分的な答えを完成としません。
Dijkstraでは仮距離と緩和を追います。未確定の経路は後で改善できます。負辺の例では、費用が途中で減ると、最小値を取り出した時点で確定する規則が安全でなくなると分かります。
次に Bellman-Fordの Dijkstra の罠プリセットで同じグラフを使います。優先キューや永久確定を使わず、最大 V−1 回の辺の緩和と追加確認で、最短路または到達可能な負閉路を調べます。
最小全域木の Prim では左の記録にカットが見え、最軽の横断辺を選びます。負辺もここでは Dijkstra と同じ問題を起こしません。
グラフを保って Kruskal へ切り替えると、下に全辺のソート列、左に連結成分が現れます。端点の根が同じなら、既に採用した経路が、候補によって閉じる巡回を示します。
注目する点
- 優先値が経路全体か一辺かを区別します。
- Kahn では正の入次数が残る前提を示します。DFS は未完了の後続頂点を処理してから現在点を記録します。
- 安い候補でも、不変条件を満たして初めて安全に採用できます。
- Dijkstra の古いキュー項目や、全域木の巡回を閉じる辺の拒否を見ます。
- 非連結グラフを試します。部分的な森は全グラフの全域木ではありません。
グラフアルゴリズムの可視化一覧
グラフや方式を変え、Python または JavaScript のコードとトレースを比較してください。