こんにちは、KIYONOエンジニアです。
私からは定期的に「アルゴリズムシリーズ」を投稿していこうと思います。
以前、自社アプリ「MAGNET SFA」のパフォーマンス改善に取り組んだ際、計算量やデータの辿り方の理解が実装改善に直結する経験がありました。
その経験から開発におけるアルゴリズム意識の大切さを感じたので紹介したいと思います。
第1回は、その中でも特によく登場する DFS（深さ優先探索） について最近学んだので取り上げます。
アルゴリズムとは何か
アルゴリズムとは、問題を解決するための手順や考え方のことです。
プログラムは最終的に「手順の集合」なので、
- どの順番で
- どの条件で
- どこまで処理するか
を整理したものがアルゴリズムだと言えます。
その中でも「探索アルゴリズム」は、
- データ構造の中をどう辿るか
- 条件に合うものをどう見つけるか
という場面で頻繁に登場します。
DFS（深さ優先探索）とは
DFS（Depth First Search）は、深さ優先探索と呼ばれる探索アルゴリズムです。
特徴を一言で言うと、
行けるところまで深く進み、行き止まりになったら戻る
木構造やグラフ構造に対して使われることが多く、
「一つのルートを最後まで調べる」ことを優先します。
DFSの基本的な考え方
DFSの動きはとてもシンプルです。
- 今いる地点を処理する
- 次に進める場所があれば進む
- もう進めなければ一つ前に戻る
- これを繰り返す
この「戻る」という動きが重要で、再帰（recursive）な処理と非常に相性が良いです。
DFSが使われる場面
DFSは競技プログラミングだけでなく、Webアプリ開発やツールの裏側でも自然に登場します。
代表的には次のような場面です。
- カテゴリツリーや組織図など、階層構造（木構造）の全探索
- フォルダ・ディレクトリ構造など、深いネストを持つ構造の走査
- 迷路やグラフで、目的地に到達できるか（存在確認）を判定する
- 依存関係の探索や循環検出など、グラフ構造の検査
- 組み合わせ生成・バックトラッキングなど、探索して戻る必要がある問題
コードで見るDFSの例
ここでは、最もシンプルな「再帰DFS」を紹介します。
グラフ（隣接リスト）を受け取り、訪問済みを管理しながら深く探索していきます。
def dfs(graph, visited, node):
if node in visited:
return
visited.add(node)
print(node)
for next_node in graph.get(node, []):
dfs(graph, visited, next_node)
graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": [],
"D": [],
"E": []
}
visited = set()
dfs(graph, visited, "A")
出力イメージ
A
B
D
E
C
「A→B→D」と深く進み、行き止まりになったら戻って「E」へ、最後に「C」を探索しています。
この “深く進んで戻る” 挙動がDFSの本質です。
まとめ
- DFSは「深く進んで、行き止まりなら戻る」探索アルゴリズム
- 木構造・グラフ構造・ネストが深いデータを扱う場面で登場しやすい
- 再帰で直感的に書ける一方、訪問済み管理が重要
ここまで読んでいただきありがとうございました！
