深さ優先探索（DFS）とは何ですか？

グラフやツリーを探索するアルゴリズムの一つで、行けるところまで深く進んでから引き返して別の道を探す方法。再帰やスタックで実装される。

深さ優先探索（DFS）のポイントは？

一つの経路を行き止まりまで深く探索してからバックトラックする。スタック（LIFO）または再帰で実装する。全探索・迷路生成・トポロジカルソートなどに活用。幅優先探索（BFS）と対になる基本的な探索手法

【ふかさゆうせんたんさく】

💡 行き止まりまで突き進んでから引き返す、一本道の冒険者

📌 このページのポイント

深さ優先探索のイメージ

ひよこ

深さ優先探索ってどう探すの？

ペンギン先生

迷路で壁に手をつけたまま進む方法をイメージしてみて。とにかく一方向に進み続けて、行き止まりになったら一歩戻って別の道を試す。これがDFSの基本だよ

ひよこ

どうやって実装するの？

ペンギン先生

一番簡単なのは再帰を使う方法だね。『今のノードを処理→隣接ノードそれぞれに対して再帰呼び出し』とするだけ。再帰を使わない場合はスタックに次に調べるノードを積んでいくよ

ひよこ

BFSとどっちを使えばいいの？

ペンギン先生

最短経路を求めるならBFS、パズルの全解列挙やグラフの連結成分の検出ならDFSが向いているよ。DFSはメモリ消費が少ないのも利点だね。BFSは同じ深さのノードを全部覚えるけど、DFSは今たどっている経路だけ覚えていればいいんだ

ひよこ

再帰が深すぎるとエラーになるって聞いたけど…

ペンギン先生

スタックオーバーフローだね。再帰呼び出しが深くなりすぎるとメモリが足りなくなる。その場合は明示的にスタックを使ったループ実装に切り替えるか、末尾再帰最適化ができる言語を使うといいよ

ひよこ

DFSならではの応用ってある？

ペンギン先生

トポロジカルソートと強連結成分の検出が代表的だよ。タスクの依存関係を整理したり、SNSのコミュニティを検出したりするのに使われるんだ。あとコンパイラの構文解析も実はDFS的な処理をしているよ

まとめ：ざっくりこれだけ覚えればOK！

「深さ優先探索」って出てきたら「一本道を突き進んで、行き止まりで引き返す探し方」と思えればだいたいOK！

📖 おまけ：英語の意味

「Depth-First Search」＝深さ優先探索

💬 「depth（深さ）」を「first（最初に）」探索するという名前で、とにかく深く潜っていくイメージだよ