グラフアルゴリズム幅優先探索・深さ優先探索・最短経路・最小全域木

グラフ $G = (V, E)$ の探索は、隣接リストを使えば幅優先探索・深さ優先探索とも $O(|V| + |E|)$ で、重みのないグラフの最短経路は幅優先探索で求まる。辺の重みが非負なら単一始点の最短経路はダイクストラ法で $O((|V| + |E|) \log |V|)$ 、負の重みがあればベルマン・フォード法で $O(|V||E|)$ で求め、負閉路も検出できる。連結な無向グラフの最小全域木は、カット性に基づくクラスカル法やプリム法で $O(|E| \log |V|)$ で求まる。

アルゴリズムとデータ構造の第3単元（全4単元）。先に読む単元：計算量と漸化式

情報系院試の問題集・ロードマップ

東大情報理工・東京科学大・阪大の大学別に、出題マップと類題を1冊にした教材（各4,980円）。収録内容と見本を商品ページで確認できる。

情報系の教材を見る

グラフの定義と表現

定義

グラフ・経路・重み

グラフ $G = (V, E)$ は頂点の集合 $V$ と辺の集合 $E$ からなる。辺に向きがあれば有向グラフ、なければ無向グラフという。頂点の列 $v_0, v_1, \dots, v_k$ で各 $(v_{i-1}, v_i)$ が辺であるものを長さ $k$ の経路という。重み関数 $w: E \to \mathbb{R}$ があるとき、経路の重みは辺の重みの和で、 $u$ から $v$ への最短経路の重みを $\delta(u, v)$ と書く。閉路をもたない有向グラフを DAG（有向非巡回グラフ）という。

表現と基本的な関係

隣接リスト: $\text{領域 } \Theta(|V| + |E|), \quad \text{頂点 } u \text{ の隣接頂点の列挙 } \Theta(\deg u)$
隣接行列: $\text{領域 } \Theta(|V|^2), \quad (u, v) \in E \text{ の判定 } \Theta(1)$
握手補題（無向）: $\sum_{v \in V} \deg v = 2|E|$
木: $\text{連結で閉路がない無向グラフ} \iff \text{連結で } |E| = |V| - 1$

幅優先探索・深さ優先探索・トポロジカルソート

幅優先探索（BFS）は始点 $s$ からキューを使って近い順に頂点を訪ねる。

$d[s] = 0$ 、他の頂点は $d[v] = \infty$ とし、 $s$ をキューに入れる。
キューから $u$ を取り出し、隣接する各 $v$ で $d[v] = \infty$ なら $d[v] = d[u] + 1$ としてキューに入れる。
キューが空になるまで2を繰り返す。

深さ優先探索（DFS）はキューの代わりにスタック（または再帰）を使い、行けるところまで進んでから戻る。各頂点の発見時刻と終了時刻が得られ、閉路の検出や強連結成分の分解に使う。

定理・法則

幅優先探索の正しさ

条件

重みのない（すべての辺の長さが1の）有向または無向グラフ、隣接リスト表現。

主張

BFS の終了時、各頂点で $d[v]$ は $s$ から $v$ への最短経路の辺数に等しく、 $s$ から到達できない頂点は $d[v] = \infty$ のままである。計算量は $O(|V| + |E|)$ 。

要点

キューに入る頂点の $d$ の値は単調非減少で、隣り合う値の差は1以下になる。辺に重みがあると、辺数の最短と重みの最短は一致しない。

定理・法則

トポロジカル順序の存在

条件

有向グラフ $G$ 。

主張

すべての辺 $(u, v)$ で $u$ が $v$ より前に来る頂点の並べ方（トポロジカル順序）が存在することと、 $G$ が DAG であることは同値である。

要点

DFS の終了時刻の降順に並べるか、入次数0の頂点を取り除き続ける方法（カーンのアルゴリズム）で $O(|V| + |E|)$ で求まる。途中で入次数0の頂点がなくなれば閉路がある。トポロジカル順序は一般に一意ではない。

計算例

カーンのアルゴリズムでトポロジカルソート

辺 $5 \to 2$ 、 $5 \to 0$ 、 $4 \to 0$ 、 $4 \to 1$ 、 $2 \to 3$ 、 $3 \to 1$ をもつ DAG をトポロジカルソートせよ。入次数0の頂点が複数あるときは番号の小さいものを先に取る。

解答

入次数は $0{:}2$ 、 $1{:}2$ 、 $2{:}1$ 、 $3{:}1$ 、 $4{:}0$ 、 $5{:}0$ 。

候補 $\{4, 5\}$ から $4$ を取り、 $0$ と $1$ の入次数を1減らす（ $0{:}1$ 、 $1{:}1$ ）。
候補 $\{5\}$ から $5$ を取り、 $2{:}0$ 、 $0{:}0$ 。
候補 $\{0, 2\}$ から $0$ 、次に $2$ を取り、 $3{:}0$ 。
$3$ を取り $1{:}0$ 、最後に $1$ 。

順序は $4, 5, 0, 2, 3, 1$ 。

