Java | 「木構造の距離計算」をもっと深く理解する

Javaで考える「木構造の距離計算」をもっと深く理解する（前半）

木構造の距離をきちんと理解できると、ツリー探索・木DP・グラフアルゴリズムが一気につながって見えるようになります。 距離は「ノード同士がどれくらい離れているか」を数値で表す指標であり、 階層構造を定量的に理解するための重要な概念です。

前半では、まず 木構造における距離の定義 距離を直感的にイメージする方法 Javaで距離計算の土台になる「深さ」と「親」の情報を求める基本パターン を、初心者向けにかみ砕いて整理していきます。 後半では、最小共通祖先（LCA）や距離の公式、より高度な距離計算へと踏み込んでいきます。

木構造における「距離」の定義をはっきりさせる

木構造における距離は、基本的に「二つのノードを結ぶパス上の辺の本数」として定義します。 ここでいうパスとは、「あるノードから別のノードへ行くときに通るノードの列」のことです。

例えば、次のような木を考えます。

根が 1 その子が 2 と 3 2 の子が 4 と 5

このとき、ノード 4 からノード 5 への距離を考えてみます。 4 から 5 へ行くには、4 → 2 → 5 と辿る必要があります。 通る辺は 4–2 と 2–5 の 2 本なので、距離は 2 です。

同様に、4 から 3 への距離は、4 → 2 → 1 → 3 と辿ることになり、 通る辺は 4–2、2–1、1–3 の 3 本なので、距離は 3 です。

ここで重要なのは、「木では二つのノードを結ぶパスが必ず一本だけに決まる」という性質です。 一般的なグラフでは複数の経路があり得ますが、木はサイクルを持たないため、 どの二点を取ってもパスは一意です。 このおかげで、距離の定義と計算が非常に扱いやすくなります。

Javaで木構造を表現する基本形を確認する

距離計算に入る前に、Javaで木構造をどう表現するかを整理しておきます。 最も素朴な方法は、「ノードクラスが自分の子ノードの一覧を持つ」形です。

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

class Node {
    int id;
    List<Node> children = new ArrayList<>();

    Node(int id) {
        this.id = id;
    }

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

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

class Node {
    int id;
    List<Node> children = new ArrayList<>();

    Node(int id) {
        this.id = id;
    }

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

先ほどの木をこのクラスで表現すると、次のようになります。

Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);

n1.addChild(n2);
n1.addChild(n3);
n2.addChild(n4);
n2.addChild(n5);

Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);

n1.addChild(n2);
n1.addChild(n3);
n2.addChild(n4);
n2.addChild(n5);

この形は「親から子へ」の一方向のつながりです。 しかし、距離計算では「親に戻る」動きも必要になるため、 実際には「無向グラフとしての木」を隣接リストで表現することが多くなります。

隣接リストを使うと、次のような形になります。

import java.util.*;

public class TreeExample {
    static List<Integer>[] tree;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        int n = 5; // ノード数（1〜5）
        tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }

        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
    }

    static void addEdge(int a, int b) {
        tree[a].add(b);
        tree[b].add(a); // 無向木として扱う
    }
}

import java.util.*;

public class TreeExample {
    static List<Integer>[] tree;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        int n = 5; // ノード数（1〜5）
        tree = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }

        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);
    }

    static void addEdge(int a, int b) {
        tree[a].add(b);
        tree[b].add(a); // 無向木として扱う
    }
}

ここでは、tree[i] が「ノード i とつながっているノードの一覧」を表します。 距離計算では、このような「隣接リスト＋DFS／BFS」という形が定番になります。

距離計算の土台になる「深さ」と「親」という考え方

木構造の距離を考えるとき、重要なキーワードが二つあります。 一つ目は「深さ（depth）」、二つ目は「親（parent）」です。

深さとは、「根からそのノードまでの距離」です。 根の深さを 0 とすると、その子の深さは 1、孫の深さは 2、というように定義できます。 深さは「上から下へ」の距離を表す指標です。

親とは、「そのノードを一つ上に辿ったときのノード」です。 親情報があると、ノードから上に向かって辿ることが簡単になります。

距離計算では、 二つのノードの距離を「それぞれが共通の祖先まで上がる距離」に分解して考えることができます。 このとき、深さと親の情報が非常に役立ちます。

Javaで「深さ」と「親」をDFSで求める基本パターン

隣接リストで表現した木に対して、DFS（深さ優先探索）を使って 各ノードの深さと親を求めるコードを見てみます。

import java.util.*;

public class TreeDepthParent {

