深さ優先探索（DFS）ビジュアライザー
グリッド上でインタラクティブに深さ優先探索を体験。壁を描いたり、スタート/ゴール地点を動かしたり、迷路を生成したり、探索の様子をステップごとに確認できます。ブラウザ上ですぐに動作します。
Click & drag on the grid to draw walls · drag the green and red squares to move start / goal · then press Play. Want a challenge? Hit 自分でプレイ and solve the maze by hand.
Move the indigo token with ↑ ↓ ← → / WASD (or tap an adjacent cell) from the green start to the red goal. Walls block you.
疑似コード
Time · Space
使い方
- 1 クリック＆ドラッグで壁を描画します。青いスタート地点や赤いゴール地点をドラッグすると位置を変更できます。
- 2 Playボタンを押すと、DFSが1つの経路を深く掘り進めてから引き返す様子を確認できます。
- 3 Mazeボタンで一瞬で障害物を生成したり、Stepボタンでノードを1つずつ進めたりできます。
- 4 DFSが見つける経路はゴールには到達しますが、多くの場合最短経路ではありません。
このツールを使う理由
- DFSが一方向にひたすら突き進み、行き詰まったときだけ引き返す様子を観察できます。
- DFSがなぜ最短経路を保証しないのかを理解できます。
- DFSの深く掘り進むアプローチを、BFSの均等に広がる探索やA*のゴールを目指す探索と比較できます。
- すべてブラウザ内で完結します。登録もアップロードも不要です。
よくある質問
深さ優先探索（DFS）とは何ですか？
DFSは、スタックや再帰を使いながら、各分岐を可能な限り深く進んでから引き返すことでグラフを探索するアルゴリズムです。
DFSの時間計算量はどれくらいですか？
O(V + E) です。BFSと同様に、各頂点と各辺をそれぞれ一度だけ調べます。
DFSは最短経路を見つけられますか？
いいえ。DFSは経路が存在すればそれを見つけますが、最初に出会った分岐をそのまま進むため、結果は最短経路より長くなることが多いです。最短経路が必要な場合はBFS、ダイクストラ法、またはA*を使用してください。
DFSはどのような問題に向いていますか？
トポロジカルソート、閉路検出、連結成分の探索、迷路生成など、最も近いゴールを探すのではなく構造全体を網羅的に調べる必要がある問題に適しています。
深さ優先探索（DFS）ビジュアライザー とは？
深さ優先探索（DFS）ビジュアライザーは、スタック構造を使ってDFSがグリッド上で1つの経路を可能な限り深く進み、行き止まりに突き当たると引き返す様子を再現するツールです。ゴールまでの経路は見つかりますが、BFSとは異なり、その経路が最短になるとは限りません。
機能
ステップごとのアニメーション
各枝を深く潜り、バックトラックしていく探索の様子を確認できます。
計算量
時間計算量: O(V + E)。空間計算量: スタック/再帰のために O(V)。
完全プライベート
すべてブラウザ内で実行され、何もアップロードされません。
例
Input
graph 1–2, 1–3, 2–4, 3–4; start 1Output
visit order: 1 → 2 → 4 → 3 (deep, then backtrack)主な用途
-
1
閉路検出
DFS が閉路を示す後退辺をどのように見つけるかを確認できます。
-
2
トポロジカルソート
DAG に対する DFS ベースの順序付けを理解します。
-
3
連結成分
開始ノードからの到達可能性を余すことなく探索します。
Zerethon の DFS ビジュアライザーは、ブラウザ上でグラフの深さ優先探索をアニメーション表示し、スタックまたは再帰を使って各枝をバックトラックする前にできるだけ深く探索します。DFS は O(V + E) 時間、O(V) 空間で実行されます。これは閉路検出、トポロジカルソート、連結性判定の基盤となるアルゴリズムです。
- カテゴリ
- アルゴリズム
- 料金
- 無料
- プライバシー
- ブラウザベース
- 登録
- 不要
参考文献
- MIT OCW 6.006 — Introduction to Algorithms (CLRS) — MIT OpenCourseWare
- VisuAlgo — DFS/BFS — VisuAlgo (NUS)
- Depth-first search — Wikipedia
プライバシー
明記されない限り、データがブラウザの外に送信されることはありません。深さ優先探索（DFS）ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。
初めての方へ。Big-O 解析付きのステップバイステップ解説を読む: Graph Algorithms を学ぶ →
比較
関連ツール
ダイクストラ法ビジュアライザー
グリッド上でダイクストラ法による経路探索を可視化。壁を描き、始点・終点を動かし、迷路を生成し、探索の進行をステップごとに確認できます。すべてブラウザ上で動作します。
ツールを開くA*経路探索ビジュアライザー
マンハッタン距離ヒューリスティックを使ったA*経路探索をグリッド上でインタラクティブに可視化。壁を描いてスタート/ゴールを動かし、迷路を自動生成し、探索をステップごとに実行できます。すべてブラウザ内で完結します。
ツールを開く幅優先探索(BFS)ビジュアライザー
グリッド上でインタラクティブに幅優先探索を体験できるツール。壁を描き、スタート地点とゴール地点を自由に動かし、迷路を自動生成しながら、探索が層ごとに広がっていく様子をステップ単位で観察できます。ブラウザだけですぐに動きます。
ツールを開くバブルソート ビジュアライザー
バブルソートの動きをアニメーションで確認できるツール。ステップ実行や速度調整、カスタム入力データ、比較・交換回数のリアルタイム表示、擬似コードの表示に対応しています。すべてブラウザ内だけで動作します。
ツールを開くZerethon Social で作成・共有・成長しよう
無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。