用語比較
幅優先探索と深さ優先探索の違い｜調べる順番と最短経路の保証（G検定）
幅優先探索は、始点から1辺で行ける頂点、次に2辺で行ける頂点、というように、近い頂点から順に調べる探索です。深さ優先探索は、隣の頂点へ進める限り進み、行き止まりになってから別の道を調べる探索です。
二つを分けるのは、調べる順番です。その結果として、幅優先探索は辺の数が最少の経路（最短経路）を求められ、深さ優先探索は何らかの経路を見つけますが、それが最短とは限りません。
このページは、G検定の探索木の問題で、二つの探索の名前と特徴が入れ替わってしまう人を対象にしています。小さな例で調べる順を実際に追い、問題文のどこを見て選べばよいかを確認します。
この記事の根拠と出典
各セクションの見出しの下に、公式資料で確認した内容か編集部の整理かをラベルで示しています。 試験日・料金・申込条件・試験方式は変わることがあるため、申込前に公式サイトで確認してください。G検定の一次情報確認日: 2026-10-02。
結論
幅優先探索
始点に近い頂点から順に、1辺で行ける頂点、2辺で行ける頂点と調べる。調べ待ちの頂点をキュー（先に入れたものを先に取り出す入れ物）で持つ。始点から到達できる頂点への最短経路を求められる。
深さ優先探索
頂点に印を付け、隣接していて印のない頂点を再帰的に訪れる。始点から目的の頂点への何らかの経路を見つけるが、最短とは限らない。
違いを表で確認
| 比較軸 | 幅優先探索 | 深さ優先探索 |
|---|---|---|
| 調べる順番 | 始点に近い頂点から順に（1辺、2辺、…） | 進める限り先へ進み、行き止まりで戻る |
| 調べ待ちの持ち方 | キュー（先入れ先出し） | 再帰（呼び出しの中で次の頂点へ進む） |
| 最短経路 | 求められる（辺の数が最少の経路） | 見つかる経路は最短とは限らない |
| 探索木で見ると | 上の階層から横に順に調べる | 一つの枝を下まで調べてから隣の枝へ |
| 区別の手がかり | 近い順、階層ごと、キュー、最短 | 深く、再帰、行き止まり、後戻り |
G検定の学習に使う書籍（Amazon）
試験範囲を通して読むときの1冊です。読んだ章は、このサイトの章別問題で確かめられます。
どこで迷っているかを切り分ける
幅と深さのどちらがどちらか、名前で迷う人
幅優先は、同じ距離にある頂点を横に広くそろえてから、次の距離へ進みます。深さ優先は、一本の道を深く進みます。名前はそのまま調べ方を表しています。
最短経路を求めるのはどちらか、取り違える人
最短経路（辺の数が最少の経路）を求められるのは幅優先探索です。深さ優先探索は経路を見つけますが、最短とは限りません。
探索木と探索の方法を、同じものと思っている人
探索木は、状況をたどる地図のような構造です。幅優先探索と深さ優先探索は、その地図をどの順で調べるかを決める方法です。
具体例で使い分ける
例 1
同じ地図を、二つの探索で調べる
説明のために作った例です。頂点はAからEの5つです。AはBとCにつながり、BはDに、DはEに、CはEにつながっています。始点はA、目的はEで、同じ段階の頂点はアルファベット順に調べます。
- 幅優先探索は、Aの次に1辺で行けるBとC、その次に2辺で行けるDとEと調べます。Eには、AからCを通る2辺で着きます。
- 深さ優先探索は、AからBへ、BからDへ、DからEへと進みます。Eには、A、B、D、Eと3辺で着きます。
結論: どちらもEに着きますが、辺の数が最少の経路（A、C、E）が求まるのは幅優先探索です。深さ優先探索が見つけた経路は、最短とは限りません。
例 2
問題文の言葉から選ぶ
説明のために作った例です。ある問題文に、始点に近いものから順に調べて、辺の数が最少の経路を必ず求められる探索方法はどれか、とあります。
- 近い順に調べる、辺の数が最少の経路、という手がかりが二つ並んでいます。
- 最短経路を求められるのは幅優先探索です。深さ優先探索は最短とは限りません。
結論: 答えは幅優先探索です。「最短」と「近い順」が出たら、幅優先を第一候補にします。
問題文から答えを選ぶ手順
- 1
調べる順番を探す
近い順や階層ごとなら幅優先探索、進める限り深くなら深さ優先探索です。
- 2
最短経路の言葉があるかを見る
辺の数が最少の経路を必ず求める、とあれば幅優先探索です。最短とは限らない、とあれば深さ優先探索です。
- 3
入れ物の言葉を見る
キューが出てきたら幅優先探索、再帰が出てきたら深さ優先探索の説明であることが多いです。
- 4
探索木そのものの説明と取り違えない
探索木は構造の名前で、探索の方法ではありません。問題が方法を聞いているかを確認します。
試験での見分け方
- 1幅優先探索は、近い頂点から順に調べる。調べ待ちはキューで持つ。
- 2深さ優先探索は、進める限り進み、行き止まりで戻る。再帰で書ける。
- 3辺の数が最少の経路を求められるのは、幅優先探索。
- 4深さ優先探索が見つける経路は、最短とは限らない。
誤答しやすい選択肢
最短経路を求められるのは深さ優先探索と書く
修正: 最短経路を求められるのは幅優先探索です。深さ優先探索は何らかの経路を見つけますが、最短とは限りません。
幅優先探索を、深く進む探索と書く
修正: 幅優先探索は、始点に近い頂点から順に調べます。深く進むのは深さ優先探索です。
キューを深さ優先探索の道具として選ぶ
修正: キューで調べ待ちを持つのは幅優先探索です。深さ優先探索は、再帰で次の頂点へ進む形でよく説明されます。
探索木を、探索の方法の一つと書く
修正: 探索木は、状況をたどる構造の名前です。幅優先探索と深さ優先探索は、その構造を調べる順番の決め方です。
最短経路を、移動距離の合計が最小の経路と書く
修正: このページの最短経路は、辺の数が最少の経路です。辺ごとに重みがある場合の話とは、分けて読みます。
確認問題
Q1始点に近い頂点から順に調べる探索は。
答え: 幅優先探索
1辺で行ける頂点、2辺で行ける頂点と、順に調べます。
Q2進める限り先へ進み、行き止まりで戻る探索は。
答え: 深さ優先探索
隣接していて印のない頂点を、再帰的に訪れます。
Q3辺の数が最少の経路を求められるのは、どちらの探索か。
答え: 幅優先探索
始点から到達できる頂点への最短経路を求められます。深さ優先探索は最短とは限りません。
Q4調べ待ちの頂点を、キューで持つのは、どちらの探索か。
答え: 幅優先探索
印を付けたが、隣接先をまだ調べていない頂点を、キューで持ちます。
到達チェック
- 幅優先探索の調べ方を説明できる
- 深さ優先探索の調べ方を説明できる
- 最短経路を求められるのはどちらかを言える
- キューと再帰がどちらに対応するかを言える
- 探索木と探索の方法を分けて言える
関連ページで確認する
同じ資格で次に知りたいこと
- 強いAIと弱いAIの違い｜理解や意識を持つとみなすか、道具とみなすか（G検定）
強いAIと弱いAIの違いを、コンピュータが理解や心の働きを実際に持つとみなすかどうかで整理します。ジョン・サールが強いAIと呼ぶ立場と、その対比としての弱いAIの定義、中国語の部屋が向けられた先を、一次資料に沿って解説し、G検定での判断手順と確認問題も掲載します。
- グリッドサーチとランダムサーチの違い
グリッドサーチとランダムサーチの違いを、候補の選び方、試行回数、重要なハイパーパラメータの探し方、G検定での判断手順、計算例と確認問題まで解説します。
- チューリングテストと中国語の部屋の違い｜判定の方法と、理解したと言えるかの論点（G検定）
チューリングテストと中国語の部屋の違いを、問い・判断の材料・結論の3点で比較します。チューリングが1950年の論文で示した模倣ゲームと、ジョン・サールが1980年の論文で示した思考実験を、一次資料に沿って整理し、G検定での判断手順と確認問題も掲載します。
よくある質問
Q幅優先探索と深さ優先探索は、何が違う？
調べる順番が違います。幅優先探索は始点に近い頂点から順に調べ、深さ優先探索は進める限り先へ進んで行き止まりで戻ります。
Q最短経路を求められるのはどちら？
幅優先探索です。始点から到達できる頂点への、辺の数が最少の経路を求められます。深さ優先探索が見つける経路は、最短とは限りません。
Qキューを使うのはどちらの探索？
幅優先探索です。印を付けたが隣接先をまだ調べていない頂点を、キュー（先に入れたものを先に取り出す入れ物）で持ちます。
次に見る比較
- G検定・DS検定・統計検定2級で重なる用語10語の比較
同じ名前の用語の定義と収録章を、資格ごとに並べます。
- ベイズの定理と条件付き確率の違い（統計検定2級の式と計算例）
求める確率の向きの違いと、陽性になる確率の計算例を確かめます。
- 紛らわしい用語ペア早見表
混同しやすい用語の違いと判定の手掛かりを、資格別の一覧で確かめます。
執筆: ミナト編集部（運営者情報を見る）