検算

各頂点の位置は $4{:}1$ 、 $5{:}2$ 、 $0{:}3$ 、 $2{:}4$ 、 $3{:}5$ 、 $1{:}6$ 番目で、6本の辺すべてで始点が終点より前にある。取り出した頂点が6個なので、閉路がないことも確かめられる。

最短経路：ダイクストラ法とベルマン・フォード法

ダイクストラ法の手順は次のとおり。

$d[s] = 0$ 、他は $d[v] = \infty$ 、確定済み集合 $S = \emptyset$ とする。
$S$ にない頂点のうち $d[u]$ が最小の $u$ を選び、 $S$ に加える。
$u$ から出る各辺 $(u, v)$ で $d[u] + w(u, v) < d[v]$ なら $d[v] \leftarrow d[u] + w(u, v)$ とする（緩和）。
すべての頂点が $S$ に入るまで2、3を繰り返す。

ベルマン・フォード法は、全辺の緩和を $|V| - 1$ 回繰り返す。その後もう一度全辺を調べて、まだ緩和できる辺があれば始点から到達できる負閉路がある。

定理・法則

ダイクストラ法の正しさ

条件

有向（または無向）グラフで、すべての辺の重みが $w(u, v) \ge 0$ 。

主張

頂点 $u$ が $S$ に加えられた時点で $d[u] = \delta(s, u)$ である。二分ヒープを使うと計算量は $O((|V| + |E|) \log |V|)$ 、配列で最小値を探すと $O(|V|^2)$ 。

要点

最初に誤った値で確定する頂点があったとすると、その最短経路上で $S$ の外にある最初の頂点 $y$ について $d[y] = \delta(s, y) \le \delta(s, u) < d[u]$ となり、 $u$ を選んだことに反する。 $\delta(s, y) \le \delta(s, u)$ に非負の重みを使う。負の辺があるとこの不等式が崩れる。

定理・法則

ベルマン・フォード法

条件

重みは負でもよい有向グラフ。

主張

始点から到達できる負閉路がなければ、 $|V| - 1$ 回の全辺緩和の後 $d[v] = \delta(s, v)$ となる。負閉路があれば、 $|V|$ 回目の検査で緩和できる辺が見つかる。計算量は $O(|V||E|)$ 。

要点

負閉路がなければ最短経路は辺 $|V| - 1$ 本以下の単純経路で、 $i$ 回目の反復で辺 $i$ 本の最短経路の値が確定する。

計算例

ダイクストラ法で距離の表を追う

有向辺 $s \to a\,(4)$ 、 $s \to b\,(1)$ 、 $b \to a\,(2)$ 、 $a \to c\,(1)$ 、 $b \to c\,(5)$ 、 $c \to t\,(3)$ 、 $b \to d\,(8)$ 、 $d \to t\,(1)$ （括弧内は重み）のグラフで、 $s$ からの最短距離を求めよ。

解答

$s$ を確定（ $0$ ）。 $d[a] = 4$ 、 $d[b] = 1$ 。
$b$ を確定（ $1$ ）。 $d[a] = \min(4, 1 + 2) = 3$ 、 $d[c] = 6$ 、 $d[d] = 9$ 。
$a$ を確定（ $3$ ）。 $d[c] = \min(6, 3 + 1) = 4$ 。
$c$ を確定（ $4$ ）。 $d[t] = 7$ 。
$t$ を確定（ $7$ ）、続いて $d$ を確定（ $9$ ）。 $d \to t$ は $10 > 7$ で更新しない。

$\delta(s, \cdot)$ は $s{:}0$ 、 $b{:}1$ 、 $a{:}3$ 、 $c{:}4$ 、 $t{:}7$ 、 $d{:}9$ 。 $t$ への最短経路は $s \to b \to a \to c \to t$ 。

検算

経路の重みは $1 + 2 + 1 + 3 = 7$ 。他の経路 $s \to a \to c \to t$ は $8$ 、 $s \to b \to c \to t$ は $9$ 、 $s \to b \to d \to t$ は $10$ で、どれも $7$ 以上。

計算例

負の辺でダイクストラ法が誤る例

有向辺 $s \to a\,(4)$ 、 $s \to b\,(5)$ 、 $b \to a\,(-3)$ 、 $a \to c\,(3)$ 、 $c \to t\,(2)$ 、 $b \to t\,(6)$ のグラフで、ダイクストラ法とベルマン・フォード法の結果を比べよ。

解答

ダイクストラ法は $s$ の次に $d[a] = 4 < d[b] = 5$ の $a$ を確定し、 $d[c] = 7$ 。次に $b$ を確定するが、 $a$ は確定済みなので $b \to a$ で更新しない。 $c$ を確定して $d[t] = 9$ となり、結果は $a{:}4$ 、 $c{:}7$ 、 $t{:}9$ 。

ベルマン・フォード法では $b \to a$ の緩和で $d[a] = 5 - 3 = 2$ となり、 $c{:}5$ 、 $t{:}7$ を得る。正しい値は後者で、 $t$ への最短経路は $s \to b \to a \to c \to t$ （重み $5 - 3 + 3 + 2 = 7$ ）。

