はじめに：ツリー探索アルゴリズムとは？
コンピュータの世界では、情報を整理するために「ツリー構造」という形式がよく使われます。これは、木の幹から枝が分かれ、さらにその先で葉が茂るように、データが階層的に繋がっている状態を指します。
「ツリー探索アルゴリズム」とは、このツリー構造の中から、目的のデータを見つけ出すための効率的な手順や方法のことです。大量のデータの中から特定の情報を素早く見つけ出すために、様々な場面で活用されています。
基本のキ：ツリー構造を理解しよう
探索アルゴリズムを学ぶ前に、まずは探索の対象となる「ツリー構造」について理解しましょう。
ツリー構造は、1つの「ノード」（要素）が複数の「子ノード」を持ち、その子ノードがさらに「孫ノード」を持つ…という形で、階層的にデータが枝分かれしていく構造です。 例えば、パソコンのフォルダ（ディレクトリ）構造もツリー構造の一例です。
- ルート (Root): ツリーの最上部に位置する、親を持たないノード。
- ノード (Node): ツリーを構成する一つ一つの要素。
- エッジ (Edge): ノード間の繋がりを示す線。
- 親ノード (Parent) / 子ノード (Child): 直接繋がっているノード間の関係。
- 葉 (Leaf): 子を持たない、末端のノード。
代表的な2つの探索アルゴリズム
ツリー探索には様々な種類がありますが、ここでは最も基本的で重要な2つのアルゴリズム、「深さ優先探索」と「幅優先探索」を紹介します。
深さ優先探索 (DFS: Depth-First Search)
深さ優先探索は、その名の通り「行けるところまで深く」進んでから探索する方法です。 あるルートを進んでいき、行き止まり（葉ノード）にたどり着いたら、一つ前に戻って別のルートを進みます。この動きを繰り返して、すべてのノードを調べていきます。
迷路を解くときに、とりあえず片方の壁に沿ってずっと進んでみる方法に似ています。
Pythonでの簡単な実装例（再帰版）
# ツリーのノードを表すクラス
class Node: def __init__(self, value): self.value = value self.children = []
# 深さ優先探索を行う関数
def depth_first_search(node): # 現在のノードの値を表示 print(node.value) # 子ノードに対して再帰的に関数を呼び出す for child in node.children: depth_first_search(child)
# （ツリーの構築部分は省略） 幅優先探索 (BFS: Breadth-First Search)
幅優先探索は、「現在地から近いところを順番に」探索していく方法です。 まずルートノードを調べ、次にルートノードの全ての子ノードを調べます。その後、子ノードのさらに子（孫ノード）を全て調べる、というように、階層ごとに横に広がるように探索を進めます。
この特性から、スタート地点からゴールまでの最短経路を見つける問題でよく利用されます。
Pythonでの簡単な実装例
from collections import deque
# ツリーのノードを表すクラス (DFSと同じ)
class Node: def __init__(self, value): self.value = value self.children = []
# 幅優先探索を行う関数
def breadth_first_search(root): if root is None: return # 探索対象のノードを格納するキューを用意 queue = deque([root]) while queue: # キューの先頭からノードを取り出す current_node = queue.popleft() # 現在のノードの値を表示 print(current_node.value) # 子ノードをキューの末尾に追加する for child in current_node.children: queue.append(child)
# （ツリーの構築部分は省略） どっちを使う？ DFSとBFSの比較
深さ優先探索（DFS）と幅優先探索（BFS）は、それぞれに得意なことと不得意なことがあります。問題の性質によって使い分けることが重要です。
| 特徴 | 深さ優先探索 (DFS) | 幅優先探索 (BFS) |
|---|---|---|
| 探索の進め方 | 縦方向（深く）に進む | 横方向（広く）に進む |
| 使用するデータ構造 | スタック（再帰呼び出しで暗黙的に使われる） | キュー |
| メモリ使用量 | ツリーが深いと多く消費する傾向がある | ツリーの幅が広いと多く消費する傾向がある |
| 主な応用例 | 連結成分の検出、トポロジカルソート、全ての解を列挙する場合 | 重みのないグラフの最短経路探索 |
| 解の発見 | 最初に見つかる解が最適（最短）とは限らない | 最初に見つかった解が最短経路となる |
実世界での応用例
ツリー探索アルゴリズムは、私たちの身近なところでたくさん活躍しています。
- ファイルシステムの検索: 特定のファイルをフォルダの中から探し出すときに使われます。
- ウェブクローラー: 検索エンジンがウェブページを収集する際、ページ内のリンクをたどって新しいページを発見するのに使われます。
- 人工知能 (AI) の意思決定: チェスや将棋などのゲームAIが、次の最適な一手を考えるために、膨大な手筋のパターン（ツリー）を探索します。
- ネットワークのルーティング: カーナビや乗り換え案内アプリで最短経路を計算する際、BFSが応用されています。
- データベースのインデックス: 大量のデータから高速に情報を検索するための内部的な仕組みとして、B木などの探索木が使われています。
まとめ
ツリー探索アルゴリズムは、階層的なデータの中から効率的に目的のものを探し出すための基本的ながら非常に強力なツールです。
「深さ優先探索(DFS)」は深く掘り進むスタイル、「幅優先探索(BFS)」は広く浅く探すスタイルで、それぞれに得意な場面があります。これらの基本的なアルゴリズムを理解することは、より複雑な問題解決やプログラミングの世界への第一歩となるでしょう。