グラフ探索

離散数学
08. グラフの探索
五島
DATE :
離散数学
頂点の探索
 頂点の探索：
 「ある頂点から到達可能な頂点をすべて発見する」という手続き
 以下のような，様々な問題が頂点の探索の応用で効率的に解ける：
 ある頂点から到達可能な頂点の列挙
 （強）連結成分へ分解
 無向グラフの各連結成分の全域木を（ひとつ）見つける
 閉路の検出
 DAG のトポロジカル・ソート
離散数学
木の巡回
離散数学
再帰呼び出しによる二分木の巡回
call
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
call
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
return
c
b
a
d
e
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
離散数学
再帰呼び出しによる二分木の巡回
call
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
return
行きがけ
c
b
a
帰りがけ
e
d
行きがけ：
call 直後
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
帰りがけ：
visit (int u)
{ return 直前
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
visit (int u)
{
if (g.left(u))
visit(g.left(u));
if (g.right(u))
visit(g.right(u));
}
離散数学
巡回の順序
 木の巡回順序：頂点の処理順序
 行きがけ順 (pre-order)
 通りがけ順 (in-order) （二分木のみ）
 帰りがけ順 (post-order)
 頂点を訪れる (visit) 順番は変わらないが，
 頂点を処理する順番が変わる
 処理：コードでは頂点番号の表示 (print)．
離散数学
二分木の巡回 (binary tree traversal)
行きがけ順 (pre-order)
visit (int u, Graph g)
{
print u;
if (g.left(u))
visit(g.left(u), g);
if (g.right(u))
visit(g.right(u), g);
}
通りがけ順 (in-order)
visit (int u, Graph g)
{
if (g.left(u))
visit(g.left(u), g);
print u;
if (g.right(u))
visit(g.right(u), g);
}
3
帰りがけ順 (post-order)
visit (int u, Graph g)
{
if (g.left(u))
visit(g.left(u), g);
if (g.right(u))
visit(g.right(u), g);
print u;
}
1
2
1
2
4
1
3
3
4
7
6
5
5
6
7
2
4
6
7
5
離散数学
木の巡回 (tree traversal)
行きがけ順 (pre-order)
帰りがけ順 (post-order)
visit (int u, Graph g)
{
print u;
foreach (v in g.adjacent(u))
visit(v, g);
}
visit (int u, Graph g)
{
foreach (v in g.adjacent(u))
visit(v, g);
print u;
}
3
2
1
4
4
5
1
2
3
9
7
6
8
9
5
8
6
7
離散数学
グラフの深さ優先探索
離散数学
深さ優先探索
 深さ優先探索 (depth first search: DFS)
 入力：
 グラフ G と開始点 s
 目的：
 s から到達可能な頂点をすべて見つける
 以下のコードでは，頂点を一度ずつ print
離散数学
疑似コード
enum State {unvisited,
State state[N];
visit(int u, Graph g);
};
visit (int u, Graph g)
{
state[u] =
;
visit_all (Graph g)
{
for (int i = 0; i < N; i++)
state[i] = unvisited;
for (int i = 0; i < N; i++)
if (state[i] == unvisited)
visit(i);
}
print u;
foreach (int v in g.adjacents(u) )
if (state[v] == unvisited)
visit(v, g);
}
離散数学
visit() の説明
 行きがけに，
visit (int u, Graph g)
{
state[u] =
;
print u;
foreach (int v in g.adjacents(u) )
if (state[v] == unvisited)
visit(v, g);
}

にし，
 表示．
 g.adjacents(u) のそれぞれに対し，
 unvisited なら
 visit()
離散数学
動作
visit(a)
visit(a)
a
visit(a)
a
visit(b)
b
a
unvisited ?
visit(b)
visit(a)
a
visit(b)
b
d
c
b
d
d
c
> ab
> ab
> abc
visit(a)
visit(a)
visit(a)
visit(a)
visit(b)
b
b
> abc
d
?
b
> abcd
d
?
d
b
visit(d)
c
> abcd
c
d
> abc
visit(b)
visit(d)
c
visit(c)
a
visit(b)
visit(d)
c
a
visit(b)
b
visit(c)
c
a
visit(b)
b
>a
a
a
visit(b)
visit(c)
c
visit(a)
d
c
> abcd
d
a
: unvisited
a
:
a
: visited
離散数学
閉路がある場合の動作
visit(a)
visit(a)
a
visit(a)
a
visit(b)
a
visit(b)
b
visit(b)
b
visit(c)
visit(c)
c
d
visit(d)
> abcd
a
: unvisited
a
:
a
: visited
b
unvisited ?
visit(c)
c
d
visit(d)
> abcd
c
d
visit(d)
> abcd
離散数学
無向グラフの場合の挙動
8
1
3
9
7
2
6
0 s
5
4
離散数学
全頂点探索の計算量
 時間計算量 : O(n + m)
 n：頂点数，m：辺数
 空間計算量: O(n)
 配列 visited[] の大きさ
離散数学
無向グラフの閉路と全域木の検出
離散数学
全域木 (spanning tree)
 全域木（spanning tree，スパニング・トゥリー，「張る木」）：
 ある無向連結グラフの部分グラフで，
 親グラフの全頂点を含み，
 木（非循環）であるもの
 非連結にならないように，閉路を切断
 できればよいが…
1
2
3
6
4
5
7
1
4
2
5
3
6
7
離散数学
無向グラフに対する閉路の検出
 閉路：a1  a2  …  am  a1
 a1 ： s から始めて，最初に visit()．
 visit(s) ⇒…⇒ visit(a1) ⇒visit(a2) ⇒ …⇒ visit(am) の
 visit(am) 内で state[a1] ==
s
 閉路が存在する
 am  a1 は，全域木に含めない
? a1
am
a2
a5
a3
visit(am)
a4
離散数学
無向グラフの閉路の検出（修正前）
enum State {unvisited,
State state[N];
visit(int u, Graph g);
};
visit (int u, Graph g)
{
state[u] =
;
print u;
find_cycle_undir (Graph g)
{
for (int i = 0; i < N; i++)
state[i] = unvisited;
for (int i = 0; i < ; i++)
if (state[i] == unvisited)
visit(i, −1);
}
foreach (int v in g.adjacents(u) )
if (state[v] == unvisited)
visit(v);
else // if (state[v] ==
)
print “cycle found!”; // (*)
}
離散数学
バグ
 w → u に対して，
