## 2. 準備：グラフの定義と 2 つの表現
### 2.1. グラフ・道・距離
$V$ を有限集合とする。
**無向グラフ**とは、対 $G=(V,E)$ であって $E \subseteq \{\, \{u,v\} \mid u,v \in V,\ u \ne v \,\}$ を満たすものをいう。$V$ の元を**頂点**、$E$ の元を**辺**という。
**有向グラフ**とは、対 $G=(V,E)$ であって $E \subseteq V \times V$ を満たすものをいう。$(u,v)\in E$ を $u$ から $v$ への**有向辺**という。
無向グラフの頂点 $u$ の**次数** $\deg(u)$ を、$u$ を含む辺の個数とする。有向グラフでは、$u$ を始点とする辺の個数を**出次数** $\deg^{+}(u)$、$u$ を終点とする辺の個数を**入次数** $\deg^{-}(u)$ とする。
さらに写像 $w : E \to \mathbb{R}$ が与えられているとき、$(G,w)$ を**重み付きグラフ**といい、$w(e)$ を辺 $e$ の**重み**という。
この定義は多重辺（同じ 2 頂点を結ぶ 2 本以上の辺）と無向の自己ループを許していません。このようなグラフを**単純グラフ**といいます。有向グラフでは $(u,u)\in E$ を許すことにします。
グラフ $G=(V,E)$ において、頂点の列 $W=(v_0,v_1,\ldots,v_k)$ が、すべての $i$ について $v_i$ と $v_{i+1}$ が辺で結ばれている（有向グラフなら $(v_i,v_{i+1}) \in E$）とき、$W$ を $v_0$ から $v_k$ への**歩道**といい、$k$ をその**長さ**という。
歩道 $W$ の頂点がすべて相異なるとき、$W$ を**道**という。$k \ge 1$ で、$v_0=v_k$ かつ $v_0,\ldots,v_{k-1}$ が相異なるとき、$W$ を**閉路**という。
$s$ から $v$ への歩道が存在するとき、$v$ は $s$ から**到達可能**であるという。$s$ から $v$ への歩道の長さの最小値を $\delta(s,v)$ と書き、$s$ から $v$ への**距離**という。到達可能でないときは $\delta(s,v)=\infty$ と定める。
距離を「歩道の長さの最小値」で定義しましたが、最小を与える歩道は必ず道になります。実際、歩道の中に同じ頂点 $x$ が 2 回現れれば、その間の部分（長さ 1 以上）を切り取ってより短い歩道が作れるので、最小性に反するからです。
以下、この章を通じて次の無向グラフを使います。
### 2.2. 隣接行列と隣接リスト
$V=\{v_1,\ldots,v_n\}$ と番号付けされたグラフ $G=(V,E)$ に対し、$n \times n$ 行列 $A$ を
$$
A_{ij} = \begin{cases} 1 & (v_i \text{ と } v_j \text{ が辺で結ばれている、有向グラフなら } (v_i,v_j) \in E) \\ 0 & (\text{そうでない}) \end{cases}
$$
で定め、$G$ の**隣接行列**という。重み付きグラフでは $1$ の代わりに重み $w$ を置き、辺がないところには $\infty$ を置く。
各頂点 $u$ に対し、$u$ に隣接する頂点（有向グラフでは $u$ を始点とする辺の終点）を並べたリスト $\mathrm{Adj}[u]$ の組を、$G$ の**隣接リスト**という。
上のグラフ $G_0$ を、頂点の順序を $s,a,b,c,d,e$ として表します。隣接行列は
$$
A = \begin{pmatrix}
0 & 1 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 1 & 0
\end{pmatrix}
$$
です。無向グラフなので $A$ は対称行列になります。$36$ 個の成分のうち $1$ は $14$ 個で、辺の本数 $7$ のちょうど 2 倍です。
隣接リストは次のとおりです。
| 頂点 | 隣接頂点 | 次数 |
|---|---|---|
| $s$ | $a,\ b$ | 2 |
| $a$ | $s,\ c$ | 2 |
| $b$ | $s,\ c,\ d$ | 3 |
| $c$ | $a,\ b,\ e$ | 3 |
| $d$ | $b,\ e$ | 2 |
| $e$ | $c,\ d$ | 2 |
次数の総和は $2+2+3+3+2+2=14=2\times 7$ です。この一致は偶然ではありません。
無向単純グラフ $G=(V,E)$ について
$$
\sum_{u \in V} \deg(u) = 2|E|
$$
が成り立つ。有向グラフ $G=(V,E)$ については
$$
\sum_{u \in V} \deg^{+}(u) = \sum_{u \in V} \deg^{-}(u) = |E|
$$
が成り立つ。
無向の場合、集合 $S = \{\,(u,e) \mid u \in V,\ e \in E,\ u \in e \,\}$ の元の個数を 2 通りに数えます。
頂点 $u$ を固定して数えると、$u$ を含む辺は定義により $\deg(u)$ 本なので、$u$ に対応する組は $\deg(u)$ 個です。$u$ について足し上げて $|S| = \sum_{u} \deg(u)$ を得ます。
辺 $e=\{u,v\}$ を固定して数えると、単純グラフでは $u \ne v$ なので、$e$ を含む組は $(u,e)$ と $(v,e)$ のちょうど 2 個です。$e$ について足し上げて $|S| = 2|E|$ を得ます。両者を等しいと置けば主張が従います。
有向の場合、各辺 $(u,v)$ は始点 $u$ の出次数に 1 だけ、終点 $v$ の入次数に 1 だけ寄与し、逆に出次数・入次数への寄与はすべてこの形なので、どちらの総和も辺の総数 $|E|$ に等しくなります。
$G=(V,E)$ を頂点数 $n=|V|$、辺数 $m=|E|$ のグラフとする。
(a) 隣接行列表現は $\Theta(n^2)$ 語の記憶領域を使う。与えられた $u,v$ について辺の有無の判定は $O(1)$ 時間、$u$ に隣接するすべての頂点の列挙は $\Theta(n)$ 時間、すべての辺の走査は $\Theta(n^2)$ 時間で行える（かつ、それより速くはできない）。
(b) 隣接リスト表現は $\Theta(n+m)$ 語の記憶領域を使う。$u$ に隣接するすべての頂点の列挙は $\Theta(1+\deg u)$ 時間、すべての辺の走査は $\Theta(n+m)$ 時間で行える。一方、与えられた $u,v$ について辺の有無の判定は、最悪 $\Theta(\deg u)$ 時間かかる。
(a) 行列は $n^2$ 個の成分を持つので領域は $\Theta(n^2)$ です。辺の有無は $A_{ij}$ という 1 回の添字アクセスで読めるので $O(1)$ です。$u$ の隣接頂点を列挙するには、行 $u$ の $n$ 個の成分を全部見る必要があります。どの成分が $1$ かは事前にわからないので、$n$ 個未満しか見ないと見落としの可能性が残り、$\Theta(n)$ が必要です。全辺の走査は各行についてこれを行うので $\Theta(n^2)$ です。
(b) 領域は、頂点ごとのリストの先頭を保持する部分が $\Theta(n)$、リストの要素の総数が、無向グラフでは各辺 $\{u,v\}$ が $\mathrm{Adj}[u]$ と $\mathrm{Adj}[v]$ に 1 回ずつ現れるので
無向単純グラフでは $m \le n(n-1)/2$ です。$m$ が $n$ に比例する程度の**疎なグラフ**では、隣接リストが $\Theta(n)$ 語で済むのに対し隣接行列は $\Theta(n^2)$ 語を使い、頂点数 $10^5$ の道路網なら $10^{10}$ 成分となって現実的ではありません。以降は隣接リストを前提にします。逆に $m=\Theta(n^2)$ の**密なグラフ**では隣接行列が有利です。
## 3. 幅優先探索：最短の「本数」を測る
### 3.1. アルゴリズム
幅優先探索（breadth-first search、BFS）は、始点 $s$ から近い順に頂点を訪れる探索です。「近い」は辺の本数で測ります。実装は、訪問予定の頂点を**先入れ先出しのキュー**（
）に入れておくだけです。
```python
from collections import deque
def bfs(adj, s):
"""adj[u] は u の隣接頂点のリスト。s は始点。"""
n = len(adj)
INF = float('inf')
dist = [INF] * n # d[v]
parent = [-1] * n # 最短路木の親
dist[s] = 0
queue = deque([s])
while queue:
u = queue.popleft() # 先頭から取り出す
for v in adj[u]: # u の隣接リストを 1 回だけ走査
if dist[v] == INF: # まだ発見していない頂点だけ
dist[v] = dist[u] + 1
parent[v] = u
queue.append(v) # 末尾に追加
return dist, parent
```
`dist[v]` が `INF` かどうかが「未発見か既発見か」の印を兼ねている点に注意してください。値は 1 度だけ書き込まれ、以後変わりません。以下、この配列を $d[v]$ と書きます。
### 3.2. 正当性
$d[v]$ が本当に距離 $\delta(s,v)$ に一致することを証明します。まず 2 つの不変式を用意します。
グラフ $G=(V,E)$（有向でも無向でもよい）と始点 $s \in V$ について上のアルゴリズムを実行する。実行中の任意の時点で次が成り立つ。
(a) すべての $v \in V$ について $d[v] \ge \delta(s,v)$ である（$d[v]=\infty$ の場合も含む）。
(b) キューの中身を先頭から順に $v_1,v_2,\ldots,v_r$（$r \ge 1$）とすると
$$
d[v_1] \le d[v_2] \le \cdots \le d[v_r] \le d[v_1] + 1
$$
が成り立つ。
(c) 頂点が取り出される順に $u_1,u_2,\ldots$ と並べると $d[u_1] \le d[u_2] \le \cdots$ である。
まず、辺で結ばれた 2 頂点の距離について
$$
u \text{ と } v \text{ が辺で結ばれている（有向なら } (u,v)\in E \text{）} \implies \delta(s,v) \le \delta(s,u)+1
$$
が成り立つことを確かめます。$\delta(s,u)=\infty$ なら右辺が $\infty$ なので自明です。$\delta(s,u)=k<\infty$ なら、長さ $k$ の $s$ から $u$ への歩道の末尾に辺 $(u,v)$ を継ぎ足すと、長さ $k+1$ の $s$ から $v$ への歩道になります。$\delta(s,v)$ は歩道の長さの最小値（
### 3.3. 計算量と実行例
隣接リスト表現の下で、BFS は $O(|V|+|E|)$ 時間、$O(|V|)$ の追加領域で動作する。隣接行列表現の下では $\Theta(|V|^2)$ 時間かかる。
配列 $d$ と $\mathrm{parent}$ の初期化に $\Theta(|V|)$ かかります。
BFS は、辺の重みがすべて等しい場合の最短経路アルゴリズムです。重みが等しくないときは後半のダイクストラ法が必要になります。[探索アルゴリズム](/computer-science/algorithms/searching) の
が「配列の中を探す」ものだったのに対し、グラフ探索は「つながりをたどって探す」ものだと対比すると、位置づけがはっきりします。
## 4. 深さ優先探索：時刻の入れ子構造
### 4.1. アルゴリズム
深さ優先探索（depth-first search、DFS）は、行けるところまで行って、行き止まりになったら 1 歩戻る探索です。再帰で書くのが自然です。頂点に**白**（未発見）・**灰色**（発見済みで走査中）・**黒**（走査完了）の 3 色を付け、色が変わる時刻を記録します。
```python
WHITE, GRAY, BLACK = 0, 1, 2
def dfs(adj):
"""adj[u] は u の隣接頂点のリスト。全頂点を始点候補として探索する。"""
n = len(adj)
color = [WHITE] * n
disc = [0] * n # 発見時刻 d[u]
fin = [0] * n # 完了時刻 f[u]
back_edges = []
time = 0
def visit(u):
nonlocal time
color[u] = GRAY
time += 1
disc[u] = time
for v in adj[u]:
if color[v] == WHITE:
visit(v) # v は u の子になる
elif color[v] == GRAY:
back_edges.append((u, v)) # 後退辺
color[u] = BLACK
time += 1
fin[u] = time
for u in range(n):
if color[u] == WHITE:
visit(u)
return disc, fin, back_edges
```
`visit(v)` が `visit(u)` の中から呼ばれたとき、$v$ を $u$ の**子**と呼びます。こうして全頂点上に森（**DFS 森**）ができます。時刻は色が変わるたびに 1 進むので $2|V|$ で終わり、$d[u]
上の DFS の実行中の任意の時点について、次が成り立つ。
(a) そのとき灰色である頂点を、再帰スタックの底から順に $x_1,x_2,\ldots,x_k$ とすると、各 $i$ について $x_{i+1}$ は $x_i$ の子である。特に $x_1,x_2,\ldots,x_k$ は $G$ の歩道であり、$x_k$ は現在隣接リストを走査中の頂点である。
(b) 頂点 $v$ が灰色である間に発見された頂点 $z$（$z \ne v$）は、DFS 森において $v$ の子孫であり、$f[z]
(a) 実行中に起きることは「`visit(u)` の呼び出し」と「`visit(u)` からの復帰」の 2 つだけなので、これらについての帰納法で示します。最初は灰色の頂点がなく主張は空虚に真です。
`visit(v)` が呼ばれるのは 2 か所です。1 つは最外側のループからで、このとき灰色の頂点は 1 つもないので、新しい列は $(v)$ の 1 個だけになり主張は成り立ちます。もう 1 つは `visit(x_k)` の隣接リスト走査の中で $v$ が白だった場合で、このとき $v$ は $x_k$ の子であり、$v$ が灰色になって列は $x_1,\ldots,x_k,v$ になります。帰納法の仮定と合わせて (a) が保たれます。`visit(x_k)` から復帰するときは $x_k$ が黒になって列の末尾が落ちるだけなので、主張は保たれます。
$x_{i+1}$ が $x_i$ の子であるということは、$x_{i+1}$ が $x_i$ の隣接リストに現れたということなので、$x_i$ と $x_{i+1}$ は辺で結ばれています。よって列は歩道です。
(b) $z$ が発見された瞬間を考えます。(a) より、そのとき灰色の列は $x_1,\ldots,x_k$ の形で、$z$ は走査中の頂点 $x_k$ の子として発見されます。いま $v$ が灰色なのだから $v=x_i$ となる $i$ があり、(a) より $x_k$ は $x_i$ の子孫（または $x_i$ 自身）なので、その子である $z$ は $v$ の子孫です。
子孫であることは、`visit(z)` の呼び出しが `visit(v)` の実行中に（入れ子になって）行われることを意味します。再帰呼び出しは内側が先に終わるので、`visit(z)` の復帰は `visit(v)` の復帰より前に起こり、$f[z]
### 4.3. 閉路検出とトポロジカルソート
$G=(V,E)$ を有向グラフとする。次の 2 つは同値である。
(i) $G$ は有向閉路を含む。
(ii) 上の DFS の実行中に、後退辺（走査時に灰色である頂点へ向かう辺）が少なくとも 1 本記録される。
したがって DFS により、$G$ が有向閉路を持つかどうかを $O(|V|+|E|)$ 時間で判定できる。
**(ii) $\Rightarrow$ (i)。** 後退辺 $(u,v)$ が記録されたとします。これは $u$ の走査中、つまり $u$ が灰色のときに、$v$ も灰色であったということです。