アルゴリズムとデータ構造
第11回 グラフの探索

1

アルゴリズムとデータ構造#11

今日の内容◼

グラフ◼ なんでグラフ？
◼ グラフの数学的な定義◼ ネットワーク（重み付きグラフ）の定義◼

グラフデータの取り扱い方◼ 隣接行列による表現◼ 隣接リストによる表現◼

グラフの探索の仕方◼ 幅優先探索◼ 深さ優先探索アルゴリズムとデータ構造#112

ケーニヒスベルクの橋◼

ケーニヒスベルクという街にはプレーゲル川が流れ、7つの橋が架かっていた◼

Q： 7つすべての橋を、それぞれちょうど 1 回ずつ渡って歩くコースって、ある ?

A： ない。
その理由は …

オイラー (Euler) 18世紀の数学者。天文学者や物理学者などでもある。
解析学、整数論、トポロジー、グラフ理論などに大きな足跡を残した。
図は、http://Wikipedia.org より

ケーニヒスベルクの橋◼

ケーニヒスベルクという街にはプレーゲル川が流れ、7つの橋が架かっていた◼

Q： 7つすべての橋を、それぞれちょうど 1 回ずつ渡って歩くコースって、ある ?

◼

川で別れる 4 つの土地を「頂点」、橋を「 （頂点を結ぶ） 辺」 に置き換える
街をグラフで表す◼

グラフが一筆書きできる条件は …
グラフの性質を調べる

アルゴリズムとデータ構造#114

なんでグラフ？
モノとモノのつながりを簡潔に記述し，解析できる！

世の中のすべてはグラフ！
アルゴリズムとデータ構造#115

グラフ (graph) G = (V, E)
頂点 (vertex) の集合 𝑉 と辺 (edge) の集合 𝐸 ⊆ 𝑉 × 𝑉 の組 (𝑉, 𝐸) のこと例） 𝑉 = 𝑣0 , 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝐸 = {𝑒0 , 𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 }のとき
ただし，𝑒0 = 𝑣0 , 𝑣1 , 𝑒1 = 𝑣1 , 𝑣2 , 𝑒2 = 𝑣0 , 𝑣2 ,𝑒3 = 𝑣2 , 𝑣3 , 𝑒4 = 𝑣3 , 𝑣4 , 𝑒5 = (𝑣4 , 𝑣0 )無向グラフ (undirected graph)

有向グラフ (directed graph)𝑣0𝑣0𝑒0𝑣1𝑒1𝑒2𝑒5𝑒0𝑣4𝑒4𝑣2 𝑒3 𝑣3𝑣1𝑒1𝑒2𝑒5𝑣4𝑒4𝑣2 𝑒3 𝑣3

有向グラフの場合，辺(𝑢, 𝑣)は頂点𝑢から頂点𝑣への辺（有向辺）を表す
無向グラフでは辺(𝑢, 𝑣)を{𝑢, 𝑣}と書く場合もある

6ネットワーク (network)
各辺𝑒𝑖 に重み（整数値または実数値）𝑤𝑖 が付いたグラフのこと．重み付きグラフ (weighted graph)．
例） 𝑉 = 𝑣0 , 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝐸 = {𝑒0 , 𝑒1 , 𝑒2 , 𝑒3 , 𝑒4 , 𝑒5 }のとき
ただし，𝑒0 = 𝑣0 , 𝑣1 , 𝑒1 = 𝑣1 , 𝑣2 , 𝑒2 = 𝑣0 , 𝑣2 ,𝑒3 = 𝑣2 , 𝑣3 , 𝑒4 = 𝑣3 , 𝑣4 , 𝑒5 = (𝑣4 , 𝑣0 )𝑤0 = 2, 𝑤1 = 3, 𝑤2 = 4, 𝑤3 = 2, 𝑤4 = 1, 𝑤5 = 2

無向ネットワーク

有向ネットワーク𝑣0𝑣02𝑣1342𝑣
2
アルゴリズムとデータ構造#11

22𝑣4

1𝑣3𝑣1
34𝑣2 22𝑣4

1𝑣3

7

隣接行列 (adjacency matrix) による表現
有向グラフについて，各辺の有無を行列で表したもの（有向ネットワークの場合は重みを要素とした行列）
𝑒0