visit(w) から visit(u) が呼ばれたとき
s
 w ∈ adjacent(u)
 state[w] != unvisited
 u → w を閉路として検出！
 修正：
 w を（処理対象から）除外
 visit(w) から visit(u) を呼ぶとき，
引数で w を渡す
visit(w)
w
visit(u)
!unvisited
u
!unvisited
離散数学
無向グラフの閉路の検出（修正後）
enum State {unvisited,
State state[N];
visit(int u, int w, Graph g);
find_cycle_undir (Graph g)
{
for (int i = 0; i < N; i++)
state[i] = unvisited;
for (int i = 0; i < N; i++)
if state[i] == unvisited)
visit(i, −1, g);
}
};
visit (int u, int w, Graph g)
{
state[u] =
;
print u;
foreach (int v in g.adjacents(u) )
if (v != w)
if (state[v] == unvisited)
visit(v, u, g);
else // if (state[v] ==
)
print “cycle found!”; // (*)
}
離散数学
閉路がある場合の動作
visit(a, ?)
visit(a, ?)
a
a
visit(b, a)
a
visit(b, a)
b
visit(b, a)
b
visit(c, b)
c
visit(a, ?)
visit(c, b)
d
visit(d, c)
> abcd
a
: unvisited
a
:
a
: visited
c
b
unvisited ?
visit(c, b)
d
visit(d, c)
c
d
visit(d, c)
> abcd
> abcd
v == w ?
離散数学
全域木 (spanning tree)
 全域木（spanning tree，スパニング・トゥリー，「張る木」）：
 ある無向連結グラフの部分グラフで，
 親グラフの全頂点を含み，
 木（非循環）であるもの
 非連結にならないように，閉路を切断
 できればよいが…
