克鲁斯卡尔重构树（Kruskal Reconstruction Tree）详解

1. 引言

在算法竞赛和数据结构学习中，克鲁斯卡尔重构树（Kruskal Reconstruction Tree，简称 KRT）是一种基于最小生成树（MST）构建的、功能强大的数据结构。它最初由 Kruskal 算法衍生而来，能够将无向连通图的边权信息转化为树形结构，从而高效地解决一类与“瓶颈路”相关的查询问题。

本文将系统性地介绍克鲁斯卡尔重构树的构建原理、核心性质、典型应用以及代码实现，帮助读者深入理解并掌握这一重要工具。

2. 前置知识

为了更好地理解克鲁斯卡尔重构树，建议读者具备以下基础知识：

  • 并查集（Union-Find/Disjoint Set Union）：用于高效合并集合与查询连通性。
  • 最小生成树（MST）与 Kruskal 算法：理解按边权排序、贪心加边的过程。
  • 树的基本概念：如节点、边、深度、最近公共祖先（LCA）等。
  • 倍增法：用于快速查询树上节点的祖先。

3. 构建原理

克鲁斯卡尔重构树的构建过程与 Kruskal 算法求最小生成树的过程同步进行，但会额外创建新的“虚点”来代表边的加入。

3.1 构建步骤

  1. 初始化：将原图的n个顶点视为n棵独立的树（即并查集中的n个集合），每个顶点也是重构树中的一个叶子节点。同时，准备一个空的节点列表用于构建重构树。
  2. 边排序：将所有边按照边权从小到大排序（对于最大生成树问题则从大到小排序）。
  3. 合并与创建虚点：按顺序遍历每条边(u, v, w)：
    • 如果u和v当前不属于同一个连通分量（即并查集中 find(u) != find(v)），则进行合并操作。
    • 创建一个新的虚点p，其点权设为当前边的边权w。
    • 在重构树中，让p成为u所在集合的根节点 和v所在集合的根节点 的父亲。即p的左孩子是find(u)的根，右孩子是find(v)的根。
    • 在并查集中，将u和v所在的集合合并，并将新集合的根设为新创建的虚点p。
  4. 结束：当所有边处理完毕，或原图已连通（合并了n-1条边）后，最终会得到一棵有2n-1个节点的二叉树，其根节点是最后一个创建的虚点。

3.2 构建示例

考虑一个简单的 4 个顶点的图，边权如下：

边1: (1, 2, 2) 边2: (2, 3, 3) 边3: (3, 4, 5) 边4: (1, 4, 6) 边5: (1, 3, 4)

按边权排序后，构建过程如下：

  1. 初始：节点 1, 2, 3, 4 各自为根。
  2. 处理边(1,2,2)：创建虚点5(权2)，作为1和2的父亲。合并集合，根为5。
  3. 处理边(2,3,3)：find(2)的根是5，find(3)的根是3。创建虚点6(权3)，作为5和3的父亲。合并集合，根为6。
  4. 处理边(1,3,4)：此时1和3已在同一集合（根为6），跳过。
  5. 处理边(3,4,5)：find(3)的根是6，find(4)的根是4。创建虚点7(权5)，作为6和4的父亲。合并集合，根为7。
  6. 最终，节点7是重构树的根。树的结构为：7(5)的左孩子是6(3)，右孩子是4；6(3)的左孩子是5(2)，右孩子是3；5(2)的左孩子是1，右孩子是2。

4. 核心性质

克鲁斯卡尔重构树具有以下关键性质，这些性质是其能够高效解决问题的基石：

  1. 二叉树结构：重构树是一棵有2n-1个节点的二叉树。原图的n个顶点是叶子节点，其余n-1个虚点是内部节点。
  2. 点权单调性：由于边是按权值从小到大加入的，因此从叶子节点到根节点的路径上，虚点的点权是单调不递减的（对于最小生成树构建）。根节点的点权最大。
  3. 瓶颈路查询：对于原图中任意两点u和v，它们在重构树上的最近公共祖先（LCA）的点权，就等于在原图中所有从u到v的路径中，最大边权的最小值（即最小瓶颈路）。这是重构树最核心的性质。
  4. 连通性映射：对于某个权值阈值x，考虑所有点权≤ x的节点及其子树，这些子树中的叶子节点就对应了原图中仅通过边权≤ x的边所能连通的顶点集合。

5. 典型应用场景

