深さ優先探索と幅優先探索の使い分け

探索における手法に深さ優先探索幅優先探索がある。 最強最速アルゴリズマー養成講座によると、問題を解答するにあたって、どちらの探索手法を使えばよいかの指針は以下の通り。 ※どちらを使ってもよい場合もあるので注意すること。

深さ優先探索を使うケース

  • 全通りを列挙し、結果をまとめる必要がある場合。
  • 文字列などを探索するときに、「辞書順最小(辞書の並び順で、いちばん最初にくるもの)」であることが求められている場合。

幅優先探索を使うケース

  • 始点から最も近いものを求めたいケース。
  • 探索範囲自体は広いものの、ある程度近くに求めたい解が存在することがわかっているケース。
  • 探索範囲が広く、深さ優先探索ではスタックが大量に使われてしまう場合。