競プロ覚書：深さ優先探索，幅優先探索 まとめ - pyてよn日記

概要 深さ優先探索 アルゴリズムと計算量 実装 問題 幅優先探索 アルゴリズムと計算量 実装 フレームワーク BFS の実装例：迷路の探索 問題 蛇足：再帰による DFS のイメージに関して思ったこと 終わりに 参考 基本的な全探索アルゴリズムである深さ優先探索，幅優先探索について，螺旋本を読んでまとめました．チートシートでは無いですが，この記事を見たら「なんとなく実装までいけそう」という記事を目指しました．「丁寧に一から解説」という記事ではないのでご注意ください． この間の ABC119 の C 問題で，書けるようになった「つもり」の深さ優先探索を実装することができなかったので，猛省しながら書き上げました． 概要 DFS，BFS それぞれについて， アルゴリズムの概要 実装の大枠 を解説しています． DFS に関しては，具体的な問題ではなく，実装のフレームワーク（のようなもの）に焦点を当