グラフアルゴリズム：BFS・DFS・ダイクストラ法を正しさから理解する

0. この記事の要点

• グラフの表現は隣接行列と隣接リストの 2 つが基本です。領域は $\Theta(|V|^2)$ と $\Theta(|V|+|E|)$、辺の有無の判定は $O(1)$ と $O(\deg u)$ で、得意なことが正反対です。
• 幅優先探索（BFS）は、始点からの辺の本数が最小の経路を、$O(|V|+|E|)$ 時間で全頂点について同時に求めます。正しさの核は「キューの中の距離はほぼ揃っている」という単調性です。
• 深さ優先探索（DFS）は、頂点の発見時刻と完了時刻が入れ子になるという構造を作ります。この構造から、有向閉路の検出とトポロジカルソートが同じ $O(|V|+|E|)$ で得られます。
• ダイクストラ法は、辺の重みがすべて非負という仮定の下で、重み付き最短経路を求めます。非負性は「まだ確定していない頂点を経由しても近道にならない」ことを保証するために必須で、これを外すと反例が作れます。
• 二分ヒープを優先度付きキューに使うと、ダイクストラ法は $O(|V| + |E|\log|V|)$ 時間で動きます。連結グラフでは $O(|E|\log|V|)$ と書けます。密グラフでは配列による $O(|V|^2)$ 実装のほうが速くなります。

1. 動機：つながり方だけを取り出す

1736 年、オイラーはケーニヒスベルクの町を流れる川に架かる 7 本の橋を、すべて 1 回ずつ渡って出発点に戻れるか、という問題を考えました。彼がやったことは、町の地図から距離も形も捨て、陸地を点、橋を線に置き換えることでした。残るのは「どことどこがつながっているか」だけです。この抽象化がグラフの始まりです。

同じ抽象化が現代の計算のいたるところに現れます。カーナビは交差点を頂点、道路を辺、所要時間を重みとするグラフの最短経路を解いています。パッケージマネージャは、パッケージを頂点、依存関係を有向辺とするグラフに循環がないかを調べ、インストール順序を決めます。表面上まったく違うこれらの問題が、到達可能か・最少の辺数で到達するには・総コストが最小の経路は何かという数個の問いに帰着します。

グラフでは計算量の測り方が一段複雑になります。ソートの入力サイズは配列の長さ $n$ ひとつでした（ソートアルゴリズム の ソート問題（定義 2.1）［ソートアルゴリズム］）。グラフの入力サイズは頂点数 $|V|$ と辺数 $|E|$ の2 つで決まり、しかも $|E|$ は $|V|-1$（木）から $|V|(|V|-1)/2$（完全グラフ）まで大きく動きます。そのため「$O(|V|^2)$ と $O(|E|\log|V|)$ のどちらが速いか」は入力の性質を指定しないと決まりません。計算量とO記法 の O 記法（定義 3.1）［計算量と O 記法］ による漸近評価が実際に効いてくる場面です。

この章では、グラフの表現を決めたうえで、BFS・DFS・ダイクストラ法を動く実装と証明の形で押さえます。

ノート

以下、$O(|V|+|E|)$ を $O(V+E)$ と略記することがあります。絶対値記号が省略されているだけで、慣習的な書き方です。

ここから先は Pro プランの内容です。

この章の続き（定義・定理・証明・例・演習）をすべて読むには Pro プランにご登録ください。無料の章は最後まで読めます。

プランを見る ログイン