本記事では、**木（ツリー）**を用いたDFS（深さ優先探索）とBFS（幅優先探索）の「探索順」を、視覚的に示した図を解説とともに紹介します。どのノードをどのタイミングで探索するのかイメージしやすくなるよう、簡単な木構造を例に取り上げます。
木を用いた探索順の可視化
ツリー構造の例
以下のような 5ノード からなるツリーを想定します。
(0)
/ \
(1) (2)
/ / \
(3) (4) (5)
- ここではノードを (0), (1), (2), (3), (4), (5) とラベル付けしており、ルートノードを (0) とします。
- (1) の子として (3)、 (2) の子として (4) と (5) を配置しています。
- なお、ノード (5) を追加するかは自由ですが、例示のため増やしてみました。
このツリーを使い、DFS と BFS の探索順がどのように変わるかを見ていきます。
深さ優先探索（DFS）のイメージ
探索の流れ
- ルートノード (0) から探索を始める。
- (0) を訪問。
- (0) の最初の子ノード (1) に進む（可能な限り深く進む）。
- (1) を訪問。
- (1) の最初の子ノード (3) に進む。
- (3) を訪問。
- (3) に子ノードがなければ行き止まりなので、一段階戻る（ (1) に戻る）。
- (1) の次の子がなければ、さらに戻って (0) に戻る。
- (0) の次の子ノード (2) に進む。
- (2) を訪問。
- (2) の最初の子 (4) に進む。
- (4) を訪問。行き止まりなので (2) に戻る。
- (2) の次の子 (5) に進む。
- (5) を訪問。行き止まりなので (2) に戻る。
- (2) に子がもうなければ (0) に戻り、さらに未訪問の子がなければ探索終了。
DFSの探索順
実際の探索順は次のようになります:
(0) → (1) → (3) → (戻る→(1)) → (戻る→(0)) → (2) → (4) → (戻る→(2)) → (5) → (戻る→(2)) → (戻る→(0))
訪問の順番を抜き出すと、
[0, 1, 3, 2, 4, 5]
という順番になります（※戻ったタイミングは省略して、**「訪れたノードの順番」**だけをリストアップしています）。
図で表すと下記イメージです。
(0) --- 最初に訪問
/ \
(1) (2) --- (1) 次, (2) は(1)の後
/ / \
(3) (4) (5) --- (3)→(4)→(5)の順で最深部に進む
- 探索順: 0 → 1 → 3 → (戻) → 2 → 4 → (戻) → 5 → (戻)
幅優先探索（BFS）のイメージ
探索の流れ
- ルートノード (0) を最初に訪問し、キューに (0) を入れる。
- キューの先頭 (0) を取り出して、隣接ノード（子ノード） (1), (2) をキューに順番に追加する。
- 次にキューの先頭 (1) を取り出す。 (1) の子ノード (3) をキューに追加する。
- 次に (2) を取り出す。 (2) の子ノード (4) と (5) をキューに追加する。
- 次に (3), (4), (5) の順に取り出し、それぞれの子ノードをキューに追加…（無いのでそのまま終了）。
BFSの探索順
実際の訪問順:
(0) → (1) → (2) → (3) → (4) → (5)
図で表すと下記イメージです。
(0) --- 最初に訪問
/ \
(1) (2) -- (1) と (2) は同じ「階層」なので連続で訪問
/ / \
(3) (4) (5) -- 次の階層 (3),(4),(5) を順に訪問
- 最初に (0)
- 次のレベルで (1), (2) を訪問
- さらに次のレベルで (3), (4), (5) を訪問
DFS/BFSの木構造サンプルコード（Java）
木のノード定義
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int val;
List<TreeNode> children;
public TreeNode(int val) {
this.val = val;
this.children = new ArrayList<>();
}
public void addChild(TreeNode child) {
this.children.add(child);
}
}
DFS実装（再帰）
public class TreeDFS {
public static void dfs(TreeNode node) {
if (node == null) return;
// ノードを訪問（出力）
System.out.print(node.val + " ");
// 子ノードを再帰的にDFS
for (TreeNode child : node.children) {
dfs(child);
}
}
public static void main(String[] args) {
// 木を構築
TreeNode root = new TreeNode(0);
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
root.addChild(node1);
root.addChild(node2);
node1.addChild(node3);
node2.addChild(node4);
node2.addChild(node5);
/* 木構造: (0)-(1)-(3), (0)-(2)-(4,5) */
System.out.print("DFS Order: ");
dfs(root); // 期待出力: 0 1 3 2 4 5
System.out.println();
}
}
BFS実装（キュー）
import java.util.LinkedList;
import java.util.Queue;
public class TreeBFS {
public static void bfs(TreeNode root) {
if (root == null) return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
System.out.print(current.val + " ");
// 子ノードをキューに追加
for (TreeNode child : current.children) {
queue.add(child);
}
}
}
public static void main(String[] args) {
// 木を構築
TreeNode root = new TreeNode(0);
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
root.addChild(node1);
root.addChild(node2);
node1.addChild(node3);
node2.addChild(node4);
node2.addChild(node5);
/* 木構造: (0)-(1)-(3), (0)-(2)-(4,5) */
System.out.print("BFS Order: ");
bfs(root); // 期待出力: 0 1 2 3 4 5
System.out.println();
}
}
まとめ
-
DFS:
- 再帰やスタックを利用し、深く進んで戻ってを繰り返す。
- 順番としては (0)→(1)→(3)→…→(2)→(4)→(5) … のような形になる。
-
BFS:
- キューを利用し、浅い階層（近いノード）を先に探索してから次の階層へ進む。
- 順番としては (0)→(1)→(2)→(3)→(4)→(5) … のようになる。
どちらの探索アルゴリズムも、木やグラフでよく使われる基本的な手法です。探索順を図示すると、どの順番でノードを訪れているかが一目でわかり、理解が深まりました。