最終更新日：2026年10月4日

fe fe-technology algorithm data-structure

まず結論

深さ優先探索（DFS）は、一つの経路を深く進み、先へ進めなくなったら戻って別の経路を調べます。幅優先探索（BFS）は、開始点から辺をたどる回数が少ない頂点から順に調べます。

科目Aでは、次の対応が判断の手掛かりです。

深さ優先＝深く進んで戻る＝スタック・再帰。幅優先＝浅い層から順に＝キュー。

このページでは、二つの探索の順序と性質を比較します。データの出し入れ自体は、スタックとキューの違いで確認できます。

直感的な説明

分かれ道のある迷路で、まず一つの道を進み続け、行き止まりなら直前の分かれ道へ戻るのが深さ優先探索のイメージです。

一方、入口から1歩で行ける場所を調べ、その次に2歩で行ける場所、3歩で行ける場所を調べるのが幅優先探索です。

ここでいう「近い」は、基本的には辺をたどる回数が少ないことです。移動時間や料金が小さいことと同じとは限りません。

定義・仕組み

同じ木で探索順序を比べる

点を頂点（ノード）、頂点を結ぶ線を辺と呼びます。頂点と辺で関係を表すものがグラフで、木はその一種です。

次の木をAから探索します。線で結ばれた頂点だけに進めるものとし、複数の未訪問の子がある場合は図の左から調べます。順序は、各頂点を初めて訪れた時点で記録します。

        A
       / \
      B   C
     / \   \
    D   E   F
   /
  G

Aの子はBとC、Bの子はDとE、Cの子はF、Dの子はGです。これ以外の辺はありません。

方法 初めて訪れる順序 読み方
深さ優先探索 A → B → D → G → E → C → F B側を深くたどり、戻って未訪問の枝へ進む
幅優先探索 A → B → C → D → E → F → G Aからの辺の数が0、1、2、3の層の順に調べる

見るポイント：DFSはCより先にGへ進みます。BFSはGより先に、浅い層のC・E・Fを調べます。

DFSでGの次にEが記録されるとき、実際にはGからD、Bへ戻ってからEへ進みます。DやBは既に訪れているので、この記録には再び書きません。

深さ優先探索とスタック

深さ優先探索では、最近通った分かれ道へ戻るための情報を保持します。この動きには、最後に入れたものを先に取り出すスタック（LIFO）が適しています。

再帰で実装する場合も、途中の呼出し情報がスタックに保持されます。再帰は、処理の中から自分自身を呼び出す方法です。

なお、未処理の子をまとめてスタックに積む実装で左側から取り出したい場合は、右側から積む必要があります。積む順序と取り出す順序は逆になるためです。

幅優先探索とキュー

幅優先探索では、先に見つけた頂点から順に処理します。そのため、先に入れたものを先に取り出すキュー（FIFO）を使います。

上の木で、キューの左端を取り出し側として、先頭の頂点を取り出した後、その未訪問の子を左から末尾に追加すると、次のようになります。

操作 操作後のキュー（左が先頭）
最初にAを入れる A
Aを取り出し、B・Cを追加 B、C
Bを取り出し、D・Eを追加 C、D、E
Cを取り出し、Fを追加 D、E、F
Dを取り出し、Gを追加 E、F、G
Eを取り出す F、G
Fを取り出す G
Gを取り出す 空

Gが追加されても、既に待っているE・Fが先に処理されます。この順番待ちによって、浅い層を先に調べられます。

グラフでは訪問済みを管理する

一般のグラフには、同じ頂点へ戻る経路や、複数の道から同じ頂点に到達する経路があります。訪問済みを管理せずに進むと、同じ頂点を何度も調べたり、循環し続けたりするおそれがあります。

幅優先探索では、通常、キューへ追加する時点で発見済みとして記録し、同じ頂点を重複して追加しないようにします。深さ優先探索でも、既に訪れた頂点への再訪を避けます。

科目Aでどう出る？

探索方法と性質を対応付ける

