Java | ツリー構造の探索アルゴリズム

ツリー構造の探索アルゴリズム（後半）

前半では、ツリー構造の基本と DFS（深さ優先探索）を中心に解説しました。 後半では、より実務的な探索アルゴリズムとして BFS（幅優先探索）、 そして 非再帰 DFS/BFS、さらに 検索・集計・フィルタリングへの応用、 最後に セキュリティとパフォーマンスの観点まで踏み込んでいきます。

ツリー探索は「再帰で書けるから簡単」というイメージを持ちやすいですが、 実務では入力の深さ・データ量・安全性を考慮した設計が求められます。 そのため、後半は「現場で使えるツリー探索」をテーマにしています。

幅優先探索（BFS）とは何か

DFSが「一つの枝を深く潜る」探索だったのに対し、 BFS（Breadth-First Search）は「同じ階層を横に広く探索する」方法です。

イメージとしては、フォルダ階層を調べるときに 「まず root の直下のフォルダを全部見る → 次にその子フォルダを全部見る」 という順番で探索する形です。

BFSは キュー（Queue） を使って実装するのが定番です。

Javaで書く幅優先探索（BFS）

前半で使った Node クラスをそのまま使います。

import java.util.LinkedList;
import java.util.Queue;

public static void bfs(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.println(node.name);

        for (Node child : node.children) {
            queue.add(child);
        }
    }
}

import java.util.LinkedList;
import java.util.Queue;

public static void bfs(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        System.out.println(node.name);

        for (Node child : node.children) {
            queue.add(child);
        }
    }
}

このコードは、次の順番でノードを訪れます。

root child1 child2 grandchild1 grandchild2

DFSとは順番が異なることが分かります。

深掘り：DFS と BFS の違いを「構造」で理解する

DFS 深く潜る → 再帰と相性が良い ツリーの「構造」をたどるのに向いている 探索順が「階層」より「枝」に依存する

BFS 横に広く探索する → キューと相性が良い 「最短距離」や「階層ごとの処理」に向いている 探索順が「階層」に依存する

特に重要なのは、BFSが「階層ごとの処理」に強いという点です。 例えば「root からの距離（深さ）を求めたい」「階層ごとに集計したい」などの場面では、 DFSよりもBFSが自然に書けます。

非再帰 DFS（スタックを使う DFS）

再帰DFSは美しく書けますが、深いツリーでは StackOverflowError の危険があります。 そのため、実務では「自前のスタックを使った DFS」を使うことがあります。

import java.util.Stack;

public static void dfsNonRecursive(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        System.out.println(node.name);

        for (int i = node.children.size() - 1; i >= 0; i--) {
            stack.push(node.children.get(i));
        }
    }
}

import java.util.Stack;

public static void dfsNonRecursive(Node root) {
    Stack<Node> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        Node node = stack.pop();
        System.out.println(node.name);

        for (int i = node.children.size() - 1; i >= 0; i--) {
            stack.push(node.children.get(i));
        }
    }
}

ここで重要なのは、子ノードを「逆順」でスタックに積んでいる点です。 スタックは LIFO（後入れ先出し）なので、逆順に積むことで DFS の順番を再現できます。

深掘り：なぜ非再帰 DFS が必要なのか

非再帰 DFS のメリットは次のような場面で発揮されます。

深さが非常に大きいツリー ユーザー入力から生成されるツリー（攻撃者が深さを操作できる） 再帰禁止の環境（組み込み系など） スタックの使用量を制御したい場面

特にセキュリティの観点では、 「入力によって再帰の深さが決まる」処理は危険です。 攻撃者が極端に深い構造を送り込むと、 再帰がスタックを使い果たしてサービスが落ちる可能性があります。

非再帰 DFS はこの問題を回避するための重要な手段です。

ツリー探索の応用：検索・集計・フィルタリング

ツリー探索は「ノードを訪れる順番」を決めるだけではありません。 実務では、探索しながら「検索」「集計」「フィルタリング」を行うことが多いです。

例：特定の名前を持つノードを検索する（DFS）

public static Node find(Node root, String target) {
    if (root.name.equals(target)) {
        return root;
    }
    for (Node child : root.children) {
        Node result = find(child, target);
        if (result != null) return result;
    }
    return null;
}

public static Node find(Node root, String target) {
    if (root.name.equals(target)) {
        return root;
    }
    for (Node child : root.children) {
        Node result = find(child, target);
        if (result != null) return result;
    }
    return null;
}

DFSは「見つかったらすぐに返す」処理が自然に書けます。

例：階層ごとのノード数を数える（BFS）

public static void countByLevel(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        System.out.println("Level " + level + ": " + size + " nodes");

        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            for (Node child : node.children) {
                queue.add(child);
            }
        }
        level++;
    }
}

public static void countByLevel(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    int level = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        System.out.println("Level " + level + ": " + size + " nodes");

        for (int i = 0; i < size; i++) {
            Node node = queue.poll();
            for (Node child : node.children) {
                queue.add(child);
            }
        }
        level++;
    }
}

BFSは「階層ごとの処理」が自然に書けるため、 集計や分析に向いています。

セキュリティの観点から見たツリー探索

ツリー探索は便利ですが、セキュリティの観点では注意すべき点があります。

入力によって深さが変わる再帰は危険

攻撃者が「極端に深い JSON」や「深すぎるフォルダ構造」を送り込むと、 再帰DFSがスタックを使い果たしてサービスが落ちる可能性があります。

安全にするための対策

深さの上限を設ける 非再帰 DFS/BFS を使う 入力データを検証する 処理時間やノード数に制限を設ける

ツリー探索は「構造が深くなりやすい」ため、 セキュリティスペシャリストは常に深さとデータ量を監視します。

パフォーマンスの観点から見た DFS と BFS

DFS メモリ消費が少ない（深さ分だけ） 深い探索に強い 検索が早く終わることがある（見つかる位置による）

BFS 階層ごとの処理が得意 最短距離の探索に強い 幅が広いツリーではメモリ消費が大きくなる

実務では、次のように使い分けます。

深さが重要 → DFS 階層が重要 → BFS 最短距離を求めたい → BFS 深さが不明で危険 → 非再帰 DFS

後半のまとめ

後半では、ツリー探索を実務レベルで使いこなすための内容を扱いました。

幅優先探索（BFS） 非再帰 DFS（スタック） 検索・集計・フィルタリングへの応用 セキュリティとパフォーマンスの観点

ツリー探索は「構造をどうたどるか」を決めるだけでなく、 実務では「どう安全に」「どう効率的に」処理するかが重要になります。