🎯 はじめに
みなさんこんにちは！
ツリー探索アルゴリズムって、教科書で勉強するときは理解したつもりでも、実際に動きを見ないと「BFSとDFSって何が違うんだっけ？」となりませんか？そこで、React + TypeScript + Vis.jsを使って、ツリー探索アルゴリズムの動きをリアルタイムで可視化するWebアプリを作ってみました。
この記事では、アルゴリズムの基本的な説明から、実装で工夫した点、そして可視化することで得られる学習効果まで、順を追って解説していきます。
🎮 デモプレイ
💻 ソースコード
🔍 ツリー探索アルゴリズムとは
ツリー探索アルゴリズムは、**データ構造として表現されたツリー（木構造）**や、問題の解空間をツリー状に抽象化した状態空間の中から、特定のノードや目的の状態を見つけ出すための手法群です。
具体的には、ノード（頂点）とエッジ（辺）で構成されるツリー構造において、ルートノードから出発し、効率的にノードを系統的に調べていく方法を指します。
📌 本アプリで扱う2つのアルゴリズム
幅優先探索（BFS: Breadth-First Search）
幅優先探索は、ルートノードから始めて、階層ごとに順番にノードを訪問していくアルゴリズムです。
特徴
- キュー（FIFO: First In First Out）を使用
- 同じ階層のノードを左から右に順番に処理
- 最短経路を見つけるのに適している
動作イメージ
1
/ \
2 3
/ \
4 5
訪問順: 1 → 2 → 3 → 4 → 5
深さ優先探索（DFS: Depth-First Search）
深さ優先探索は、できるだけ深く探索してから、戻って次の枝を探索するアルゴリズムです。訪問タイミングによって3つのバリエーションがあります。
DFS Preorder（前順）
特徴
- スタック（LIFO: Last In First Out）を使用
- ノードに到達したらすぐに処理
- ツリーのコピーに適している
訪問順序
- 現在のノードを処理
- 左の子を処理
- 右の子を処理
訪問順: 1 → 2 → 4 → 5 → 3
DFS Inorder（中順）
特徴
- 二分探索木で使うと昇順にソートされた結果が得られる
- 左 → 親 → 右の順で処理
訪問順序
- 左の子を処理
- 現在のノードを処理
- 右の子を処理
訪問順: 4 → 2 → 5 → 1 → 3
DFS Postorder（後順）
特徴
- ツリーの削除処理に適している
- 子ノードを全て処理してから親を処理
訪問順序
- 左の子を処理
- 右の子を処理
- 現在のノードを処理
訪問順: 4 → 5 → 2 → 3 → 1
各アルゴリズムの比較
| アルゴリズム | データ構造 | 訪問順序 | 用途・特徴 |
|---|---|---|---|
| BFS | キュー | 階層ごと（横方向） | 最短経路探索、同階層の処理 |
| DFS Preorder | スタック | 親→左→右 | ツリーのコピー、構造の保存 |
| DFS Inorder | スタック | 左→親→右 | 二分探索木のソート済み出力 |
| DFS Postorder | スタック | 左→右→親 | ツリーの削除、後処理が必要な操作 |
時間計算量: すべてO(n) - 全ノードを1回ずつ訪問
空間計算量:
- BFS: O(w) - wは最大幅
- DFS: O(h) - hは高さ
🖥️ アプリの使い方
🚶 基本操作
-
ツリーの生成
- 「ノード数」で5〜50個の範囲で設定
- 「生成パターン」でツリーの種類を選択（ランダム、二分探索木、AVL木、赤黒木、Min-Heap、Max-Heap）
- 「データ生成」ボタンでツリーを作成
-
アルゴリズムの選択と実行
- 「アルゴリズム」ドロップダウンから探索方法を選択
- 「アニメーション速度」スライダーで再生速度を調整
- 「実行」ボタンでアニメーション開始
-
再生コントロール
- 実行中は「一時停止」ボタンで停止可能
- 停止中は「再開」ボタンで続きから再生
- 「リセット」ボタンで初期状態に戻す
-
目標値の設定（オプション）
- 「目標値」に数値を入力すると、その値が見つかった時点で探索終了
- 未設定の場合は全ノードを探索
⚖️ 状態表示
アニメーション中、ノードは状態によって色分けされます。
| 色 | 状態 | 説明 |
|---|---|---|
| 灰色 | 未訪問 | まだ処理されていないノード |
| 青色 | 処理中 | 現在訪問しているノード |
| 黄色 | キュー/スタック待ち | 次に処理される予定のノード |
| 緑色 | 訪問済み | 既に処理が完了したノード |
🔄 比較モード
画面上部の「比較モード」ボタンをクリックすると、2つのアルゴリズムを同時に実行できます。
- 左右それぞれでアルゴリズムを選択可能
- 同じツリー構造に対して異なるアルゴリズムを適用
- 各アルゴリズムのステップ数や実行ログを並べて比較
- 探索順序の違いが一目瞭然
💡 実装の工夫点
ツリー構造の可視化
ツリーの描画には、グラフ可視化ライブラリのVis.jsを採用しました。
Vis.jsは、ノードとエッジの自動レイアウト機能が優れており、階層的なツリー構造を美しく表示できます。また、ノードの色やスタイルを動的に変更できるため、アニメーション中の状態変化をリアルタイムに反映できます。
ツリーデータからVis.js用のグラフデータへの変換は、再帰的な走査で実現しています。この変換処理は純粋関数として実装されているため、同じツリー構造からは常に同じグラフが生成され、予測可能な動作が保証されます。
多様なツリー生成パターン
学習効果を高めるため、6種類のツリー生成パターンを用意しました。
ランダムツリーは基本的な動作確認に適しています。二分探索木やAVL木では、Inorderでソート済みの順序が得られることを確認できます。ヒープ構造では、親子の大小関係が保たれることを視覚的に理解できます。
各パターンの生成アルゴリズムは、データ構造の教科書に沿った実装になっており、正しい構造が生成されるよう注意深く設計されています。特にAVL木では、挿入時の回転処理を実装し、常にバランスが保たれるようにしています。
📚 可視化で得られる学習効果
アルゴリズムの動作原理の直感的理解
最大の学習効果は、アルゴリズムの動作を目で見て理解できることです。
教科書では「BFSはキューを使う」と書かれていても、実際にどうキューが動くのかイメージしにくいものです。しかし、アニメーションでノードが黄色になり（キュー待ち）、青になり（処理中）、緑になる（訪問済み）過程を見ることで、キューの動作が腹落ちします。
特に、DFSの3つのバリエーション（Preorder、Inorder、Postorder）の違いは、言葉で説明されるより、実際に動きを比較した方が圧倒的に理解しやすいでしょう。
データ構造との関係性の理解
ツリーの生成パターンを変えることで、データ構造とアルゴリズムの関係も学べます。
例えば、二分探索木にDFS Inorderを実行すると、ノードが昇順に訪問されることが視覚的に分かります。これは、二分探索木の「左の子 < 親 < 右の子」という性質と、Inorderの「左→親→右」という訪問順序が組み合わさった結果です。
また、ヒープ構造では、BFSで訪問すると配列の並び順と一致することが確認できます。これにより、ヒープが配列で効率的に表現できる理由が理解できます。
アルゴリズムの選択基準の習得
比較モードを使うことで、問題に応じた適切なアルゴリズムの選び方を学べます。
同じツリーに対してBFSとDFSを実行し、訪問順序の違いを観察することで、「最短経路を求めるならBFS」「メモリ効率を優先するならDFS」といった選択基準が体感的に身につきます。
また、ステップ数の比較により、同じ結果を得るのにどちらが効率的か、数値で判断できるようになります。
🎓 まとめ
ツリー探索アルゴリズムの可視化アプリを作成し、アルゴリズム学習における可視化の重要性を実感しました。
特に以下の点で学習効果が高いと感じています。
- 抽象的な概念を具体的なアニメーションで理解できる
- 複数のアルゴリズムを並べて比較できる
- 自分のペースで一時停止しながら学習できる
- データ構造とアルゴリズムの関係性を体感できる
今後は、他の木構造（B木、トライ木など）や、グラフ探索アルゴリズム（ダイクストラ法、A*など）の可視化にも挑戦してみたいと思います。
プログラミング学習において、「百聞は一見に如かず」という言葉は真実です。可視化ツールを活用して、楽しく効率的に学習を進めていきましょう。