観点 深さ優先探索（DFS） 幅優先探索（BFS）
進み方 一つの経路を深く進み、戻る 開始点から浅い層の順に進む
主なデータ構造 スタック、または再帰の呼出しスタック キュー
最初に見つけた経路 最短とは限らない 重みなしのグラフでは辺の数が最小の経路になる
保持する情報の特徴 戻るための情報などを保持する 未処理の同じ層や次の層の候補を保持する

幅優先探索で最短経路そのものを取り出すには、各頂点をどの頂点から発見したかも記録しておきます。探索順序を並べただけでは、目的地への経路にはなりません。

「最短」の条件を確認する

幅優先探索は、重みなしのグラフで辺の数が最小の経路を求められます。すべての辺のコストが同じ正の値なら、辺の数が最小であることは合計コストが最小であることにも対応します。

しかし、Aから目的地Tへ直接進む辺が10分、AからXを経由してTへ進む二つの辺がそれぞれ1分なら、1本の経路より2本の経路の方が短時間です。

辺の数が少ない経路と、重みの合計が小さい経路を混同しないようにします。

どんな場面で使う？

深さ優先探索は、経路や組合せを一つずつ試し、途中で戻って別の候補を調べる処理の基礎になります。

幅優先探索は、すべての移動を1手として扱う問題で、目的の状態までの最小手数を調べる場合などに使えます。どちらも、ある頂点から到達できる範囲を調べる方法として利用できます。

よくある誤解・混同

DFSやBFSなら、探索順序は一つに決まる？

開始点と、隣接する頂点を調べる順序によって変わります。このページは左から調べると指定しています。設問で文字順や番号順などが指定されていたら、その順序に従います。

深さ優先探索は、必ず親を先に出力する？

深さ優先でたどることと、頂点をいつ出力するかは別です。このページは初めて訪れたときに記録していますが、子を調べ終わってから記録する方法もあります。設問では、探索の進み方と記録のタイミングを確認します。

根を記録する時点による先行順・中間順・後行順の違いは、二分木の走査で、同じ木を使って比較しています。

幅優先探索は、常に深さ優先探索より多くのメモリを使う？

枝分かれが多い木では、幅優先探索の待ち候補が多くなる傾向があります。ただし、必要なメモリはグラフの形や実装、訪問済みの管理方法にも依存するため、「常に」とは断定できません。

二分探索は幅優先探索の別名？

二分探索は、整列済みのデータから候補範囲を半分ずつ絞る方法です。木やグラフを浅い層から調べる幅優先探索とは異なります。

確認問題（科目A・オリジナル）

次の木をAから探索する。複数の未訪問の子があれば左から調べ、各頂点を初めて訪れた順に記録する。深さ優先探索と幅優先探索の組合せとして、適切なものはどれか。

      A
     / \
    B   C
   /     \
  D       E
  • ア：深さ優先はA・B・C・D・E、幅優先はA・B・D・C・E
  • イ：深さ優先はA・B・D・C・E、幅優先はA・B・C・D・E
  • ウ：深さ優先も幅優先もA・B・D・C・E
  • エ：深さ優先はD・B・E・C・A、幅優先はA・B・C・D・E

正解：イ

  • ア：二つの探索順序が逆です。
  • イ：深さ優先はBからDへ進んでからC側へ移ります。幅優先はAの子B・Cを調べてからD・Eへ進みます。
  • ウ：幅優先では、Dより浅い層にあるCを先に訪れます。
  • エ：D・B・E・C・Aは、子を調べ終わってから親を記録する場合の並びです。「初めて訪れた順」という条件に合いません。

公式情報・参考リンク

まとめ（試験直前用）

  • DFSは深く進んで戻る。BFSは開始点から浅い層の順に調べる。
  • DFSはスタック・再帰、BFSはキューと対応する。
  • BFSが求める最短は、重みなしなら辺の数の最小。異なる重みの合計最小とは限らない。
  • 探索順序は、開始点・隣接頂点の順序・記録のタイミングを確認する。
  • 循環のあるグラフでは、訪問済みを管理して重複した探索を防ぐ。

© 2024-2026 stemtazoo. All rights reserved.