離散数学 08. グラフの探索 五島.

Presentation on theme: "離散数学 08. グラフの探索 五島."— Presentation transcript:

1 離散数学 08. グラフの探索 五島

2 頂点の探索 頂点の探索： 「ある頂点から到達可能な頂点をすべて発見する」という手続き
離散数学 頂点の探索 頂点の探索： 「ある頂点から到達可能な頂点をすべて発見する」という手続き 以下のような，様々な問題が 頂点の探索 の応用で効率的に解ける： ある頂点から到達可能な頂点の列挙 （強）連結成分へ分解 無向グラフの各連結成分の全域木を（ひとつ）見つける 閉路の検出 DAG のトポロジカル・ソート

3 離散数学 木の巡回

4 再帰呼び出しによる二分木の巡回 call call visit (int u) { if (g.left(u))
離散数学 再帰呼び出しによる二分木の巡回 call 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) { if (g.left(u)) visit(g.left(u)); if (g.right(u)) visit(g.right(u)); } return 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)); } c b a d e

5 再帰呼び出しによる二分木の巡回 行きがけ： call 直後 call visit (int u) { if (g.left(u))
離散数学 再帰呼び出しによる二分木の巡回 行きがけ： call 直後 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) { if (g.left(u)) visit(g.left(u)); if (g.right(u)) visit(g.right(u)); } return 帰りがけ： return 直前 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)); } 行きがけ c b a d 帰りがけ e

6 巡回の順序 木の巡回順序： 頂点の処理順序 行きがけ順 (pre-order) 通りがけ順 (in-order) （二分木のみ）
離散数学 巡回の順序 木の巡回順序： 頂点の処理順序 行きがけ順 (pre-order) 通りがけ順 (in-order) （二分木のみ） 帰りがけ順 (post-order) 頂点を訪れる (visit) 順番は変わらない が， 頂点を処理する順番が変わる 処理： コードでは頂点番号の表示 (print)．

7 二分木の巡回 (binary tree traversal)
離散数学 二分木の巡回 (binary tree traversal) 行きがけ順 (pre-order) 通りがけ順 (in-order) 帰りがけ順 (post-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); } 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); } 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; } 3 1 1 2 2 3 4 3 2 1 4 7 6 5 4 5 6 6 7 7 5

8 木の巡回 (tree traversal) 行きがけ順 (pre-order) 帰りがけ順 (post-order)
離散数学 木の巡回 (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 1 2 4 4 2 5 3 1 9 7 5 6 8 8 6 9 7

9 離散数学 グラフの深さ優先探索

10 深さ優先探索 深さ優先探索 (depth first search: DFS) 入力： グラフ G と開始点 s 目的：
離散数学 深さ優先探索 深さ優先探索 (depth first search: DFS) 入力： グラフ G と開始点 s 目的： s から到達可能な頂点をすべて見つける 以下のコードでは，頂点を一度ずつ print

11 離散数学 疑似コード enum State {unvisited, visiting}; State state[N]; visit(int u, Graph g); 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); } visit (int u, Graph g) { state[u] = visiting; print u; foreach (int v in g.adjacents(u) ) if (state[v] == unvisited) visit(v, g); }

12 離散数学 visit() の説明 visit (int u, Graph g) { state[u] = visiting; print u; foreach (int v in g.adjacents(u) ) if (state[v] == unvisited) visit(v, g); } 行きがけに， visiting にし， 表示． g.adjacents(u) のそれぞれに対し， unvisited なら visit()

13 動作 a a a a a b b b b b c d c d c d c d c d > a > ab > ab
離散数学 動作 visit(a) visit(a) visit(a) visit(a) visit(a) a a a a a unvisited ? visit(b) visit(b) visit(b) visit(b) visit(b) b b b b b visit(c) visit(c) visit(c) ? c d c d c d c d c d > a > ab > ab > abc > abc visit(a) visit(a) visit(a) visit(a) a a a a : unvisited a visit(b) visit(b) visit(b) visit(b) : visiting b b b b a : visited visit(d) visit(d) visit(d) a ? c d c d c d c d > abc > abcd > abcd > abcd

