本記事では、**木（ツリー）**を用いた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) … のようになる。

どちらの探索アルゴリズムも、木やグラフでよく使われる基本的な手法です。探索順を図示すると、どの順番でノードを訪れているかが一目でわかり、理解が深まりました。