𝑣1
𝑒1𝑣0
𝑒2𝑣0 𝑣1 𝑣2 𝑣3 𝑣4𝑒5𝑣4
𝑒4𝑣2 𝑒3 𝑣3𝑣022𝑣13𝑣2

42𝑣3

00001

10000110000010000010𝐴 𝑖, 𝑗 = ൞1𝑣𝑖 , 𝑣𝑗 ∈ 𝐸 ,0𝑣𝑖 , 𝑣𝑗 ∉ 𝐸)

𝑣0 𝑣1 𝑣2 𝑣3 𝑣4𝑣41𝑣0𝑣1𝑣2𝑣3𝑣4𝑣0𝑣1𝑣2𝑣3𝑣40000220000

4300000200000
10𝐴 𝑖, 𝑗 =൞𝑤𝑘𝑣𝑖 , 𝑣𝑗 = 𝑒𝑘 ∈ 𝐸 ,0𝑣𝑖 , 𝑣𝑗 ∉ 𝐸)

※ 無向グラフの場合は，各無向辺 (u, v) を２つの有向辺 (u, v), (v, u) に置き換えた有向グラフとみなして表現する

8隣接リスト (adjacency list) による表現
有向グラフについて，各辺の有無を連結リストの配列で表したもの（ネットワークの場合は重みを付加する）
𝑒0𝑣1𝑒1𝑣0𝑒2𝑒5𝑣4𝑒4𝑣2 𝑒3 𝑣3𝑣022𝑣134𝑣2 2𝑣41𝑣30
1234

12 NULL
3 NULL
4 NULL
0 NULL0123412340

23 NULL
2 NULL
1 NULL
2 NULL

2 NULL

2 4 NULL

重みは第２要素に格納※ 無向グラフの場合は，各無向辺 (u, v) を２つの有向辺 (u, v), (v, u) に置き換えた有向グラフとみなして表現する

9隣接行列と隣接リストの利点，欠点
利点
隣接 ２頂点間に辺があるか否か行 をO(1)時間でチェック可能列利点
隣接 O(𝑚)の記憶領域で済む
リス
ト １つの頂点の隣接頂点を求めるのは，その隣接頂点数に比例した時間だけで可能n = |V|, m = |E|

欠点
O(𝑛2 )の記憶領域が必要
１つの頂点の隣接頂点を求めるのにO(𝑛)時間必要

欠点
２頂点間に辺があるか否かをチェックするのに，隣接頂点数に比例した時間が必要
連結リストを線形探索するから10

グラフの探索
頂点数𝑛の入力グラフ 𝐺 = (𝑉, 𝐸) が与えられたとき，そのすべての頂点を訪問すること．
• 入力グラフは，隣接リスト表現で与えられるとする• 出力として，訪問した頂点の並びを出力する．
ただし，同じ頂点は2回以上重複して出力しないものとする

応用• ゲーム（迷路，盤ゲーム），画像処理，etc…

各種グラフ処理の基本アルゴリズム

探索法には主に次の２つがある。
１．幅優先探索 (Breadth-First Search, BFS)
２．深さ優先探索 (Depth-First Search, DFS)
アルゴリズムとデータ構造#1111

