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

BFSが始点から浅いところを順に調べるのに対して、DFSは未訪問の隣接頂点へできるだけ深く進むよ。先へ進めなくなったら戻り、まだ調べていない枝へ進むんだ。

そうだね。再帰呼び出しや、後入れ先出しのスタックで実装できる。グラフに同じ頂点へ戻る経路があるときは、訪問済みかどうかも記録して、同じ場所を際限なく調べないようにするんだ。

グラフのサイクル検出や、閉路のない有向グラフを依存関係に沿って並べるトポロジカルソートなどに使えるよ。通常のDFSは頂点を訪問する方法で、それだけで全経路を列挙するわけではない。経路の列挙には、経路ごとの状態管理などを組み合わせるんだ。

いつでもそうとは限らないよ。広い木ではDFSの探索用スタックがBFSの待ち行列より小さくなる場合があるけれど、深い探索ではスタックが大きくなる。グラフでは頂点数に応じた訪問済み情報も必要なので、経路の深さだけで全体のメモリは決まらないんだ。

最初に見つけた経路が最短とは限らないよ。探索が非常に深いと、再帰呼び出しの上限なども問題になる。深さに上限を設けたり明示的なスタックを使ったりする方法はあるけれど、目的に合う探索方法と終了条件を決める必要があるんだ。