DFS（深さ優先探索） とは？

BFSが浅いところを全部見てから深くに行くのに対して、DFSは一つの道をとことん深く進んで、行き止まりになったら一つ前に戻って別の道を試す方式だよ。

その通り！実はこの方法、スタックというデータ構造を使うか、関数の再帰呼び出しで自然に実装できるんだ。プログラムの関数呼び出し自体がスタックだから、再帰と相性抜群なんだよ。

すべてのパターンを列挙したいとき、グラフにループがあるか調べたいとき、あとはトポロジカルソートと呼ばれるタスクの依存関係を整理する処理に使うね。

そうだよ。BFSは同じ深さのノードを全部キューに入れるから、幅が広いグラフだとメモリが爆発しがち。DFSは今進んでいる経路のノードだけ覚えておけばいいから、深さ分のメモリで済むんだ。

最短経路を保証しないのが最大の弱点だね。あと、無限に深い経路があると永遠に戻ってこられないこともある。その対策として深さに上限を設ける「反復深化探索」というテクニックもあるよ。BFSのメモリ効率とDFSの省メモリを両立した賢い方法なんだ。