基本情報の幅優先探索と深さ優先探索を閉路のあるグラフで理解する

基本情報の幅優先探索は、開始点から辺をたどる回数が少ない頂点から調べる方法です。深さ優先探索は、一つの道を先へ進み、進めなくなったら戻って別の道を調べます。前者はキュー、後者は再帰やスタックの動きと結び付けると、探索順を追いやすくなります。

ただし、グラフでは木と違って同じ頂点へ複数の経路から着くことがあります。この記事では閉路のある自作グラフを一つ固定し、キューと呼出し履歴、訪問済みの印を一手ずつ追います。探索順だけでなく、最短経路を求められる条件と、同じ頂点を何度も登録しない理由まで確認します。

この記事のポイント

幅優先と深さ優先を同じグラフで比較できる
キューの中身と再帰の呼出し履歴を区別できる
訪問済みの印で閉路と重複登録へ対処できる
最短の辺数と重みの合計を取り違えずに判断できる

無料

基本情報技術者試験過去問アプリ

本番形式で繰り返し解ける。スキマ時間に1問から

2,000問以上収録

無料で過去問を解く

基本情報の幅優先探索と深さ優先探索の違い

閉路のあるグラフを表で確認する

頂点A、B、C、D、E、Fからなる無向グラフを使います。辺はA-B、A-C、B-D、C-D、C-E、D-F、E-Fの7本です。無向なので、AからBへ進めるならBからAへも進めます。どの頂点もAから到達できるものとし、ここでは辺に距離や料金などの重みを付けません。

隣接する頂点を、次の表の順番で調べることにします。各行はアルファベット順です。探索の開始点はA、訪問順は初めて処理する時点の順番と定めます。後半の例題も、写真の模型の見た目ではなく、この隣接関係を基に追ってください。

スクロールできます

頂点	隣接する頂点を調べる順番
A	B、C
B	A、D
C	A、D、E
D	B、C、F
E	C、F
F	D、E

AからB、D、Cを通るとAへ戻れるため、閉路があります。またDにはBからもCからも到達できます。このようなグラフでは、単に隣へ進むだけでは同じ頂点を繰り返し扱う可能性があります。すでに発見・訪問した頂点を記録することが、木の図だけを読む場合との大きな違いです。

有向グラフの場合は、辺の向きも条件になります。例えばDからCへの辺だけがあるなら、Dの隣としてCを読むことと、CからDへ進めることは同じではありません。無向グラフの表をそのまま片側だけ消したつもりで追うのではなく、出発する頂点の行に移動先があるかを確認します。

隣接行列で表される場合も、行が出発側、列が到着側という定義なら、その行の印がある列を調べます。無向グラフでは対応が対称になりますが、有向グラフで同じとは限りません。表の軸の定義と、辺の矢印を確認することが、訪問順を計算する前の準備になります。

幅優先はキューで近い層から

幅優先探索はBFSとも呼ばれます。まずA、次にAの隣のBとC、その次にさらに一つ辺をたどって着く頂点、というように調べる範囲を広げます。この「近い」は、ここでは辺の本数が少ないという意味です。図面上で近く描かれているかどうかではありません。

使うキューは先入れ先出しです。先に登録した頂点を先に取り出し、新しく見つかった頂点は末尾へ追加します。Aを取り出してB、Cを追加すると、キューはB、Cです。BからDが見つかっても、すでに待っているCの後へ並べるのでC、Dになります。

この順番待ちによって、次の深さの頂点が前の深さの頂点を追い越さなくなります。キューを単に「待つ箱」と覚えるより、新しい頂点は後ろへ置き、前から一つずつ処理することまで確認してみてください。探索順の問題でキューの左右を逆に読むと、別の結果になってしまいます。

BFSとキューの関係はNISTの幅優先探索の定義でも確認できます。キューそのものの操作を整理するなら、基本情報のスタックとキューを先に確認すると、探索への対応が読みやすくなります。

深さ優先は進んでから戻る

深さ優先探索はDFSとも呼ばれます。AからBへ進み、Bからまだ訪れていないDへ進む、と一つの経路を深くたどります。行ける未訪問の隣がなくなったら、直前の分岐へ戻り、まだ調べていない隣があるかを確認します。戻ることも処理の一部です。

再帰で書く場合、現在の頂点を訪問済みにした後、その隣の未訪問頂点について同じ探索処理を呼び出します。呼び出した処理が終わると、元の処理へ戻って次の隣を確認します。途中の呼出し情報がスタックとして保持されるため、どの分岐へ戻るかを覚えておけます。

ここで、訪問順の一覧と呼出し中のスタックは同じものではありません。訪問順には過去に調べ終えた頂点も残りますが、呼出しスタックからは戻り終えた頂点が取り除かれます。これから戻る場所を表す記憶と、すでに訪れた頂点の履歴を、別の欄に書くと混乱しにくくなります。

NISTの深さ優先探索の定義でも、再帰による実装が示されています。明示的なスタックで実装する場合は、積む順番と取り出す順番の関係まで確認が必要です。再帰版と同じ隣接順をそのまま積めば、必ず同じ順で訪れるとは限りません。

