FEアルゴリズムとプログラミング · アルゴリズム

深さ優先探索

Depth-First Search

ふかさゆうせんたんさく

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

共有:

他の資格での定義

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

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

Past Exams

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

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

グラフや木構造において、現在のノードに隣接する全てのノードを先に探索してから次の深さに進む探索アルゴリズム。キューを使って実装される。最短経路の探索に適する。BFSと略される。

最適化問題を部分問題に分割し、各部分問題の解を記憶しながら全体の最適解を求めるアルゴリズム設計手法。重複する部分問題を再計算せずに済むため効率的。ナップサック問題や最短経路問題に応用される。

直前の2項を足した値が次の項になる数列。1,1,2,3,5,8,13…と続く。再帰処理の例題として頻出で、素直に再帰で書くと同じ計算を何度も繰り返すため、途中結果を保存する動的計画法で高速化できる。

アルゴリズムの実行に必要な計算ステップ数を入力サイズの関数として表したもの。オーダー記法O(n)で表現され、O(1)、O(log n)、O(n)、O(n log n)、O(n²)などがある。アルゴリズムの効率を評価する基本指標。

隣接する要素を比較して交換を繰り返すことでデータを整列するアルゴリズム。平均・最悪計算量ともにO(n²)で効率は良くないが、アルゴリズムが単純で理解しやすい。安定ソート。

未整列部分から最小値（または最大値）を見つけて先頭に移動する操作を繰り返す整列アルゴリズム。計算量はO(n²)で、交換回数が少ないがデータ比較は多い。不安定ソート。