参考文献
大槻兼資 著, 問題解決力を鍛える！アルゴリズムとデータ構造, 講談社, 2020
深さ優先探索 (DFS: Depth-First Search)
深さ優先探索とは
一通りずつ探索する手法。
参考文献では、虫食い算（筆算の一部を空白にしその部分の解を求める問題）を例に挙げられていた。
利用されるアルゴリズムの例(ChatGPTより)
- 連結成分の探索
→グラフ内の連結成分の探索 - トポロジカルソート
→有向非巡回グラフ(DAG: )のノードの順序づけ - 迷路の解法
→スタートからゴールまでの経路探索 - 2部グラフ判定
→グラフを2つのグループに分けられるかの探索 - 閉路検出
→有向グラフや無向グラフにおけるサイクルの有無の探索
幅優先探索 (BFS: Breadth-First Search)
幅優先探索
一通りずつ探索するのではなく、全通り一斉に探索する探索手法。
参考文献では迷路の最短経路の探索が例に挙げられていた。
利用されるアルゴリズムの例
- 無向グラフにおける最短経路探索
重みが全て1のグラフにおけるグラフ内の最短経路探索 - レベル順探索
- 木構造において階層ごとに処理を階層ごとに処理
- パズルの最小手数探索
その名の通り - webクローラー
深さを制限しながらwebのリンクを横に展開して探索する
結論
深さ優先探索：とりあえず問題を解く
幅優先探索：最短で解く方法を探す
このように解釈した。