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

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

離散数学 木の巡回

再帰呼び出しによる二分木の巡回 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

再帰呼び出しによる二分木の巡回 行きがけ： 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

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

二分木の巡回 (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

木の巡回 (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

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

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

離散数学 疑似コード 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); }

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

動作 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

閉路がある場合の動作 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

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

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

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

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

無向グラフに対する閉路の検出 閉路：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

離散数学 無向グラフの閉路の検出（修正前） 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!”; // (*) }

バグ 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

離散数学 無向グラフの閉路の検出（修正後） 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!”; // (*) }

閉路がある場合の動作 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

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

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

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

無向グラフに対する閉路の検出 閉路： 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

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

有向グラフ向け修正 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

離散数学 有向グラフ用閉路の検出 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; }

バグではない 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 ?

閉路がある場合の動作 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

閉路でない場合の動作 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

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

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

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

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

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

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

トポロジカル・ソートの応用例 例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

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

離散数学 トポロジカル・ソートの疑似コード 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 }

証明 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 になる

離散数学 まとめ

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

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