BFS vs DFS
BFS vs DFS compared — data structure, shortest paths, memory and use cases, with interactive visualizers for both.
Breadth-first search (BFS) explores a graph level by level with a queue; depth-first search (DFS) dives down one branch with a stack (or recursion). Both visit every node in O(V + E) but suit different problems.
BFS vs DFS at a glance
| BFS | DFS | |
|---|---|---|
| Data structure | Queue (FIFO) | Stack / recursion |
| Shortest path (unweighted) | Yes | No |
| Memory | Wide frontier | Path depth |
| Best for | Shortest paths, levels | Cycles, topological sort, mazes |
When to use BFS
Use BFS for shortest paths on unweighted graphs and level-order traversal.
When to use DFS
Use DFS for cycle detection, topological sorting, and exploring all paths.
Tools for BFS & DFS
幅優先探索(BFS)ビジュアライザー
グリッド上でインタラクティブに幅優先探索を体験できるツール。壁を描き、スタート地点とゴール地点を自由に動かし、迷路を自動生成しながら、探索が層ごとに広がっていく様子をステップ単位で観察できます。ブラウザだけですぐに動きます。
ツールを開く深さ優先探索（DFS）ビジュアライザー
グリッド上でインタラクティブに深さ優先探索を体験。壁を描いたり、スタート/ゴール地点を動かしたり、迷路を生成したり、探索の様子をステップごとに確認できます。ブラウザ上ですぐに動作します。
ツールを開くダイクストラ法ビジュアライザー
グリッド上でダイクストラ法による経路探索を可視化。壁を描き、始点・終点を動かし、迷路を生成し、探索の進行をステップごとに確認できます。すべてブラウザ上で動作します。
ツールを開く迷路ジェネレーター
再帰分割法（recursive division）によるアニメーション付き迷路ジェネレーター — 壁が組み上がっていく過程をステップごとに確認し、速度を調整して、新しい迷路を何度でも生成できます。経路探索アルゴリズムのビジュアライザーと組み合わせて使うのに最適です。すべてブラウザ上で完結します。
ツールを開くBFS vs DFS
再帰分割アルゴリズムはどのように迷路を作るのですか？
まず何もない空間から始め、各区画をランダムな位置に隙間を残した1本の直線の壁で再帰的に仕切っていきます。これを区画がそれ以上分割できなくなるまで繰り返します。
「完全な迷路」とは何ですか？
任意の2マス間にちょうどひとつの経路しか存在しない迷路のことです——ループも孤立した領域もありません。再帰分割アルゴリズムは常に完全な迷路を生成します。
この迷路を解くことはできますか？
はい——同じ方眼グリッドを使うBFS、Dijkstra、A*のビジュアライザーにレイアウトをコピーすれば、経路探索アルゴリズムがどのように迷路を進んでいくか確認できます。
他にどんな迷路生成アルゴリズムがありますか？
Recursive backtracker（ランダム化DFS）、Prim法、Kruskal法、Wilson法、Eller法などがあり、それぞれ見た目の異なる構造の迷路が生成されます。