1
2
3
6
4
5
7
1
4
2
5
3
6
7
離散数学
全域木の検出
 s から始まる visit() の再帰呼び出しのグラフ
 ⇒ （s を含む連結成分の）全域木
 証明：
 visit() できるのは，s を含む連結成分
 閉路を発見すると，その先には visit() しない
 visit() の再帰呼び出しからなるグラフには閉路がない ⇒ 木
離散数学
有向グラフの閉路の検出
離散数学
無向グラフに対する閉路の検出
 閉路： a1  a2  …  am  a1
 a1 ： s から始めて，最初に visit()．
 visit(s) ⇒…⇒ visit(a1) ⇒visit(a2) ⇒ …⇒ visit(am) の
 visit(am) 内で state[a1] ==
s
 閉路が存在する
 am  a1 は，全域木に含めない
? a1
am
a2
a5
a3
visit(am)
a4
離散数学
無向 / 有向グラフに対する閉路の検出
 無向グラフの場合：
 unvisited でなく
路
なら閉
①
s
②
 有向グラフの場合：
a1
?
 unvisited でなく
路
なら閉
am
a2
a5
a3
visit(am)
 ⇒ ウソ
a4
離散数学
有向グラフ向け修正
 visit(s) ⇒…⇒ visit(a1) ⇒visit(a2) ⇒ …⇒ visit(am) の
 探索中に a1 に到達したら閉路
 探索中でなければ閉路でない
 探索終了後の頂点を visited として区別
①
s
②
a1
?
am
a2
a5
a3
visit(am)
a4
離散数学
有向グラフ用閉路の検出
enum State {unvisited,
visited};
State state[N];
,
visit (int u, Graph g)
{
state[u] =
;
print u;
visit(int u, Graph g);
find_cycle_dir (Graph g)
{
for (int i = 0; i < N; i++)
state[i] = unvisited;
for (int i = 0; i < N; i++)
if (state[i] == unvisited)
visit(i);
}
foreach (int v in g.adjacents(u) )
if (state[v] == unvisited)
visit(v, g);
else if (state[v] ==
)
print “cycle found!”; // (*)
state[u] = visited;
}
離散数学
バグではない
 w → u に対して，
s
visit(w) から visit(u) が呼ばれたとき
 w ∈ adjacent(u)
visit(w)
w
 state[w] !=
visit(u)
 u → w を閉路として検出！
 ⇒ あってる
u
離散数学
閉路がある場合の動作
visit(a)
visit(a)
a
visit(a)
a
visit(b)
a
visit(b)
b
visit(b)
b
visit(c)
b
visit(c)
c
d
visit(d)
> abcd
a
: unvisited
a
:
a
: visited
visit(c)
c
d
c
d
visit(d)
visit(d)
> abcd
cycle found!
> abcd
cycle found!
離散数学
閉路でない場合の動作
visit(a)
visit(a)
a
visit(a)
a
visit(b)
visit(b)
b
visit(b)
b
visit(c)
visit(c)
c
a
d
> abc
a
: unvisited
a
:
a
: visited
c
> abcd
b
visit(d)
d
visit(d)
c
> abcd
d
離散数学
連結成分への分解
離散数学
無向グラフの連結成分への分解
 s を含む連結成分：
 s から到達可能な全頂点（無向グラフの性質）
 s から始まる visit() で訪れた頂点の集合
 証明：
 基本的には，v in adjacents(u) なるすべての v に visit(v) する
 v in adjacents(u) なのに visit(v) しない v は，既に visit() したものだけ
