問題

グラフの探索アルゴリズムに関する記述として、適切なものはどれか。

ア）幅優先探索（BFS）は、探索の補助データ構造としてスタックを用い、深さ方向へ優先的に探索を進める。

イ）深さ優先探索（DFS）は、探索の補助データ構造としてスタック（または再帰呼び出し）を用い、一つの経路を行き着くところまで探索してから他の経路に戻る。

ウ）幅優先探索は、無向グラフにのみ適用可能であり、有向グラフには適用できない。

エ）幅優先探索と深さ優先探索は、同一のデータ構造（キュー）を用いる点で共通しているが、探索順序のみが異なる。

解答・解説を見る

正解： イ）

解説：

  • ア）幅優先探索（BFS）は、補助データ構造として「キュー」を用い、開始点から近い順（同じ深さのノードを先に）に探索を進めます。「スタックを用い深さ方向へ優先的に」という記述はBFSではなくDFSの特徴であり、誤りです。
  • イ）深さ優先探索（DFS）は、補助データ構造としてスタック（または関数の再帰呼び出しによる暗黙のスタック）を用い、一つの経路をできるところまで深く探索し、行き止まりに達したら直前の分岐点まで戻って別の経路を探索します。正解です。
  • ウ）幅優先探索は無向グラフだけでなく、有向グラフにも適用可能な汎用的な探索アルゴリズムです。「無向グラフにのみ適用可能」は誤りです。
  • エ）幅優先探索はキューを、深さ優先探索はスタックを用いるというように、使用する補助データ構造自体が異なります。「同一のデータ構造を用いる」は誤りです。

重要キーワード

用語説明
幅優先探索（BFS）キューを用いて近い順に探索するアルゴリズム
深さ優先探索（DFS）スタックや再帰を用いて経路を深く探索するアルゴリズム
キュー先入れ先出し（FIFO）のデータ構造
スタック後入れ先出し（LIFO）のデータ構造