利用上述性质，克鲁斯卡尔重构树可以高效解决以下问题：

  • 最小瓶颈路查询：多次查询两点间路径的最大边权的最小值。预处理 O(m log m + n log n)，每次查询 O(log n)（需结合 LCA 算法）。
  • 连通性阈值查询：给定权值阈值x，查询两点在仅使用边权 ≤ x 的边时是否连通。这等价于判断两点在重构树中权值 ≤ x 的祖先是否相同。
  • 点权转化：将图上基于边权的问题（如最小瓶颈）转化为树上基于点权的问题（如 LCA 点权），从而可以利用更丰富的树算法（如树上倍增、树剖、主席树等）。
  • 结合其他数据结构：例如，在重构树的 DFS 序上建立线段树或主席树，可以处理“子树内叶子节点信息查询”等问题。

6. 代码实现（C++）

以下是一个完整的克鲁斯卡尔重构树构建代码示例，包含并查集、边排序、建树以及 LCA 预处理。

#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Edge { int u, v, w; bool operator<(const Edge& other) const { return w < other.w; // 按边权从小到大排序 } }; class KruskalReconstructionTree { private: int n; // 原图顶点数 vector<Edge> edges; vector<int> parent; // 并查集 vector<int> val; // 节点权值（叶子节点权可设为0或-INF） vector<vector<int>> g; // 重构树的邻接表 int nodeCnt; // 当前重构树节点数量 vector<vector<int>> fa; // 倍增祖先 vector<int> depth; int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void dfs(int u, int p) { fa[u][0] = p; depth[u] = p == -1 ? 0 : depth[p] + 1; for (int i = 1; i < 20; ++i) { if (fa[u][i-1] != -1) fa[u][i] = fa[fa[u][i-1]][i-1]; else fa[u][i] = -1; } for (int v : g[u]) { if (v == p) continue; dfs(v, u); } } int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); for (int i = 19; i >= 0; --i) { if (fa[u][i] != -1 && depth[fa[u][i]] >= depth[v]) { u = fa[u][i]; } } if (u == v) return u; for (int i = 19; i >= 0; --i) { if (fa[u][i] != fa[v][i]) { u = fa[u][i]; v = fa[v][i]; } } return fa[u][0]; } public: KruskalReconstructionTree(int _n, vector<Edge>& _edges) : n(_n), edges(_edges) { // 初始化 nodeCnt = n; parent.resize(2 * n); // 最多2n-1个节点 val.resize(2 * n, 0); g.resize(2 * n); for (int i = 0; i < 2 * n; ++i) parent[i] = i; // 按边权排序 sort(edges.begin(), edges.end()); // 克鲁斯卡尔重构 for (const auto& e : edges) { int fu = find(e.u); int fv = find(e.v); if (fu != fv) { // 创建新虚点 int newRoot = nodeCnt++; val[newRoot] = e.w; // 在重构树中加边 g[newRoot].push_back(fu); g[newRoot].push_back(fv); // 并查集合并，新根为 newRoot parent[fu] = newRoot; parent[fv] = newRoot; parent[newRoot] = newRoot; // 自环，方便后续find } } // 预处理LCA int root = nodeCnt - 1; // 最后一个创建的节点是根 fa.assign(nodeCnt, vector<int>(20, -1)); depth.resize(nodeCnt); dfs(root, -1); } // 查询u和v的最小瓶颈路权值（即LCA的点权） int queryMinMax(int u, int v) { int anc = lca(u, v); return val[anc]; } // 获取重构树邻接表（用于其他树上操作） const vector<vector<int>>& getTree() const { return g; } // 获取节点权值 const vector<int>& getVal() const { return val; } int getNodeCount() const { return nodeCnt; } }; int main() { int n = 4, m = 5; vector<Edge> edges = {{1, 2, 2}, {2, 3, 3}, {3, 4, 5}, {1, 4, 6}, {1, 3, 4}}; // 注意：示例中顶点编号从1开始，代码中需调整或保证输入一致 KruskalReconstructionTree krt(n, edges); cout << "最小瓶颈路权值 between 1 and 4: " << krt.queryMinMax(1, 4) << endl; // 应输出5 return 0; }

7. 总结与扩展

克鲁斯卡尔重构树巧妙地将图上的瓶颈路问题转化为了树上的 LCA 问题，极大地降低了查询复杂度。其核心思想在于利用 Kruskal 算法的贪心过程，将边权信息“提升”为树节点的点权，并保持了关键的单调性质。

扩展方向：

  • 最大生成树重构：按边权从大到小排序构建，此时 LCA 点权代表“最小边权的最大值”。
  • 带权图：原图顶点带权时，可以在叶子节点上赋予原顶点权值，并结合线段树维护子树信息。
  • 动态问题：结合 LCT（Link-Cut Tree）或可持久化数据结构处理边权增加/删除的动态瓶颈路查询。

掌握克鲁斯卡尔重构树，能为解决复杂的图论问题提供一种清晰而高效的范式。