訪問済みの印をいつ付けるか

この例のBFSでは、頂点をキューへ追加する時点で発見済みの印を付けます。DはBの処理で初めて追加されます。後でCの隣としてDが出てきても、すでに印があるので再追加しません。印を「今まさに処理し終えた」という意味に限定せず、追加済みの頂点まで管理するわけです。

取り出した時点まで印を付けない設計では、まだキューで待っている同じ頂点を、別の経路からもう一度追加する場合があります。その方式が常に誤りというわけではありませんが、重複候補を取り出した際に無視するなど、別の処理が必要になります。問題文の擬似コードが印を付ける位置を確認してください。

この例の再帰DFSでは、探索関数へ入った時点で訪問済みにします。隣を見るたびに、訪問済みなら再帰呼出しを行いません。AからBへ進んだ後、Bの隣にAがあっても戻る再帰を始めないので、同じ辺を往復し続けることを防げます。

有限個の頂点を各一回扱う例では、この管理によって閉路があっても探索を終えられます。ただし、頂点を一回ずつ訪れる探索と、同じ頂点を別の経路で通る候補をすべて列挙したい問題は目的が違います。何を訪問済みとして省略してよいかも、解こうとしている問題に合わせて決めます。

隣接順と訪問の意味を固定する

同じグラフで同じBFSを使っても、Aの隣をC、Bの順に調べれば、同じ深さの頂点の順番が変わる可能性があります。DFSも、どの隣へ最初に進むかで経路が変わります。探索法の名前だけで、頂点名の並びがいつも一意に決まるとは考えないようにしましょう。

またDFSでは、頂点へ入ったときに記録するのか、子の処理がすべて終わってから記録するのかで出力順が変わります。この記事は初めて入った時点を訪問順とします。木の前順・間順・後順の区別は、基本情報の木構造と二分木の走査で確認できます。

図を追う前に、開始点、辺の向き、隣を調べる順、印を付ける時点、出力する時点の五つを書いておきます。同じ「訪問」という言葉でも、発見したときと処理が終わったときを区別する問題があるからです。ここを固定すると、途中の表と最終的な並びを対応させられます。

条件を変える練習として、同じグラフで隣を逆のアルファベット順に調べてみます。BFSではAからC、Bを追加し、CからE、Dを追加するので、取り出し順はA、C、B、E、D、Fです。DFSで同じ逆順を使うと、A、C、E、F、D、Bとなります。頂点のつながりが同じでも、同じ深さの並びや深く進む枝が変わっています。

ただし、この変更でもAからFまでの最短の辺数が3という事実は変わりません。探索順が違うことと、グラフ自体の最短距離が変わることは別です。先に出てきたから近いと決めるのではなく、どの探索で、何を距離としているのかを一緒に確認しましょう。

基本情報の幅優先探索と深さ優先探索を追跡する

BFSのキューを一行ずつ追う

最初はAを発見済みにし、キューへ入れます。以下のキューは左端が先頭、右端が末尾です。各行では先頭の頂点を一つ取り出し、その隣を表の順で調べ、未発見の頂点だけを末尾へ追加します。追加した時点で印を付ける条件を、途中で変えないでください。

スクロールできます

操作	新しく追加する頂点	操作後のキュー
初期化	A	A
Aを取り出す	B、C	B、C
Bを取り出す	D	C、D
Cを取り出す	E	D、E
Dを取り出す	F	E、F
Eを取り出す	なし	F
Fを取り出す	なし	空

取り出す順番はA、B、C、D、E、Fです。Cの隣にあるDは、すでにBから発見されているので追加しません。Eの隣にあるFも、すでにDの処理で追加されています。表では「新しく追加する頂点」と「いま取り出した頂点」を別々に見ることが、重複を防ぐポイントです。

距離も一緒に記録できます。Aを0とし、新しく見つけた隣の距離を、いまの頂点の距離に1を足して決めます。BとCは1、DとEは2、Fは3です。初めて発見したときの親を保存すれば、FからD、B、Aへ逆にたどり、AからFへの経路A-B-D-Fを取り出せます。

表のBFSを、説明用の擬似コードにすると次の流れです。キューへ入れる前に発見済みにしていることと、距離を親の距離から一つだけ増やしていることに注目してください。この例での動作を示したもので、特定の試験問題のプログラムの転載ではありません。

発見済み[A] ← 真
距離[A] ← 0
Aをキューの末尾へ入れる
キューが空でない間、繰り返す
  u ← キューの先頭から取り出す
  uの隣vを、表の順番で調べる
    vが未発見なら
      発見済み[v] ← 真
      距離[v] ← 距離[u] + 1
      親[v] ← u
      vをキューの末尾へ入れる

親を記録するのは、距離を計算するためだけではありません。Fの親D、Dの親B、Bの親Aと逆にたどれば、実際に通れる経路を復元できます。ただし親の記録は元の無向辺の向きを変えるものではなく、今回どの頂点から発見したかという探索側の情報です。