離散数学
有向グラフの場合
 どの2つも一般には一致しない：

s を含む強連結成分（の頂点の集合)
s を含む強連結成分
 ⊆ s から到達可能（な頂点の集合）
 ⊆ s を含む連結成分（の頂点の集合）
s
s
sから到達可能
s を含む連
結成分
離散数学
有向グラフの（強）連結成分への分解
 連結成分への分解
 辺の向きを無視した無向グラフを作り，それを連結成分へ分解すれば
よい
 強連結成分への分解
 少し難しい
 省略（石畑の教科書参照）
離散数学
DAG のトポロジカル・ソート
離散数学
DAG のトポロジカル・ソート
 有向グラフの全頂点を一列に並べ
る
c
 v1, v2,..., vn
 ただし，vi * vj (i < j)
 * で表される半順序関係を包含
a
b
d
e
する全順序関係の構築
 グラフに閉路がある？
 ある (DCG)：
 並べ方は存在しない
 ない (DAG)：
 一通り以上存在する
a, b, c, d, e, f
a, b, d, e, c, f
a, b, d, c, e, f
f
離散数学
トポロジカル・ソートの応用例
 例1：論文
 辺 a  b：項目 b を説明するには a を事前に説明しておく必要がある
 トポロジカル・ソート：項目を並べる順番
 例2：式の評価（コンパイラ，etc）
 頂点：評価したい（値を求めたい）式の部分式
 トポロジカル・ソート：式を評価すべき順番（の逆順）
*
(a + b) * (a + b + c)
+1
a
*; +2; +1; a; b; c
+2
b
c
離散数学
巡回順序とトポロジカル・ソート
× 行きがけ順
× 左優先： *; +1; a; b; +2; c
∵ +1 と +2 の順序が逆
○ 右優先： *; +2; c; +1; b; a
○ 帰りがけ順（の逆順）
○ 左優先： a; b; +1; c; +2; *
○ 右優先： c; b; a; +1; +2; *
*
(a + b) * (a + b + c)
+1
a
*; +2; +1; a; b; c
+2
b
c
離散数学
トポロジカル・ソートの疑似コード
enum State {unvisited,
, visited};
State state[N];
queue q;
visit (int u, Graph g)
{
state[u] =
;
visit (int u, Graph g);
foreach (v in adjacents(u) )
if (state[v] == unvisited)
visit(v, g);
else if (state[v] ==
)
print “not a DAG!”; // (*)
queuetopological_sort (Graph g)
{
for (int i = 0; i < n; i++)
state[i] = unvisited;
q.empty();
for (int i = 0; i < n; i++)
if (state[i] == unvisited)
visit(i, g);
return q.reverse();
}
state[u] = visited;
q.append(u); // add to tail
}
離散数学
証明
 u  v とする
 「u より v が先に visited になる」ことを言えばよい
 先に visited になる ⇒ 先に q.append() される ⇒ 後に出力される
 visit(u, ...) 中で…
 visited[v] ==
 DAG なので，起こり得ない（エラーで終了）
 visited[v] == visited
 すなわち， v はすでに visited になっている
 visited[v] == unvisited
 visit(v, ...) が実行され，u より v が先に visited になる
離散数学
まとめ
離散数学
頂点の探索
 頂点の探索：
 「ある頂点から到達可能な頂点をすべて発見する」という手続き
 以下のような，様々な問題が頂点の探索の応用で効率的に解ける：
 ある頂点から到達可能な頂点の列挙
 （強）連結成分へ分解
 無向グラフの各連結成分の全域木を（ひとつ）見つける
 閉路の検出
 DAG のトポロジカル・ソート
離散数学
次回
 今回：
 深さ優先探索
 「行けるところまで行く」
 次回：
 深さ優先以外の探索
 ⇒ 最短路，etc.

Download Report