14 閉路がある場合の動作 a a a b b b c d c d c d > abcd > abcd > abcd
離散数学 閉路がある場合の動作 visit(a) visit(a) visit(a) a a a visit(b) visit(b) visit(b) b b b unvisited ? visit(c) visit(c) visit(c) c d c d c d visit(d) visit(d) visit(d) > abcd > abcd > abcd : unvisited a : visiting a : visited a

15 離散数学 無向グラフの場合の挙動 3 1 4 8 7 6 9 5 2 s

16 全頂点探索の計算量 時間計算量 : O(n + m) n： 頂点数，m： 辺数 空間計算量: O(n) 配列 visited[] の大きさ
離散数学 全頂点探索の計算量 時間計算量 : O(n + m) n： 頂点数，m： 辺数 空間計算量: O(n) 配列 visited[] の大きさ

17 離散数学 無向グラフの閉路 と 全域木 の検出

18 全域木 (spanning tree) 全域木（spanning tree，スパニング・トゥリー，「張る木」）：
離散数学 全域木 (spanning tree) 全域木（spanning tree，スパニング・トゥリー，「張る木」）： ある無向連結グラフの部分グラフで， 親グラフの全頂点を含み， 木（非循環）であるもの 非連結にならないように，閉路を切断 できればよいが… 1 4 1 2 5 2 6 7 3 6 3 4 5 7

19 無向グラフに対する閉路の検出 閉路：a1  a2  …  am  a1 a1 ： s から始めて，最初に visit()．
離散数学 無向グラフに対する閉路の検出 閉路：a1  a2  …  am  a1 a1 ： s から始めて，最初に visit()． visit(s) ⇒…⇒ visit(a1) ⇒visit(a2) ⇒ …⇒ visit(am) の visit(am) 内で state[a1] == visiting 閉路が存在する am  a1 は，全域木に含めない s a1 visiting ? am a2 visit(am) a5 a3 a4

20 離散数学 無向グラフの閉路の検出（修正前） enum State {unvisited, visiting}; State state[N]; visit(int u, Graph g); 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); } visit (int u, Graph g) { state[u] = visiting; print u; foreach (int v in g.adjacents(u) ) if (state[v] == unvisited) visit(v); else // if (state[v] == visiting) print “cycle found!”; // (*) }

21 バグ w → u に対して， visit(w) から visit(u) が呼ばれたとき w ∈ adjacent(u)
離散数学 バグ w → u に対して， visit(w) から visit(u) が呼ばれたとき w ∈ adjacent(u) state[w] != unvisited u → w を閉路として検出！ 修正： w を（処理対象から）除外 visit(w) から visit(u) を呼ぶとき， 引数で w を渡す s visit(w) w visit(u) !unvisited u !unvisited

22 離散数学 無向グラフの閉路の検出（修正後） enum State {unvisited, visiting}; 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] = visiting; print u; foreach (int v in g.adjacents(u) ) if (v != w) if (state[v] == unvisited) visit(v, u, g); else // if (state[v] == visiting) print “cycle found!”; // (*) }

23 閉路がある場合の動作 a a a b b b c d c d c d > abcd > abcd > abcd
離散数学 閉路がある場合の動作 visit(a, ?) visit(a, ?) visit(a, ?) a a a visit(b, a) visit(b, a) visit(b, a) b b b unvisited ? visit(c, b) visit(c, b) visit(c, b) c d c d c d visit(d, c) visit(d, c) visit(d, c) > abcd > abcd > abcd v == w ? : unvisited a : visiting a : visited a

24 全域木 (spanning tree) 全域木（spanning tree，スパニング・トゥリー，「張る木」）：
離散数学 全域木 (spanning tree) 全域木（spanning tree，スパニング・トゥリー，「張る木」）： ある無向連結グラフの部分グラフで， 親グラフの全頂点を含み， 木（非循環）であるもの 非連結にならないように，閉路を切断 できればよいが… 1 4 1 2 5 2 6 7 3 6 3 4 5 7