幅優先探索の考え方
基本的なアイデア• ソース（スタート地点となる頂点）𝑠から「波」を伝播させて，波の「先端」(frontier）を横断的に訪問（展開）することで，すべての頂点を探索する
ab特長h• ソースから近い順番に訪問できる
dgc feアルゴリズムの動き

1. ソース 𝑠 を一つ決め，キュー（FIFO）に入れる
2. キューから一つ頂点 𝑣 を取り出して 𝑣 をたどる
3. 𝑣 の隣接頂点のうち未訪問（かつ未発見）の頂点をすべてキューに入れる12
4. キューが空になるまで２と３を繰り返す

幅優先探索アルゴリズム BFS
Procedure BFS (𝐺: グラフ)
頂点𝑣の状態の意味
1: for each 𝑣 ∈ 𝑉 do 状態[𝑣] ← 白;
色意味
2: Q ← 空のキュー;
白未訪問
3: 状態[𝑠] ← 赤; // ソース𝑠は適当な頂点
赤発見済
4: Q.Enqueue(𝑠);黒訪問済
5: while (Q が空でない) do begin
6:𝑣 ← Q.Dequeue();
7:𝑣 を出力する; // その頂点を処理
8:for each (𝑣の隣接頂点𝑢) do
9:if (状態[𝑢]=白) then10:
状態[𝑢] ← 赤;
最悪/平均の
11:
Q.Enqueue(𝑢);
時間計算量は O(𝑛 + 𝑚)
12:
end if(𝑛: 頂点数，𝑚: 辺の本数)13:
状態[𝑣] ← 黒;
14: end while
13幅優先探索の計算例
a

問い： 右図の隣接リスト表現で与えられるグラフ
𝐺のBFSで出力される頂点リストを与えよ．
解答： a, b, f, g, h, d, c, ed
ステップ

訪問
頂点𝑣

0
1
2
3
4
56
7
8

abfghdce𝑣の隣接頂点リスト

キューQの内容b, f, g, hd, c, fnullnull
gnulld, enull

ab, f, g, hf, g, h, d, cg, h, d, ch, d, cd, cce-bc fehg

𝐺の隣接リスト表現
頂点
隣接リスト
ab, f, g, hbd, c, fcd, ed
nullenull
fnullgnullhg※ 下線は次に取り出される頂点．赤字は新たに追加された頂点．

14

深さ優先探索の考え方
基本的なアイデア• ソース（スタート地点となる頂点） 𝑠 から，未発見の頂点を優先的に可能な限り深い方へと探索する
a特長bh• メモリ使用量が少なくなることが多いd• 特に再帰版は実装が簡単
gc fe

アルゴリズムの動き

1. ソース 𝑠 を一つ決め，スタック（LIFO）に入れる
2. スタックから一つ頂点 𝑣 を取り出して 𝑣 をたどる
3. 𝑣の隣接頂点のうち未訪問（かつ未発見）の頂点をすべてスタックに入れる
15
4. スタックが空になるまで２と３を繰り返す

深さ優先探索アルゴリズム DFS

幅優先探索 (BFS) と見比べて、変わった場所は？

Procedure DFS (𝐺: グラフ)
頂点𝑣の状態の意味
1: for each 𝑣 ∈ 𝑉 do 状態[𝑣] ← 白;
色意味
2: Q ← 空のスタック;白未訪問
3: 状態[𝑠] ← 赤; // ソース𝑠は適当な頂点
赤発見済
4: Q.Push(𝑠);黒訪問済
5: while (Q が空でない) do begin
6:𝑣 ← Q.Pop();
7:𝑣 を出力する; // その頂点を処理
8:for each (𝑣の隣接頂点𝑢) do
9:if (状態[𝑢]=白) then10:
状態[𝑢] ← 赤;
最悪/平均の11:Q.Push(𝑢);
時間計算量は O(𝑛 + 𝑚)
12:
end if(𝑛: 頂点数，𝑚: 辺の本数)13:
状態[𝑣] ← 黒;
14: end while16

深さ優先探索の計算例
a問い： 右図の隣接リスト表現で与えられるグラフ
𝐺のDFSで出力される頂点リストを与えよ．
解答： a, h, g, f, b, c, e, dd
ステップ

訪問
頂点𝑣

012345678ahgfbced𝑣の隣接頂点リスト

b, f, g, hg
null
null
d, c, fd, e
null
null

スタックQの内容

ab, f, g, hb, f, gb, fbd, cd, ed-bhc fe

頂点abcdefgh※ 下線は次に取り出される頂点．赤字は新たに追加された頂点．

g

隣接リスト
b, f, g, hd, c, fd, enull
null
null
nullg
17深さ優先探索アルゴリズム DFS （再帰版）
Procedure DFS (𝐺: グラフ)
頂点𝑣の状態の意味
1: for each (𝑣 ∈ 𝑉) do 状態[𝑣] ← 白;
色意味
2: 𝑠 ←ソース頂点; // ソース𝑠は適当な頂点
白未訪問
3: Visit(𝑠);// 再帰手続きの開始
黒Procedure Visit(𝑣: 頂点)
1: 𝑣 を出力する;
2: 状態[𝑣] ← 黒;
3: for each (𝑣の隣接頂点𝑢) do
4:
if (状態[𝑢]=白) then5:
Visit(𝑢);//再帰呼び出し6:
end if
6: end for

訪問済

このアルゴリズム場合，隣接リストの順に未訪問の頂点を可能な限り深く探索するので，スタックを使うアルゴリズムとは出力順が異なる点に注意【練習】 先の例のグラフ𝐺に対してどのような順番で出力されるか？

18