━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ データ構造・アルゴリズム論 確認問題14 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
●問 (グラフの深さ優先探索アルゴリズム) 次の無向グラフの深さ優先探索について考える．ただし，複数の候補から 未訪問の頂点を選ぶ時には，アルファベット順で早いものを優先すること． Ａ─Ｂ─Ｃ │ │ │ Ｄ─Ｅ─Ｆ │ │ Ｇ─Ｈ─Ｉ (1) 頂点を探索の訪問順に並べた列を求めよ． (2) 探索で得られるスパニング木を求めよ． ────────────────────────────────────── ●答 (グラフの深さ優先探索アルゴリズム) (1) 訪問順の頂点列は次の通り． Ａ, Ｂ, Ｃ, Ｆ, Ｅ, Ｄ, Ｈ, Ｇ, Ｉ (2) スパニング木を元のグラフの部分グラフとして示したものは次の通り． Ａ─Ｂ─Ｃ │ Ｄ─Ｅ─Ｆ │ Ｇ─Ｈ─Ｉ 探索の始点Ａを根とする木として，次の形に表示しても良い． Ａ │ Ｂ │ Ｃ │ Ｆ │ Ｅ ／ ＼ Ｄ Ｈ ／ ＼ Ｇ Ｉ [解説] 深さ優先探索(DFS)では，指定の頂点を訪問後，未訪問の隣接頂点を 一つずつ選んで再帰的に探索する．未訪問の隣接頂点がなくなって それ以上進めなくなったら，進んできた経路を１段階戻って探索を続ける． (1)の解答の頂点の訪問順は，(2)の解答の下の木の先行順の走査の結果と 同じであることに注意する． スパニング木は，連結な(全頂点が辺でつながった)部分グラフのうち， 閉路がないものであり，探索で訪問した辺だけを残すことで得られる． なお，無向グラフに対して，有向グラフの探索や走査をする場合， 各辺について両方向に辺があるものと考えてアルゴリズムを使う． ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 授業のホームページ 山田 俊行 https://www.cs.info.mie-u.ac.jp/~toshi/