25 全域木の検出 s から始まる visit() の再帰呼び出しのグラフ ⇒ （s を含む連結成分の）全域木 証明：
離散数学 全域木の検出 s から始まる visit() の再帰呼び出しのグラフ ⇒ （s を含む連結成分の）全域木 証明： visit() できるのは，s を含む連結成分 閉路を発見すると，その先には visit() しない visit() の再帰呼び出しからなるグラフには閉路がない ⇒ 木

26 離散数学 有向グラフの閉路の検出

27 無向グラフに対する閉路の検出 閉路： a1  a2  …  am  a1 a1 ： s から始めて，最初に visit()．
離散数学 無向グラフに対する閉路の検出 閉路： a1  a2  …  am  a1 a1 ： s から始めて，最初に visit()． visit(s) ⇒…⇒ visit(a1) ⇒visit(a2) ⇒ …⇒ visit(am) の visit(am) 内で state[a1] == visiting 閉路が存在する am  a1 は，全域木に含めない s a1 visiting ? am a2 visit(am) a5 a3 a4

28 無向 / 有向グラフに対する閉路の検出 無向グラフの場合： unvisited でなく visiting なら閉路 有向グラフの場合：
離散数学 無向 / 有向グラフに対する閉路の検出 無向グラフの場合： unvisited でなく visiting なら閉路 有向グラフの場合： ⇒ ウソ s ① ② a1 visiting ? am a2 visit(am) a5 a3 a4

29 有向グラフ向け修正 visit(s) ⇒…⇒ visit(a1) ⇒visit(a2) ⇒ …⇒ visit(am) の
離散数学 有向グラフ向け修正 visit(s) ⇒…⇒ visit(a1) ⇒visit(a2) ⇒ …⇒ visit(am) の 探索中に a1 に到達したら閉路 探索中でなければ閉路でない 探索終了後の頂点を visited として区別 s ① ② a1 visiting ? am a2 visit(am) a5 a3 a4

30 離散数学 有向グラフ用閉路の検出 enum State {unvisited, visiting, visited}; State state[N]; 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); } visit (int u, Graph g) { state[u] = visiting; print u; foreach (int v in g.adjacents(u) ) if (state[v] == unvisited) visit(v, g); else if (state[v] == visiting) print “cycle found!”; // (*) state[u] = visited; }

31 バグではない w → u に対して， visit(w) から visit(u) が呼ばれたとき w ∈ adjacent(u)
離散数学 バグではない w → u に対して， visit(w) から visit(u) が呼ばれたとき w ∈ adjacent(u) state[w] != visiting u → w を閉路として検出！ ⇒ あってる s visit(w) w visiting ? visit(u) u visiting ?

32 閉路がある場合の動作 a a a b b b c d c d c d > abcd > abcd cycle found!
離散数学 閉路がある場合の動作 visit(a) visit(a) visit(a) a a a visit(b) visit(b) visit(b) b b visiting? b visit(c) visit(c) visit(c) c d c d c d visit(d) visit(d) visit(d) > abcd > abcd cycle found! > abcd cycle found! : unvisited a : visiting a : visited a

33 閉路でない場合の動作 a a a b b b c d c d c d > abc > abcd > abcd
離散数学 閉路でない場合の動作 visit(a) visit(a) visit(a) a a a visit(b) visit(b) visit(b) b b b visit(c) visit(c) visit(d) visit(d) c d c d c d visiting? > abc > abcd > abcd : unvisited a : visiting a : visited a

34 離散数学 連結成分への分解

35 無向グラフの連結成分への分解 s を含む連結成分： s から到達可能な全頂点（無向グラフの性質）
離散数学 無向グラフの連結成分への分解 s を含む連結成分： s から到達可能な全頂点（無向グラフの性質） s から始まる visit() で訪れた頂点の集合 証明： 基本的には，v in adjacents(u) なるすべての v に visit(v) する v in adjacents(u) なのに visit(v) しない v は，既に visit() したものだけ

36 有向グラフの場合 どの2つも一般には一致しない： s を含む強連結成分（の頂点の集合) ⊆ s から到達可能（な頂点の集合）
離散数学 有向グラフの場合 どの2つも一般には一致しない： 　 s を含む強連結成分（の頂点の集合) ⊆ s から到達可能（な頂点の集合） ⊆ s を含む連結成分（の頂点の集合） s を含む強連結成分 s s s を含む連結成分 sから到達可能

