過去問クラブ 学ぶ、わかる、つづく。
ログイン
用語解説

深さ優先探索

一つの枝を深くたどる

深さ優先探索は、木やグラフで、ある方向へ進めるところまで進み、その後に戻って別の方向を調べる探索方法です。DFSと略します。再帰呼出しや明示的なスタックを使って実装できます。迷路で一つの道を進み、行き止まりになったら分岐へ戻る考え方に似ています。

Pythonによる例

def depth_first(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
        for neighbor in reversed(graph.get(vertex, [])):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

後に積んだ要素から取り出すスタックを使い、未訪問の隣接頂点を調べる例です。

訪問済みの管理

一般のグラフには循環があるため、同じ頂点を何度もたどると終了しない場合があります。訪問済みの集合を持つことで、それを防ぎます。木の場合でも親へ戻る辺をどのように扱うかなど、入力の表現を確認します。探索の順序は隣接頂点を並べる順にも左右され、DFSなら常に一つの決まった列になるわけではありません。

利用する場面

連結性の確認、閉路の検出、木の走査、条件に合う組合せの探索などに関係します。ただし、最初に見つかった経路が最短とは限りません。辺の本数が最小の経路を求めたいときは、幅優先探索などの条件を検討します。探索方法と、解として求める性質を結び付けることが重要です。

試験での要点

再帰で記述された場合は、呼出しの前に記録するか、戻った後に記録するかでも出力順が変わります。スタックの内容と訪問済みの頂点を別々に書くと、処理を追いやすくなります。隣接リストで各頂点と辺を適切に一度ずつ調べる探索はO(V+E)ですが、同じ状態を繰り返す組合せ探索全体まで同じ計算量と考えてはいけません。

参考資料

内容確認日:2026-11-13

この言葉を含む問題を探す

この用語に関連する問題

1問

用語一覧

10件

ファイアウォール

通信の通過を制御する ファイアウォールは、定めた方針に基づいて通信を許可したり拒否したりする仕組みです。組織のネットワーク境界だけでなく、端末自身や内...

ファイブフォース

ファイブフォースは、マイケル・ポーターが提唱したマーケティングフレームワーク 以下の5つの力を分析することで環境の分析に役立てることができる。 新規参...

フィッシング

正規の相手を装って情報を奪う フィッシングは、実在する組織などを装い、偽のサイトや連絡を通じて認証情報や決済情報などを入力させる手口です。電子メールだ...

プライベートIPアドレス

組織内で使うアドレス プライベートIPアドレスは、私的なネットワーク内で利用するために予約されたIPアドレスです。IPv4では、10.0.0.0/8、172.16.0.0/12、192....

ブラックボックステスト

外から見える仕様に基づいて調べる ブラックボックステストは、対象の内部構造ではなく、仕様や外部から観測できる振舞いに基づいてテストを設計する考え方です...

ブルートフォース攻撃

候補を繰り返し試す ブルートフォース攻撃は、考えられる候補を多数試し、パスワードや鍵などを見つけようとする攻撃です。総当たり攻撃とも呼びます。利用でき...

プロキシサーバー

通信を仲介するサーバー プロキシサーバーは、クライアントと通信先の間に入り、要求や応答を中継するサーバーです。利用者側の代理として外部へ接続する構成と...

副問合せ

問い合わせの中で問い合わせる 副問合せは、SQL文の中に埋め込まれた別の問い合わせです。サブクエリーとも呼びます。別の集計結果と比較したり、条件に合う関連...

深さ優先探索

一つの枝を深くたどる 深さ優先探索は、木やグラフで、ある方向へ進めるところまで進み、その後に戻って別の方向を調べる探索方法です。DFSと略します。再帰呼出...

負荷分散

処理を複数の資源へ振り分ける 負荷分散は、利用者からの要求などを複数のサーバーへ振り分け、一台への集中を避ける仕組みです。ロードバランシングとも呼びま...