幅優先探索 (BFS)
池に石を落とすと、波紋が輪になって均等に広がります。幅優先探索もグラフを同じように探索します。まずスタートから1歩のところすべて、次に2歩のところすべて、という順です。この単純な順序こそが、最短経路を見つけられる理由です。
考え方
グラフとは、ノードをエッジでつないだものです。場所と道路、人と友人関係、迷路のマスとその間の通路などです。幅優先探索が答えるのは「ここから始めて、どこに行けるか、最少何歩で行けるか」という問いです。これから訪れるノードをキューに入れておきます。先頭からノードを取り出し、新しいノードを末尾に加えるので、ノードは見つかった順に処理されます。
ステップごとの手順
スタートを距離 0 でキューに入れます。先頭のノードを取り出します。まだ見ていない隣接ノードごとに、距離を現在のノードより1大きく記録し、現在のノードを到達元として記録して、キューの末尾に加えます。すでに見た隣接ノードは飛ばします。キューが空になるか、ゴールに到達するまで繰り返します。
例
エッジ A–B、A–C、B–D、C–D、C–E、D–F を持つグラフで、A から始めます。キューから A を取り出すと、距離 1 の B と C が見つかります。B を取り出すと、距離 2 の D が見つかります。C を取り出すと、D はすでに見ていて、距離 2 の E が見つかります。D を取り出すと、距離 3 の F が見つかります。E と F からは新しいノードは見つからず、キューは空になります。記録した到達元を F からたどると F ← D ← B ← A となり、A から F への最短経路は A → B → D → F、エッジ3本です。
距離が正しい理由
距離 1 のノードはすべて距離 2 のどのノードよりも先に、距離 2 のノードはすべて距離 3 のどのノードよりも先にキューに入ります。ノードの隣接ノードは、そのノード自身がキューから出たときにしかキューに入らないからです。そのため、ノードに最初に届く経路はエッジ数が最少で、BFS が距離を直す必要はありません。各ノードは1回取り出され、各エッジは両端から見られるので、処理量はノード数とエッジ数の和に比例して増えます。
歴史と用途
Konrad Zuse は1945年、Plankalkül 言語の研究の中で幅優先探索を記述しましたが、その研究が出版されたのは1972年でした。Edward F. Moore は1959年に迷路から出る最短経路を求めるために再発見し、C. Y. Lee は1961年に回路基板の配線に使いました。今日では、パズルの最少手数、ソーシャルネットワークでの隔たりの次数、ウェブクローラーが最初にたどるページ、ゲームで最も近い空きマスを求めるのに使われます。エッジに長さがある場合は、ダイクストラ法がこれを一般化したものです。
試してみよう
アプリを開いて「ステップ」を押してください。訪問中のノードは強調表示され、キューで待っているノードは青、訪問済みのノードは緑になり、それぞれに距離が表示されます。キューはグラフの下に先頭から表示されます。クリックを「ゴール」に切り替えてノードを選ぶと、そこで止まって最短経路が見られます。ノードとエッジを増やした新しいグラフも作れます。
よくある質問
BFS の時間計算量は?
V 個のノード(頂点)と E 本のエッジに対して O(V + E) です。各ノードはキューに1回入って1回出て、各エッジは両端から調べられます。キューと距離のために O(V) の追加メモリが必要です。
BFS はなぜキューを使うのですか?
先入れ先出しなら、ノードが見つかった順、つまり距離の順に並ぶからです。代わりにスタックを使うと、探索はまず深く潜っていきます。それが深さ優先探索です。
BFS は重み付きグラフで最短経路を見つけられますか?
一般には見つけられません。数えるのはエッジ数で、エッジの長さではないからです。負のエッジがない重み付きグラフにはダイクストラ法を使ってください。重みがすべて 0 か 1 なら、0-1 BFS という変種が使えます。
BFS はどこで使われますか?
パズルや迷路を最少手数で解く、ソーシャルネットワークで友人の友人を探す、ウェブをレベルごとにクロールする、ネットワークでブロードキャストする、そして最大フローを求めるなど他のアルゴリズムの部品として使われます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
幅優先探索を試す