37 有向グラフの（強）連結成分への分解 連結成分への分解 辺の向きを無視した無向グラフを作り，それを連結成分へ分解すればよい 強連結成分への分解
離散数学 有向グラフの（強）連結成分への分解 連結成分への分解 辺の向きを無視した無向グラフを作り，それを連結成分へ分解すればよい 強連結成分への分解 少し難しい 省略（石畑の教科書参照）

38 離散数学 DAG のトポロジカル・ソート

39 DAG のトポロジカル・ソート 有向グラフの全頂点を一列に並べる v1, v2,..., vn
離散数学 DAG のトポロジカル・ソート 有向グラフの全頂点を一列に並べる v1, v2,..., vn ただし，vi * vj (i < j) * で表される半順序関係を包含す る全順序関係の構築 グラフに閉路がある？ ある (DCG)： 並べ方は存在しない ない (DAG)： 一通り以上 存在する c a b d f e a, b, c, d, e, f a, b, d, e, c, f a, b, d, c, e, f

40 トポロジカル・ソートの応用例 例1：論文 辺 a  b： 項目 b を説明するには a を事前に説明しておく必要がある
離散数学 トポロジカル・ソートの応用例 例1：論文 辺 a  b： 項目 b を説明するには a を事前に説明しておく必要がある トポロジカル・ソート： 項目を並べる順番 例2：式の評価（コンパイラ，etc） 頂点： 評価したい（値を求めたい）式の部分式 トポロジカル・ソート： 式を評価すべき順番（の逆順） * (a + b) * (a + b + c) *; +2; +1; a; b; c +1 +2 a b c

41 離散数学 巡回順序 と トポロジカル・ソート × 行きがけ順 × 左優先： *; +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) *; +2; +1; a; b; c +1 +2 a b c

42 離散数学 トポロジカル・ソートの疑似コード enum State {unvisited, visiting, visited}; State state[N]; queue q; visit (int u, Graph g); 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(); } visit (int u, Graph g) { state[u] = visiting; foreach (v in adjacents(u) ) if (state[v] == unvisited) visit(v, g); else if (state[v] == visiting) print “not a DAG!”; // (*) state[u] = visited; q.append(u); // add to tail }

43 証明 u  v とする 「u より v が先に visited になる」ことを言えばよい
離散数学 証明 u  v とする 「u より v が先に visited になる」ことを言えばよい 先に visited になる ⇒ 先に q.append() される ⇒ 後に出力される visit(u, ...) 中で… visited[v] == visiting DAG なので，起こり得ない（エラーで終了） visited[v] == visited すなわち， v はすでに visited になっている visited[v] == unvisited visit(v, ...) が実行され，u より v が先に visited になる

44 離散数学 まとめ

45 頂点の探索 頂点の探索： 「ある頂点から到達可能な頂点をすべて発見する」という手続き
離散数学 頂点の探索 頂点の探索： 「ある頂点から到達可能な頂点をすべて発見する」という手続き 以下のような，様々な問題が 頂点の探索 の応用で効率的に解ける： ある頂点から到達可能な頂点の列挙 （強）連結成分へ分解 無向グラフの各連結成分の全域木を（ひとつ）見つける 閉路の検出 DAG のトポロジカル・ソート

46 離散数学 次回 今回： 深さ優先探索 「行けるところまで行く」 次回： 深さ優先以外の探索 ⇒ 最短路，etc.