Java | 木構造の最短経路・距離計算

Javaで学ぶ「木構造の最短経路・距離計算」（前半）

木構造の「距離」や「最短経路」は、アルゴリズムの世界でも実務でもよく登場するテーマです。 フォルダ間の距離、組織図での上下関係の距離、ネットワーク構造の距離など、 「ノード同士がどれくらい離れているか」を知りたい場面は意外なほど多くあります。

前半では、まず木構造の基本的な性質を確認しながら、 「距離とは何か」「最短経路とは何か」を丁寧にかみ砕き、 Javaで書けるシンプルな距離計算から始めていきます。 後半では、より応用的な「任意の二ノード間の距離」や「木の直径」などに踏み込みます。

木構造における「距離」とは何か

木構造における距離とは、基本的に「ノード間の辺の本数」です。 例えば、次のような木を考えます。

• root
  • A
    • C
  • B

root と A の距離は 1（root → A） root と C の距離は 2（root → A → C） A と C の距離は 1（A → C） B と C の距離は 3（B → root → A → C）

このように、「何本の辺を通れば到達できるか」が距離の定義になります。 木構造ではループがないため、「最短経路」は常に一意に決まるという性質があります。 これはグラフ一般よりも扱いやすいポイントです。

Javaで木構造を表現する基本クラス

まずは、汎用的な木構造を表現するクラスを用意します。 前のテーマでも使ったような、シンプルな Node クラスを使います。

import java.util.ArrayList;
import java.util.List;

class Node {
    String name;
    List<Node> children;

    Node(String name) {
        this.name = name;
        this.children = new ArrayList<>();
    }

    void addChild(Node child) {
        children.add(child);
    }
}

import java.util.ArrayList;
import java.util.List;

class Node {
    String name;
    List<Node> children;

    Node(String name) {
        this.name = name;
        this.children = new ArrayList<>();
    }

    void addChild(Node child) {
        children.add(child);
    }
}

このクラスを使って、次のような木を作ることができます。

Node root = new Node("root");
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");

root.addChild(a);
root.addChild(b);
a.addChild(c);

Node root = new Node("root");
Node a = new Node("A");
Node b = new Node("B");
Node c = new Node("C");

root.addChild(a);
root.addChild(b);
a.addChild(c);

この木は、先ほどの例と同じ構造です。 ここから、「距離」や「最短経路」を計算するアルゴリズムを考えていきます。

根から特定ノードまでの距離を計算する（DFSでの深さ）

最初のステップとして、「根から特定ノードまでの距離」を計算してみます。 これは、木構造の「深さ」を求める問題とほぼ同じです。

考え方はシンプルで、「根からスタートして、再帰的に子をたどりながら、今の深さを持ち歩く」という形になります。

public static int distanceFromRoot(Node root, String target) {
    return dfs(root, target, 0);
}

private static int dfs(Node node, String target, int depth) {
    if (node.name.equals(target)) {
        return depth;
    }
    for (Node child : node.children) {
        int d = dfs(child, target, depth + 1);
        if (d != -1) {
            return d;
        }
    }
    return -1; // 見つからなかった場合
}

public static int distanceFromRoot(Node root, String target) {
    return dfs(root, target, 0);
}

private static int dfs(Node node, String target, int depth) {
    if (node.name.equals(target)) {
        return depth;
    }
    for (Node child : node.children) {
        int d = dfs(child, target, depth + 1);
        if (d != -1) {
            return d;
        }
    }
    return -1; // 見つからなかった場合
}

このコードでは、depth が「根から現在のノードまでの距離」を表しています。 ターゲットに一致した瞬間に、その depth を返します。

深掘り：この距離計算の流れを頭の中で追う

例えば、先ほどの木で distanceFromRoot(root, "C") を呼び出したとします。

最初に dfs(root, "C", 0) が呼ばれます。 root は “C” ではないので、子である A と B に対して再帰が行われます。

A に対して dfs(a, "C", 1) が呼ばれます。 A も “C” ではないので、子である C に対して再帰が行われます。

C に対して dfs(c, "C", 2) が呼ばれます。 ここで node.name.equals(target) が真になり、depth である 2 が返されます。

このように、「深さを1ずつ増やしながら再帰する」ことで、 根から特定ノードまでの距離を自然に計算できます。

