DFSってBFSと何が違うの？
BFSが浅いところを全部見てから深くに行くのに対して、DFSは一つの道をとことん深く進んで、行き止まりになったら一つ前に戻って別の道を試す方式だよ。
迷路で壁にぶつかるまで進んで、ダメなら引き返す感じだね！
その通り！実はこの方法、スタックというデータ構造を使うか、関数の再帰呼び出しで自然に実装できるんだ。プログラムの関数呼び出し自体がスタックだから、再帰と相性抜群なんだよ。
どんなときにDFSを使うのがいいのかな？
すべてのパターンを列挙したいとき、グラフにループがあるか調べたいとき、あとはトポロジカルソートと呼ばれるタスクの依存関係を整理する処理に使うね。
BFSよりメモリが少なくて済むって本当？
そうだよ。BFSは同じ深さのノードを全部キューに入れるから、幅が広いグラフだとメモリが爆発しがち。DFSは今進んでいる経路のノードだけ覚えておけばいいから、深さ分のメモリで済むんだ。
DFSに弱点はあるの？
最短経路を保証しないのが最大の弱点だね。あと、無限に深い経路があると永遠に戻ってこられないこともある。その対策として深さに上限を設ける「反復深化探索」というテクニックもあるよ。BFSのメモリ効率とDFSの省メモリを両立した賢い方法なんだ。
