訪問済み
キュー内
調べたエッジ

  • 現在
  • キュー内
  • 訪問済み
  • 経路
ノードのクリックで設定

幅優先探索について詳しく

幅優先探索 (BFS)

幅優先探索はグラフを輪のように広がって探索します。まずスタートに隣接するノードすべて、次にエッジ2本先のノードすべて、という順です。これを先入れ先出しのキューで行います。ノードをクリックしてそこから始め、必要ならゴールも選んで、探索を1ステップずつ進めてみましょう。キューが伸び縮みし、各ノードに距離が付き、最短経路が現れる様子がわかります。 「再生」で探索を見るか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると好きな位置に移動できます。ノードをクリックするとスタートになります。クリックを「ゴール」に切り替えて別のノードをクリックすると、そこへの最短経路を探します。各ノードの数字はスタートからの距離で、グラフの下の列がキューです。「新しいグラフ」で別のグラフを作ります。ノード数とエッジ数を選べます。ボードを選択した状態では、矢印キーでステップ、スペースキーで再生と一時停止、Home と End で最初と最後に移動します。

使い方

  1. ノードをクリックしてスタートにします。経路を探すには、クリックを「ゴール」に切り替えて別のノードをクリックします。
  2. 「再生」を押すか、「ステップ」と「戻る」で1ステップずつ進めます。ステップスライダーをドラッグすると探索の好きな位置に移動できます。
  3. グラフの下のキューと各ノードの距離に注目しましょう。「新しいグラフ」で別のグラフを試せます。

幅優先探索のしくみ

スタートノードを距離 0 でキューに入れます。あとは繰り返しです。キューの先頭のノードを取り出し、その隣接ノードを1つずつ見ます。まだ見ていない隣接ノードには、取り出したノードより1大きい距離を付け、そのノードを到達元として記録し、キューの末尾に加えます。すでに見た隣接ノードは飛ばします。キューが空になれば、到達できるすべてのノードの距離が決まっています。

最短経路が見つかる理由

キューは見つかった順にノードを出し、ノードは輪ごとに見つかります。距離 1 のノードはすべて、距離 2 のどのノードよりも先にキューに入ります。以降も同じです。そのため、ノードに初めて到達したときの経路はエッジ数が最少です。記録した到達元をゴールからスタートまでたどると、その経路が得られます。数えるのはエッジ数だけです。エッジの長さが異なる場合はダイクストラ法が必要です。

よくある質問

幅優先探索とは?

スタートノードからグラフを探索する方法です。まず隣接ノードをすべて訪れ、次にその隣接ノード、と輪ごとに広げます。見つかった順にノードを並べておくためにキューを使います。

幅優先探索で最短経路は見つかりますか?

はい、どのエッジも同じ重さなら見つかります。BFS があるノードに初めて到達したとき、使ったエッジ数は最少です。エッジの長さが異なる場合は、ダイクストラ法を使ってください。

BFS と DFS の違いは?

幅優先探索はキューを使い、輪ごとに均等に広がります。深さ優先探索はスタック(または再帰)を使い、1本の経路を行けるところまで深く進んでから戻ります。BFS はエッジ数で最短の経路を見つけますが、DFS は見つけません。ただし DFS は閉路の検出やトポロジカルソートに便利です。

幅優先探索の速さは?

各ノードを1回ずつキューから取り出し、各エッジを両端から見るので、処理量はノード数とエッジ数の和に比例して増えます。

グラフはどこかに送信されますか?

いいえ。グラフの作成と探索はブラウザ内で行われ、最後の設定はこのブラウザのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