木構造の最短経路・距離計算（後半）
前半では、木構造における「距離」の基本概念、 根から特定ノードまでの距離、そして BFS を使った距離計算の基礎を整理しました。 後半では、より実務的で応用的なテーマとして 任意の二ノード間の距離、 その中心となる LCA（最小共通祖先）、さらに 木の直径（最も遠い二点間の距離）、 そして セキュリティ・パフォーマンスの観点からの距離計算の注意点 を深掘りします。
木構造の距離計算は、アルゴリズムの中でも「仕組みが分かると一気に楽しくなる」分野です。 読者が実務でも使えるレベルまで理解できるよう、丁寧に進めていきます。
任意の二ノード間の距離を求めるための鍵：LCA（最小共通祖先）
木構造で「ノード u とノード v の距離」を求めたいとき、 最も重要になるのが LCA（Lowest Common Ancestor：最小共通祖先） です。
LCAとは何か
二つのノード u と v に対して、 「u と v の両方の祖先であり、最も深い位置にあるノード」が LCA です。
例えば次のような木を考えます。
- root
- A
- C
- B
- A
A と C の LCA は A B と C の LCA は root A と B の LCA は root
LCA が分かると、距離は次の式で求められます。
距離(u, v) = depth(u) + depth(v) − 2 × depth(LCA(u, v))
この式は木構造の距離計算の中心となる考え方です。
Javaで書く「LCAの基本実装」（親参照を使う方法）
最もシンプルな LCA の実装は、「各ノードが親を持っている」場合です。 まず、Node クラスに親参照を追加します。
class Node {
String name;
Node parent;
List<Node> children = new ArrayList<>();
Node(String name) {
this.name = name;
}
void addChild(Node child) {
child.parent = this;
children.add(child);
}
}
LCAを求める基本アルゴリズム
- u と v の深さを求める
- 深い方を浅い方まで引き上げる
- 二つのノードが一致するまで親をたどる
Javaコードは次のようになります。
public static Node lca(Node u, Node v) {
int du = depth(u);
int dv = depth(v);
while (du > dv) {
u = u.parent;
du--;
}
while (dv > du) {
v = v.parent;
dv--;
}
while (u != v) {
u = u.parent;
v = v.parent;
}
return u;
}
private static int depth(Node node) {
int d = 0;
while (node.parent != null) {
node = node.parent;
d++;
}
return d;
}
この方法はシンプルで理解しやすく、 木構造の距離計算の基礎として非常に優れています。
任意の二ノード間の距離を求める（LCAを使う）
LCA が求まれば、距離は簡単に計算できます。
public static int distance(Node u, Node v) {
Node ancestor = lca(u, v);
return depth(u) + depth(v) - 2 * depth(ancestor);
}
深掘り：なぜこの式で距離が求まるのか
u から LCA までの距離は depth(u) − depth(LCA) v から LCA までの距離は depth(v) − depth(LCA)
これを足すと、
(depth(u) − depth(LCA)) + (depth(v) − depth(LCA)) = depth(u) + depth(v) − 2 × depth(LCA)
となります。
木構造ではループがないため、 「LCA を経由する経路が最短である」ことが保証されます。
木の「直径」を求める（最も遠い二点間の距離）
木構造の距離計算でよく登場する応用が「木の直径」です。 直径とは、「木の中で最も距離が長い二ノード間の距離」のことです。
直径を求めるアルゴリズム
- 任意のノード x を選ぶ
- x から最も遠いノード u を BFS で見つける
- u から最も遠いノード v を BFS で見つける
- u と v の距離が直径になる
Javaコードは次のようになります。
public static Node farthest(Node start) {
Queue<Node> queue = new LinkedList<>();
Map<Node, Integer> dist = new HashMap<>();
queue.add(start);
dist.put(start, 0);
Node far = start;
while (!queue.isEmpty()) {
Node node = queue.poll();
far = node;
for (Node child : node.children) {
if (!dist.containsKey(child)) {
dist.put(child, dist.get(node) + 1);
queue.add(child);
}
}
if (node.parent != null && !dist.containsKey(node.parent)) {
dist.put(node.parent, dist.get(node) + 1);
queue.add(node.parent);
}
}
return far;
}
直径は次のように求まります。
Node u = farthest(root);
Node v = farthest(u);
int diameter = distance(u, v);
深掘り：なぜこの方法で直径が求まるのか
木構造では、最も遠いノードを起点にすると、 そのノードから最も遠いノードが「直径の端点」になることが数学的に証明されています。
この性質を利用することで、 直径を効率的に求めることができます。
セキュリティの観点から見た距離計算の注意点
木構造の距離計算は便利ですが、 セキュリティスペシャリストの視点では次の点に注意が必要です。
深さが極端に深い木は危険
攻撃者が「100万階層の JSON」などを送り込むと、 再帰 DFS が StackOverflowError を起こします。
ノード数が極端に多い木も危険
距離計算は BFS を使うことが多いため、 ノード数が多いとメモリ消費が急増します。
安全にするための対策
深さの上限を設ける ノード数の上限を設ける 再帰ではなく BFS を使う 処理時間のタイムアウトを設ける
距離計算は「入力の構造に依存する」ため、 セキュリティの観点では常に深さとノード数を監視する必要があります。
パフォーマンスの観点から見た距離計算
距離計算は DFS と BFS のどちらでも可能ですが、 目的によって使い分けが必要です。
DFS 深さを持ち歩く処理に向いている 再帰で書くとシンプル 深い木では危険（スタックオーバーフロー）
BFS 階層ごとの距離計算に向いている 根から全ノードの距離を一度に求められる 幅が広い木ではメモリ消費が増える
実務では、次のように使い分けます。
距離を一度だけ求めたい → DFS 距離を全ノード分求めたい → BFS 任意の二ノード間の距離 → LCA + 深さ 木の直径 → BFS × 2
後半のまとめ
後半では、木構造の距離計算を実務レベルで使いこなすための内容を扱いました。
LCA（最小共通祖先） 任意の二ノード間の距離計算 木の直径（最も遠い二点間の距離） セキュリティとパフォーマンスの観点 DFS・BFS の使い分け
木構造の距離計算は、 「深さ」「共通祖先」「探索アルゴリズム」の三つを理解すると一気に楽になります。