━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題15
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (グラフの幅優先探索アルゴリズム)

次の無向グラフの幅優先探索について考える．ただし，複数の候補から
未訪問の頂点を選ぶ時には，アルファベット順で早いものを優先すること．

        Ａ─Ｂ─Ｃ
        │　│　│
        Ｄ─Ｅ─Ｆ
        　　│　│
        Ｇ─Ｈ─Ｉ

(1) 頂点を探索の訪問順に並べた列を求めよ．
(2) 探索で得られるスパニング木を求めよ．

──────────────────────────────────────

●答 (グラフの幅優先探索アルゴリズム)

頂点列：
        Ａ, Ｂ, Ｄ, Ｃ, Ｅ, Ｆ, Ｈ, Ｉ, Ｇ

スパニング木：

        Ａ─Ｂ─Ｃ
        │　│　│
        Ｄ　Ｅ　Ｆ
        　　│　│
        Ｇ─Ｈ　Ｉ

[解説]

無向グラフに対して，有向グラフの探索や走査をする場合，
各辺について両方向に辺があるものと考えてアルゴリズムを使う．

幅優先探索(BFS)では，未訪問の隣接頂点を全て訪問することを，
頂点の訪問順に反復する．

スパニング木は，連結な(全頂点が辺でつながった)部分グラフのうち，
閉路がないものであり，探索で訪問した辺だけを残すことで得られる．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/