Depth First Search

最終更新日14 Mar 2015 12:05

実装の仕方

普通はstackで実装するが、

  • この頂点に関して何個目まで調べたか知りたい
  • 前後に何か処理を入れたい

場合は、再帰を利用するといい。

深さ優先探索に向いているもの

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


files

サポートサイト Wikidot.com