深さ優先探索とは？ふかさゆうせんたんさく
深さ優先探索とは、グラフや木をたどるとき、行けるところまで進み、行き止まりで1つ戻って別の枝を試す探索方法。スタックまたは再帰呼出しで実装する。全経路の列挙や、たどった先で既訪問の頂点に戻る閉路の検出に向き、ネットワークのトポロジを機械的に点検する処理の土台になる。
最終更新：2026-10-06
ネットワークSPを最短で暗記・合格する →背景
網の形が正しいかを目で確認できるのは、装置が数台のうちだけである。拠点や仮想スイッチが増えると、意図しない経路や閉路は図を眺めても見つからない。頂点と辺の集合として扱い、決まった順序で機械的にたどる手続きに落としてしまえば、規模が増えても同じ手順で点検できる。深さ優先は、そのもっとも基本的なたどり方にあたる。
具体例
構成管理台帳の接続情報から、装置を頂点・リンクを辺としてたどり、まだ戻っていない頂点へ再び到達したらそこに閉路があると分かる。NetBox に登録した接続を書き出してこの探索にかければ、STPで止まっているだけの余計な経路を、設計変更の前に洗い出せる。
試験での引っ掛け
幅優先探索との取り違えが最頻出で、深さ優先はスタック、幅優先はキューを使う。深さ優先で最初に見つかった経路は最短とは限らず、辺の重みが等しいグラフで最短を保証するのは幅優先のほう。訪問済みの印を付けないと、閉路のあるグラフで同じ頂点を無限にたどる。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。