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

> グラフの表現と、幅優先探索・深さ優先探索・トポロジカルソート、ダイクストラ法とベルマン・フォード法の条件、クラスカル法とカット性を、距離の表を追う計算例と負の辺での反例で解説します。

- HTML版（正規URL）: https://inshihub.com/basics/algorithms/graph-algorithms
- 科目: [アルゴリズムとデータ構造](https://inshihub.com/basics/algorithms)（大学基礎課程の数学・物理・化学・生物・情報）
- 最終更新: 2026-11-16
- 先に読む単元: [計算量と漸化式](https://inshihub.com/basics/algorithms/complexity-recurrences)

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

## グラフの定義と表現

### 定義：グラフ・経路・重み

グラフ $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$ からキューを使って近い順に頂点を訪ねる。

1. $d[s] = 0$、他の頂点は $d[v] = \infty$ とし、$s$ をキューに入れる。
2. キューから $u$ を取り出し、隣接する各 $v$ で $d[v] = \infty$ なら $d[v] = d[u] + 1$ としてキューに入れる。
3. キューが空になるまで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$。

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

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

検算：

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

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

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

1. $d[s] = 0$、他は $d[v] = \infty$、確定済み集合 $S = \emptyset$ とする。
2. $S$ にない頂点のうち $d[u]$ が最小の $u$ を選び、$S$ に加える。
3. $u$ から出る各辺 $(u, v)$ で $d[u] + w(u, v) < d[v]$ なら $d[v] \leftarrow d[u] + w(u, v)$ とする（緩和）。
4. すべての頂点が $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$ からの最短距離を求めよ。

解答：

1. $s$ を確定（$0$）。$d[a] = 4$、$d[b] = 1$。
2. $b$ を確定（$1$）。$d[a] = \min(4, 1 + 2) = 3$、$d[c] = 6$、$d[d] = 9$。
3. $a$ を確定（$3$）。$d[c] = \min(6, 3 + 1) = 4$。
4. $c$ を確定（$4$）。$d[t] = 7$。
5. $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$ である。

## グラフアルゴリズムが出た院試の過去問

### [グラフ理論](https://inshihub.com/exam-themes/graph-theory)（8大学・22問）

- [名古屋大学大学院 数理情報学 2026年度 第6問](https://inshihub.com/exam-solutions/nagoya-university/graduate-school-of-informatics/mathematical-informatics/2026#problem-6): 離散最適化
- [名古屋大学大学院 複雑系科学 2026年度 第17問](https://inshihub.com/exam-solutions/nagoya-university/graduate-school-of-informatics/complex-systems-science/2026#problem-17): 情3：整列・二分探索木と最短経路法
- [東京都立大学大学院 情報科学域 専門科目 2026年度 第4問](https://inshihub.com/exam-solutions/tokyo-metropolitan-university/graduate-school-of-systems-design/information-science/2026-winter#problem-4): ダイクストラ法の追跡
- [京都大学 知能情報学コース 2025年度 第3問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/intelligence-science-and-technology/2025#problem-3): F2-1 アルゴリズムとデータ構造
- [京都大学 数理工学コース 2025年度 第4問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/mathematical-engineering/2025#problem-3): 専門 第2問：グラフ理論
- [北海道大学大学院 情報科学専攻 情報理工学コース 専門科目 2025年度 第4問](https://inshihub.com/exam-solutions/hokkaido-university/graduate-school-of-information-science-and-technology/computer-science-and-information-technology/2025#problem-4): アルゴリズムとデータ構造

解答まで無料で読める演習問題:

- [大阪大学 専門科目（情報数理学） 2023年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2023#problem-1): 情報基礎

### [グラフ探索](https://inshihub.com/exam-themes/graph-search)（9大学・14問）

- [名古屋大学大学院 複雑系科学 2026年度 第17問](https://inshihub.com/exam-solutions/nagoya-university/graduate-school-of-informatics/complex-systems-science/2026#problem-17): 情3：整列・二分探索木と最短経路法
- [東京都立大学大学院 情報科学域 専門科目 2026年度 第4問](https://inshihub.com/exam-solutions/tokyo-metropolitan-university/graduate-school-of-systems-design/information-science/2026-winter#problem-4): ダイクストラ法の追跡
- [北海道大学大学院 情報科学専攻 情報理工学コース 専門科目 2025年度 第4問](https://inshihub.com/exam-solutions/hokkaido-university/graduate-school-of-information-science-and-technology/computer-science-and-information-technology/2025#problem-4): アルゴリズムとデータ構造
- [東京科学大学 専門科目（情報工学） 2025年度 第3問](https://inshihub.com/exam-solutions/institute-of-science-tokyo/school-of-computing/computer-science/2025#problem-3): 格子経路と再帰・動的計画法
- [京都大学 数理工学コース 2024年度 第4問](https://inshihub.com/exam-solutions/kyoto-university/graduate-school-of-informatics/mathematical-engineering/2024#problem-3): 専門 第2問：グラフ理論
- [東京大学 専門科目（コンピュータ科学） 2024年度 第3問](https://inshihub.com/exam-solutions/tokyo-university/information-science/computer-science/2024#problem-3): 連結性と全域木

解答まで無料で読める演習問題:

- [大阪大学 専門科目（情報数理学） 2022年度 第1問](https://inshihub.com/exam-solutions/osaka-university/graduate-school-of-information-science-and-technology/information-and-physical-sciences/2022#problem-1): 情報基礎
- [東京大学 学際情報学専攻 先端表現情報学コース 専門科目 2014年度 第2問](https://inshihub.com/exam-solutions/tokyo-university/graduate-school-of-interdisciplinary-information-studies/emerging-design-and-informatics/2014#problem-2): 水量計測と状態探索