任意の二ノード間の距離の考え方（まずは概念から）

根からの距離は比較的簡単ですが、 「任意の二ノード間の距離」を求めたい場面も多くあります。

例えば、組織図で「社員Aと社員Bの距離」 フォルダ構造で「フォルダXとフォルダYの距離」 ネットワーク構造で「ノードPとノードQの距離」などです。

木構造では、任意の二ノード間の距離は次のように考えられます。

1つ目のノードから共通の祖先までの距離 2つ目のノードから共通の祖先までの距離 それらを足したものが、二ノード間の距離になる

この「共通の祖先」を、アルゴリズムの世界では LCA（Lowest Common Ancestor：最小共通祖先） と呼びます。 前半では、まずこの考え方を概念として押さえておき、 後半で具体的な実装に踏み込みます。

距離計算と「深さ」の関係

距離計算を理解するうえで、「深さ」という概念が非常に重要です。 深さとは、「根から何本の辺を通ったか」という値です。

例えば、先ほどの木では

root の深さは 0 A と B の深さは 1 C の深さは 2

となります。

任意の二ノード間の距離を求めるとき、 深さと LCA を使うと次のような式で表現できます。

距離(u, v) = depth(u) + depth(v) − 2 × depth(LCA(u, v))

この式は後半で詳しく扱いますが、 今の段階では「距離計算は深さと共通祖先の組み合わせで考えられる」というイメージだけ持っておいてください。

幅優先探索（BFS）で距離を計算する考え方

距離計算は DFS だけでなく、BFS とも相性が良いです。 特に「根からすべてのノードまでの距離」を一度に計算したい場合、 BFS は非常に便利です。

BFSは「階層ごとに探索する」アルゴリズムなので、 階層番号そのものが「距離」として使えます。

例えば、次のようなコードで「根から各ノードまでの距離」を計算できます。

import java.util.LinkedList;
import java.util.Queue;
import java.util.HashMap;
import java.util.Map;

public static Map<Node, Integer> distancesFromRoot(Node root) {
    Map<Node, Integer> dist = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();

    dist.put(root, 0);
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        int d = dist.get(node);

        for (Node child : node.children) {
            dist.put(child, d + 1);
            queue.add(child);
        }
    }

    return dist;
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.HashMap;
import java.util.Map;

public static Map<Node, Integer> distancesFromRoot(Node root) {
    Map<Node, Integer> dist = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();

    dist.put(root, 0);
    queue.add(root);

    while (!queue.isEmpty()) {
        Node node = queue.poll();
        int d = dist.get(node);

        for (Node child : node.children) {
            dist.put(child, d + 1);
            queue.add(child);
        }
    }

    return dist;
}

このメソッドは、「根から各ノードまでの距離」を Map<Node, Integer> に保存して返します。 後半では、このような距離情報を使って、 任意の二ノード間の距離を効率的に計算する方法を扱います。

セキュリティ・パフォーマンスの観点から見た距離計算（前半の触り）

距離計算は一見すると「数学的な話」に見えますが、 セキュリティやパフォーマンスとも密接に関係しています。

例えば、ユーザー入力から生成された木構造に対して距離計算を行う場合、 攻撃者が「極端に深い木」や「極端にノード数の多い木」を送り込む可能性があります。

そのような場合、再帰DFSで距離計算をすると StackOverflowError や極端な処理時間の増加につながることがあります。

そのため、実務では

深さに上限を設ける BFSで距離を計算して、深さを監視する ノード数や深さに応じて処理を制限する

といった工夫が必要になります。 このあたりは後半で具体的に掘り下げます。

前半のまとめと後半への橋渡し

前半では、木構造における「距離」と「最短経路」の基本的な考え方を整理しました。

木構造では距離は「辺の本数」で定義されること 根から特定ノードまでの距離は、DFSで深さを持ち歩くことで計算できること 任意の二ノード間の距離は、共通祖先（LCA）と深さを使って考えられること BFSを使うと、根からすべてのノードまでの距離を一度に計算できること

後半では、これらの考え方をさらに発展させて

LCA（最小共通祖先）の具体的な計算方法 任意の二ノード間の距離計算アルゴリズム 木の「直径」（最も遠い二点間の距離）の求め方 セキュリティ・パフォーマンスを意識した距離計算の設計

などを、Javaコードとともに詳しく解説していきます。