BFSとDFS — 広く探すか、深く潜るか
地図でも、SNSの友達のつながりでも、フォルダの階層でも —— 「点と点が線でつながったもの(グラフ)」をたどって全部を訪ねたいことがあります。そのとき問われるのはたどる順番です。代表的なのが2つ。BFS(幅優先)は近いところから波紋のように広げ、DFS(深さ優先)は行けるところまで一気に潜ります。
同じグラフ・同じスタート(頂点A)でも、順番はまるで変わります。下の図1でBFS / DFS を切り替え、「次の一歩」を押してみてください。次にどの頂点を取り出すかを決める待ち箱(フロンティア)の中身に注目すると、2つの違いがはっきり見えます。
違いは「待ち箱」の出し方だけ
驚くことに、BFSとDFSのプログラムはほとんど同じです。見つけた頂点を待ち箱にためて、1つ取り出して訪問し、そのとなりをまた待ち箱に入れる —— この繰り返し。違うのは待ち箱から取り出す順番だけです。
BFSはキュー(先に入れたものから出す=FIFO)を使います。だから「Aのとなり全部 → そのまたとなり全部」と、近い順に層をなして広がります。最短経路(最少ホップ)を探したいときの土台です。DFSはスタック(後に入れたものから出す=LIFO)を使います。すると最後に見つけたとなりへ次々もぐり込み、行き止まりで初めて引き返す。迷路を片手を壁につけて進むイメージです。
図1でEとFを結ぶ「近道の辺」に注目すると面白いです。BFSではFは先にCから見つかるのでこの辺は使われませんが、DFSでは深くもぐる途中のEからFを発見します。同じグラフから、違う形の「探索の木」が育つのです。
- BFS（幅優先）
- キューを使い、スタートから近い順に層状に探索。最少ステップの経路探しに向く。
- DFS（深さ優先）
- スタックを使い、行けるところまで潜ってから引き返す。全探索や経路の有無判定に向く。
- フロンティア
- 「見つけたが、まだ訪問していない」頂点の待ち箱。中身の出し方が探索の性格を決める。
- 訪問ずみ管理
- 一度入れた頂点に印を付け、輪(サイクル)があっても二度処理しないようにする。
まとめ
BFSとDFSは、コードの骨格は同じで、待ち箱がキューかスタックかという一点だけが違います。それだけで「近い順に広げる」か「深く潜る」かという正反対の性格が生まれる —— アルゴリズムの面白さが詰まった一対です。最短経路ならBFS、全パターン探索や深い構造の走査ならDFS、と使い分けの勘所も「広いか・深いか」で覚えられます。