メインコンテンツへスキップ
Z Graph & Pathfinding

幅優先探索(BFS)ビジュアライザー

グリッド上でインタラクティブに幅優先探索を体験できるツール。壁を描き、スタート地点とゴール地点を自由に動かし、迷路を自動生成しながら、探索が層ごとに広がっていく様子をステップ単位で観察できます。ブラウザだけですぐに動きます。

無料 登録不要 クライアントサイド プライバシーに配慮 Updated

Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.

Moves: Time: 🎉 Reached the goal!
/

疑似コード

使い方

  1. 1 クリック&ドラッグで壁を描画できます。緑色のスタート地点や赤色のゴール地点はドラッグして自由に移動できます。
  2. 2 Playボタンを押すと、スタート地点からBFSが層ごとに広がっていく様子を確認できます。
  3. 3 Mazeボタンで障害物を一瞬で自動生成したり、Stepボタンで1マスずつ手動で進めたりできます。
  4. 4 重み付けのないグリッドでは、BFSが見つける経路は常に最短(通過マス数が最小)であることが保証されています。

このツールを使う理由

  • 探索の最前線(フロンティア)が輪のように外側へ広がっていく、BFSならではの特徴的な動きを目で確認できます。
  • 重みのないグラフでBFSが最短経路を導ける理由を、直感的に理解できます。
  • BFSの均等な広がり方を、DFS(一方向へ深く掘り進む探索)やA*(ゴールへ直進する探索)と見比べられます。
  • すべての処理はブラウザ内だけで完結します。登録もデータのアップロードも不要です。

よくある質問

幅優先探索(BFS)とは何ですか?

BFSは、キュー(queue)を使ってグラフを層ごとに探索するアルゴリズムです。あるノードの隣接ノードをすべて訪れてから、次の階層の隣接ノードへと進みます。重みのないグラフでは、この方法により最短経路が得られます。

BFSの時間計算量はどれくらいですか?

O(V + E) です。各頂点と各辺をそれぞれ一度だけ調べるため、この計算量になります。V は頂点数、E は辺数を表します。

BFSは常に最短経路を見つけられますか?

重みのないグラフであれば、必ず見つけられます。重み付きグラフの場合は、各辺のコストを考慮できるダイクストラ法やA*を使う必要があります。

BFSとDFSの違いは何ですか?

BFSはキュー(queue)を使い、輪状に外側へ広がるように探索するため、重みのないグラフでは最短経路が保証されます。一方DFSはスタック(stack)を使い、行き止まりまで一方向を深く掘り進んでからバックトラックするため、最短経路は保証されません。

幅優先探索(BFS)ビジュアライザー とは？

幅優先探索(BFS)ビジュアライザーは、キュー(queue)構造を使ってBFSがグリッドを層ごとに探索していく過程を再現するツールです。スタート地点を起点に、探索範囲が輪のように外側へ広がっていきます。重み付けのないグリッドでは、この方法によって必ず最短経路が見つかり、ゴールに到達した瞬間にその経路がハイライト表示されます。

機能

ステップごとのアニメーション

キューがフロンティアを1レベルずつ広げていく様子を観察できます。

計算量

時間計算量: O(V + E)。空間計算量: O(V)。重みなしグラフで最短経路を求めます。

100%プライベート

すべてブラウザ内で完結し、データはアップロードされません。

例

Input

graph 1–2, 1–3, 2–4, 3–4; start 1

Output

visit order: 1 → 2 → 3 → 4 (level by level)

主な用途

  1. 1

    最短経路（重みなし）

    BFSが始点から辺の数が最少の経路を導き出す理由を確認できます。

  2. 2

    レベル順走査

    グラフや木構造を層ごとに探索します。

  3. 3

    連結性と到達可能性

    始点から到達可能なノードを調べます。

概要

ZerethonのBFSビジュアライザーは、ブラウザ上でグラフの幅優先探索をアニメーション表示し、キュー（queue）を使って始点からレベルごとに探索していく様子を可視化します。BFSはO(V + E)の時間計算量とO(V)の空間計算量で動作し、重みなしグラフにおける最短経路（辺の数が最少の経路）を見つけます。

カテゴリ
アルゴリズム
料金
無料
プライバシー
ブラウザベース
登録
不要

参考文献

プライバシー

明記されない限り、データがブラウザの外に送信されることはありません。幅優先探索(BFS)ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。

初めての方へ。Big-O 解析付きのステップバイステップ解説を読む: Graph Algorithms を学ぶ →

Zerethon Social で作成・共有・成長しよう

無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。

無料登録