再帰DFSの呼出し履歴を追う

同じ隣接表で、DFSは各頂点へ入ったときに訪問済みにします。Aから最初の未訪問の隣Bへ進み、BからDへ進みます。Dの隣はB、C、Fの順ですが、Bは訪問済みなのでCへ進みます。その後はCからE、EからFへ進みます。

スクロールできます

初めて入る頂点	呼出し中のスタックを外側から並べる
A	A
B	A、B
D	A、B、D
C	A、B、D、C
E	A、B、D、C、E
F	A、B、D、C、E、F

訪問順はA、B、D、C、E、Fです。Fの隣のDとEはどちらも訪問済みなので、新たな呼出しはせずEへ戻ります。Eもほかに未訪問の隣がないためCへ戻り、順にD、B、Aまで戻ります。Aの隣Cも、すでに訪問済みなので改めて探索しません。

この例で、すべての隣の処理が終わって戻る順番を記録するなら、F、E、C、D、B、Aになります。初めて入る順と、戻る順は違います。「スタックの中身はどれか」「出力の順はどれか」という設問では、どの時点のどの記録を問われているかまで読む必要があります。

閉路と重複の処理を点検する

DへはBからもCからも到達できます。この例のBFSでは、Bの処理でDへ印を付けているため、Cからは追加しません。A-B-D-C-Aの閉路についても、Aへすでに印があるので、新しい探索を始めることはありません。頂点の名前と印を対応させるだけで、戻り道を新規候補として扱わずに済みます。

自作の確認問題として、BFSで印を付ける時点を取り出し時へ変え、待っている頂点を別途管理しない場合を考えてみてください。BからDが追加された後、Dを取り出す前にCを処理します。この時点でDにまだ印がないなら、CからDを再び追加する可能性があります。

重複追加を許す実装なら、取り出した後にすでに処理済みかを確認するなどの扱いが必要です。擬似コードを読む際に、条件の位置を勝手に変更して追わないようにしましょう。同じアルゴリズムの説明でも、発見済み、処理中、処理済みを区別する実装があります。

また、元のグラフへ孤立した頂点Gを一つ追加した場合、Aからの探索だけではGを訪れません。グラフ全体を調べたいなら、まだ訪れていない頂点を新しい開始点として探索する、といった外側の処理が必要です。一回の探索で到達できた範囲と、グラフの全頂点を混同しないことも大切です。

最短経路には条件がある

この例のBFSでFの距離は3です。開始点から距離0のA、距離1のBとC、距離2のDとEの順に処理するので、より少ない辺数で着ける経路があるのに、先に遠い距離を確定することを防げます。辺数を距離として扱う、重みのないグラフでの性質です。

一方、例のDFSが最初にFを発見したときの経路はA-B-D-C-E-Fで、辺が5本あります。実際にはA-B-D-Fという3本の経路があるので、DFSで初めて見つけた経路は最短ではありません。到達できる経路を見つけることと、最小の辺数を保証することは別の目的です。

最短経路が一つだけとも限りません。A-C-E-Fも3本なので、どの親を先に記録したかで、取り出される最短経路が変わる場合があります。BFSが最短の辺数を求める性質と、同じ長さの経路の中でどれを選ぶかという順序の問題を分けて考えましょう。

辺ごとに時間や費用が違う場合は、辺数が少ない経路が最小の合計になるとは限りません。例えばA-B-D-Fの各辺が10、A-C-E-Fの各辺が1なら、どちらも3本でも合計は30と3です。重み付きの最短経路を学ぶ場合は、適用条件を確認したうえで基本情報のダイクストラ法へ進めます。

計算量と記憶量の前提を読む

頂点数をV、辺数をEとし、隣接リストで各隣を順に読める場合、頂点を一回ずつ管理し、辺を順に調べるBFSとDFSの基本的な探索時間はO(V＋E)です。無向辺は両側のリストで確認しますが、定数倍の違いなのでこの表し方になります。ここでは隣接リストがすでに用意されている前提です。

隣接行列なら、ある頂点の隣を知るために行を横に調べます。V個の頂点ごとにV個分を確認する実装ではO(V²)になります。同じBFSという名前でも、グラフの表現と隣の調べ方を確認する必要があります。アルファベット順へ並べ替える処理を実行時に追加するなら、その手間も別に考えます。

BFSのキュー、DFSの呼出しスタックや明示的スタック、訪問済み配列などにも記憶が必要です。有限グラフの基本的な実装では、補助記憶は頂点数に応じてO(V)まで使うことがあります。「DFSならいつでもBFSより少ない記憶で済む」と無条件には決められません。幅の広い木と深い経路では、待つ頂点や呼出しの残り方が変わります。

これらの基礎とグラフ表現は、プリンストン大学の無向グラフと探索の教材でも確認できます。試験では、探索する範囲、データ構造、各操作が何回起きるかを順に数えることが、名前だけで計算量を暗記するより確実です。