    static List<Integer>[] tree;
    static int[] depth;
    static int[] parent;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        int n = 5;
        tree = new ArrayList[n + 1];
        depth = new int[n + 1];
        parent = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }

        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);

        dfs(1, -1, 0); // 根を1とし、親なしを-1、深さ0でスタート

        System.out.println("depth[1] = " + depth[1]); // 0
        System.out.println("depth[2] = " + depth[2]); // 1
        System.out.println("depth[4] = " + depth[4]); // 2

        System.out.println("parent[1] = " + parent[1]); // -1
        System.out.println("parent[2] = " + parent[2]); // 1
        System.out.println("parent[4] = " + parent[4]); // 2
    }

    static void addEdge(int a, int b) {
        tree[a].add(b);
        tree[b].add(a);
    }

    static void dfs(int node, int p, int d) {
        parent[node] = p;
        depth[node] = d;

        for (int next : tree[node]) {
            if (next == p) continue; // 親方向には戻らない
            dfs(next, node, d + 1);
        }
    }
}

import java.util.*;

public class TreeDepthParent {

    static List<Integer>[] tree;
    static int[] depth;
    static int[] parent;

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        int n = 5;
        tree = new ArrayList[n + 1];
        depth = new int[n + 1];
        parent = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }

        addEdge(1, 2);
        addEdge(1, 3);
        addEdge(2, 4);
        addEdge(2, 5);

        dfs(1, -1, 0); // 根を1とし、親なしを-1、深さ0でスタート

        System.out.println("depth[1] = " + depth[1]); // 0
        System.out.println("depth[2] = " + depth[2]); // 1
        System.out.println("depth[4] = " + depth[4]); // 2

        System.out.println("parent[1] = " + parent[1]); // -1
        System.out.println("parent[2] = " + parent[2]); // 1
        System.out.println("parent[4] = " + parent[4]); // 2
    }

    static void addEdge(int a, int b) {
        tree[a].add(b);
        tree[b].add(a);
    }

    static void dfs(int node, int p, int d) {
        parent[node] = p;
        depth[node] = d;

        for (int next : tree[node]) {
            if (next == p) continue; // 親方向には戻らない
            dfs(next, node, d + 1);
        }
    }
}

このコードの重要なポイントを深掘りします。

まず、dfs の引数 node が「今いるノード」、p が「その親」、d が「その深さ」です。 parent[node] = p; によって、各ノードの親が記録されます。 depth[node] = d; によって、各ノードの深さが記録されます。

次に、for (int next : tree[node]) で隣接ノードをたどり、 if (next == p) continue; で「親方向への戻り」を避けています。 これにより、木を一方向にたどることができ、 すべてのノードに対して深さと親が正しく計算されます。

この「深さ」と「親」の情報が、距離計算の基礎になります。 後半で扱う距離の公式や LCA アルゴリズムは、 この情報を前提として動きます。

距離を「深さ」と「共通祖先」でイメージする

深さと親が分かっていると、二つのノードの距離を次のようにイメージできます。

まず、二つのノードの深さが違う場合、 深い方のノードを親に上げていくことで、深さを揃えます。 例えば、深さ 2 のノードと深さ 1 のノードがあるなら、 深さ 2 のノードを一つ親に上げて深さ 1 にします。

次に、深さが揃った状態で、 両方のノードを同時に親に上げていきます。 同じノードになったところが「共通祖先」です。

このとき、 上に上がった回数の合計が、二つのノードの距離になります。

この直感は、後半で扱う 距離の公式 $\text{dist}(u,v)=\text{depth}[u]+\text{depth}[v]-2\times \text{depth}[\text{LCA}(u,v)]$ の理解にもつながります。

前半では、 「距離は、深さと親を使って分解して考えられる」 という感覚を持ってもらうことが大事です。

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

前半では、木構造の距離計算を深く理解するための土台として

木構造における距離は「パス上の辺の本数」であること 木は「二点間のパスが一意に決まる」ため距離が扱いやすいこと Javaで木をノードクラスや隣接リストで表現する基本形 DFSで「深さ（根からの距離）」と「親」を計算する方法 距離を「深さを揃えてから、親に上がる回数」でイメージできること

を整理しました。

後半では、ここから一歩進んで

最小共通祖先（LCA）を使った距離計算の一般式 距離の公式の意味と具体的な計算例 LCAを素朴に求める方法と高速化のアイデア 距離計算と木DP・グラフ探索とのつながり セキュリティ・パフォーマンスの観点から見た距離計算の注意点

を、具体的な Java コードとともに深掘りしていきます。