A-1アルゴリズム・プログラミング · アルゴリズム

深さ優先探索

Depth-first Search

ふかさゆうせんたんさく

グラフや木で、ある頂点から進めるところまで深く進み、行き止まりになったら一つ前に戻って別の経路を進むことを繰り返して、すべての頂点を訪問する探索方法。スタックや再帰を使って実現する。

共有:

他の資格での定義

グラフや木構造において、できるだけ深い方向に進んでから戻る探索アルゴリズム。スタックを使って実装される。迷路の解法や経路探索などに使用される。DFSと略される。

グラフや木構造を探索する際、可能な限り深い方向に進み、行き止まりになったら戻って別の枝を探索するアルゴリズム。スタック（再帰呼出し）を用いて実装される。迷路探索やトポロジカルソートに利用。

Past Exams

過去問で 3 回出題（応用情報技術者試験 3）

出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。「選択肢」は、問題文ではなく選択肢に出たものです。用語名で照合しているため、関係の薄い問題が含まれることがあります。