深さ優先探索とは？ふかさゆうせんたんさく
深さ優先探索とは、木やグラフをたどるときに、進める限り1本の枝を奥まで進み、行き止まりで1つ手前に戻って未探索の枝を試す探索アルゴリズム。スタックまたは再帰呼出しで実装でき、経路の列挙・到達可能性の判定・ファイルシステムのような階層構造の全走査に向く。閉路のあるグラフでは訪問済みの印を付けないと同じ頂点を無限にたどる。
最終更新：2026-10-06
情報処理安全確保支援士を最短で暗記・合格する →背景
ネットワークやディレクトリ構造のように枝分かれする対象を「漏れなく1回ずつ」たどるには、どこまで見たかを覚える規則が要る。深さ優先は覚える量が現在の経路ぶんだけで済むため、メモリが限られる環境や階層の深い構造で使いやすい。支援士では直接の出題は少ないが、ウイルススキャンの全走査や攻撃経路の分析ツールがこの動きをしており、アルゴリズムの基礎として午前Iに残る。
具体例
Linuxのfindコマンドはディレクトリを深さ優先でたどり、/home/a/docs/…と奥まで降りてから隣のディレクトリへ移る。Windows Defenderのフルスキャンも同じ順序でファイルを検査する。攻撃経路を洗い出すツールが「侵入点→到達できるホスト→さらにそこから到達できるホスト」と掘り進めるのも深さ優先の応用である。
試験での引っ掛け
幅優先探索との取り違えが最頻出。深さ優先はスタック（後入れ先出し）、幅優先はキュー（先入れ先出し）で動く。深さ優先で最初に見つけた経路は最短とは限らず、辺の重みが無いグラフで最短を保証するのは幅優先。シンボリックリンクによる循環を検知しないと無限ループになる点も、find の -L オプションでの実害として覚えておく。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。