検算

このグラフに閉路はないので負閉路もなく、ベルマン・フォード法の条件を満たす。 $|V| = 5$ で4回の反復後、5回目の検査で緩和できる辺はない。

最短経路アルゴリズムの使い分け

重みなし: $\text{BFS}: O(|V| + |E|)$
DAG（負の重み可）: $\text{トポロジカル順に緩和}: O(|V| + |E|)$
非負の重み: $\text{ダイクストラ法（二分ヒープ）}: O((|V| + |E|)\log|V|)$
負の重みあり: $\text{ベルマン・フォード法}: O(|V||E|)$
全点対: $\text{ワーシャル・フロイド法}: \Theta(|V|^3), \quad d_{ij}^{(k)} = \min\left(d_{ij}^{(k-1)},\ d_{ik}^{(k-1)} + d_{kj}^{(k-1)}\right)$
負閉路がなければ負の重みがあってもよい。終了後に $d_{ii} < 0$ となる $i$ があれば負閉路がある。

最小全域木とカット性

定義

最小全域木

連結な重みつき無向グラフ $G$ の全域木（全頂点を含む部分グラフで木であるもの）のうち、辺の重みの和が最小のものを最小全域木という。辺は $|V| - 1$ 本である。

定理・法則

カット性

条件

$G$ は連結な重みつき無向グラフ。辺集合 $A$ はある最小全域木に含まれる。頂点の分割 $(S, V \setminus S)$ を横切る $A$ の辺はない。

主張

$(S, V \setminus S)$ を横切る辺のうち重み最小の辺 $e$ について、 $A \cup \{e\}$ もある最小全域木に含まれる。

要点

$A$ を含む最小全域木 $T$ が $e$ を含まなければ、 $T$ に $e$ を加えてできる閉路はカットを横切る別の辺 $e'$ をもつ。 $e'$ を $e$ に替えても重みは増えない。クラスカル法とプリム法はこの性質で正しさが示される。

クラスカル法は辺を重みの小さい順に見て、閉路を作らない辺を採用する。閉路の判定には素集合データ構造（union-find）を使い、全体は辺の整列で $O(|E| \log |E|) = O(|E| \log |V|)$ かかる。プリム法は1頂点から始め、木と木の外を結ぶ最小の辺を加え続ける。

計算例

クラスカル法

無向辺 $AB\,(4)$ 、 $AC\,(1)$ 、 $BC\,(2)$ 、 $BD\,(5)$ 、 $CD\,(8)$ 、 $CE\,(10)$ 、 $DE\,(2)$ 、 $DF\,(6)$ 、 $EF\,(3)$ のグラフの最小全域木を求めよ。

解答

重みの小さい順に見る。 $AC\,(1)$ 採用、 $BC\,(2)$ 採用、 $DE\,(2)$ 採用、 $EF\,(3)$ 採用。 $AB\,(4)$ は $A, B$ がすでに $C$ を通じてつながるので閉路になり不採用。 $BD\,(5)$ 採用で辺が $6 - 1 = 5$ 本になり終了する。

最小全域木は $\{AC, BC, DE, EF, BD\}$ 、重みは $1 + 2 + 2 + 3 + 5 = 13$ 。

検算

9本から5本を選ぶ $\binom{9}{5} = 126$ 通りをすべて調べても、全域木の重みの最小は13である。分割 $\{A, B, C\}$ と $\{D, E, F\}$ を横切る辺は $BD\,(5)$ 、 $CD\,(8)$ 、 $CE\,(10)$ で、最小の $BD$ が採用されておりカット性とも合う。

答案でよくある誤り

1
負の重みの辺があるグラフにダイクストラ法を使う。確定済みの頂点が後から短くなり得るので、ベルマン・フォード法を使うか、DAG ならトポロジカル順の緩和を使う。
2
重みつきグラフの最短経路を BFS で求める。BFS が求めるのは辺数の最短で、重みがすべて等しいときだけ重みの最短と一致する。
3
計算量を $O(|V|^2)$ と $O((|V| + |E|)\log |V|)$ のどちらか片方だけ書き、データ構造を書かない。ダイクストラ法の計算量は優先度付きキューの実装で変わるので、配列か二分ヒープかを書く。
4
負閉路があるのに最短距離を答える。負閉路に到達できる頂点では最短経路の重みが定義されない（ $-\infty$ ）。ベルマン・フォード法の $|V|$ 回目の検査で確かめる。
5
クラスカル法で、重みが小さければ閉路を作る辺も採用する。採用前に、両端が同じ連結成分にないことを union-find で確かめる。
6
最小全域木の中の経路を2頂点間の最短経路とみなす。辺 $uv\,(3)$ 、 $vw\,(2)$ 、 $uw\,(2)$ の三角形では最小全域木は $\{vw, uw\}$ で、木の中の $u$ から $v$ への経路は重み $4$ だが、最短経路は辺 $uv$ の $3$ である。