- 現在
- キュー内
- 訪問済み
- 経路
幅優先探索 (BFS)
幅優先探索はグラフを輪のように広がって探索します。まずスタートに隣接するノードすべて、次にエッジ2本先のノードすべて、という順です。これを先入れ先出しのキューで行います。ノードをクリックしてそこから始め、必要ならゴールも選んで、探索を1ステップずつ進めてみましょう。キューが伸び縮みし、各ノードに距離が付き、最短経路が現れる様子がわかります。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、そこへの最短経路を探します。各ノードの数字はスタートからの距離で、グラフの下の列がキューです。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。
使い方
- ノードをクリックしてスタートにします。経路を探すには、クリックを「ゴール」に切り替えて別のノードをクリックします。
- 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると探索の好きな位置に移動できます。
- グラフの下のキューと各ノードの距離に注目しましょう。「新しいグラフ」で別のグラフを試せます。
幅優先探索のしくみ
スタートノードを距離 0 でキューに入れます。あとは繰り返しです。キューの先頭のノードを取り出し、その隣接ノードを1つずつ見ます。まだ見ていない隣接ノードには、取り出したノードより1大きい距離を付け、そのノードを到達元として記録し、キューの末尾に加えます。すでに見た隣接ノードは飛ばします。キューが空になれば、到達できるすべてのノードの距離が決まっています。
最短経路が見つかる理由
キューは見つかった順にノードを出し、ノードは輪ごとに見つかります。距離 1 のノードはすべて、距離 2 のどのノードよりも先にキューに入ります。以降も同じです。そのため、ノードに初めて到達したときの経路はエッジ数が最少です。記録した到達元をゴールからスタートまでたどると、その経路が得られます。数えるのはエッジ数だけです。エッジの長さが異なる場合はダイクストラ法が必要です。
よくある質問
幅優先探索とは?
スタートノードからグラフを探索する方法です。まず隣接ノードをすべて訪れ、次にその隣接ノード、と輪ごとに広げます。見つかった順にノードを並べておくためにキューを使います。
幅優先探索で最短経路は見つかりますか?
はい、どのエッジも同じ重さなら見つかります。BFS があるノードに初めて到達したとき、使ったエッジ数は最少です。エッジの長さが異なる場合は、ダイクストラ法を使ってください。
BFS と DFS の違いは?
幅優先探索はキューを使い、輪ごとに均等に広がります。深さ優先探索はスタック(または再帰)を使い、1本の経路を行けるところまで深く進んでから戻ります。BFS はエッジ数で最短の経路を見つけますが、DFS は見つけません。ただし DFS は閉路の検出やトポロジカルソートに便利です。
幅優先探索の速さは?
各ノードを1回ずつキューから取り出し、各エッジを両端から見るので、処理量はノード数とエッジ数の和に比例して増えます。
グラフはどこかに送信されますか?
いいえ。グラフの作成と探索はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
エディターへ