グラフ探索

離散数学
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.