最小生成树的唯一性判定
我们来探讨一个经典问题：给定一个带权无向连通图，如何判断其最小生成树（Minimum Spanning Tree, MST）是否唯一。换句话说，是否存在另一棵生成树，其总权值与最小生成树相等，但边集不完全相同？
问题描述
输入：
- 一个连通的无向图 \(G = (V, E)\)，其中每条边 \(e \in E\) 有一个权值 \(w(e)\)（通常为整数）。
输出：
- 判断图 \(G\) 的最小生成树是否唯一。
- 如果是唯一的，输出“是”；否则，输出“否”。
背景与关键概念
在深入算法之前，我们需要理解为什么一个图会有多棵最小生成树。
核心原因：权值相等的边。
考虑一个简单情况：假设图中有两条（或多条）权值相同的边，它们连接了相同的连通分量（在构建 MST 的过程中），那么在 Kruskal 或 Prim 算法做选择时，任意选择其中一条都可以。如果后续选择不同的边会导致生成不同的生成树，且总权值相同，那么最小生成树就不唯一。
但仅仅有权值相等的边还不够，它们的“结构位置”必须提供可替换性。更精确地说：
对于一棵最小生成树 \(T\)，如果存在一条不在 \(T\) 中的边 \(e\)，其权值等于 \(T\) 中某条边 \(f\) 的权值，且将 \(e\) 加入 \(T\) 会形成一个环，而 \(f\) 是这个环上权值最大的边（之一），那么用 \(e\) 替换 \(f\) 会得到另一棵权值和相等的生成树。
因此，判定的核心思路是：检查对于每一棵最小生成树，是否所有边都是“唯一确定”的。
基本思想
一个最直观的判定方法是：
- 先计算一棵最小生成树 \(T\)，并记录其总权值 \(W\)。
- 然后，对于图中的每条边 \(e\)（特别是那些未在 \(T\) 中的边），尝试“挑战” \(T\) 的唯一性：
- 假设我们强制不使用某条边 \(e'\)（该边在 \(T\) 中）。
- 在这种情况下，重新计算最小生成树（即求图 \(G\) 去掉 \(e'\) 后的 MST，或者更高效地，求“必须包含某条边”的 MST）。
- 如果新得到的 MST 权值仍然等于 \(W\)，说明存在另一棵 MST 不包含 \(e'\)，因此 MST 不唯一。
但这个直接方法的时间复杂度较高（需要对每一条 MST 中的边都重新算 MST）。我们需要更高效的算法。
高效算法：次优最小生成树（Second-best MST）思路的变种
一个经典的高效算法基于以下定理：
定理：设 \(T\) 是图 \(G\) 的一棵最小生成树。则 \(G\) 的最小生成树唯一，当且仅当对于每一条不在 \(T\) 中的边 \(e = (u, v)\)，满足：
- \(e\) 的权值严格大于 \(T\) 中从 \(u\) 到 \(v\) 的路径上每条边的权值。
- 更严格地说：\(e\) 的权值严格大于 \(T\) 中从 \(u\) 到 \(v\) 的路径上最大边权。
解释：
- 当我们把 \(e\) 加入 \(T\) 时，会形成一个环（该环由 \(e\) 加上 \(T\) 中从 \(u\) 到 \(v\) 的路径构成）。
- 如果 \(w(e)\) 等于该路径上某条边的权值，那么我们可以用 \(e\) 替换那条边，得到另一棵权值和相等的生成树。
- 如果 \(w(e)\) 大于路径上所有边的权值，那么任何替换都会使总权值增加，因此 \(T\) 是唯一的最小生成树（对于该特定环而言）。
- 我们需要对每一条不在 \(T\) 中的边 \(e\) 都检查这个条件。
算法步骤
步骤 1：计算任意一棵最小生成树 \(T\)
- 使用 Kruskal 或 Prim 算法。
- 时间复杂度：\(O(E \log V)\) 或 \(O(E + V \log V)\)。
步骤 2：预处理树 \(T\) 上任意两点间的最大边权
- 我们需要高效地回答查询：给定树上两点 \(u\) 和 \(v\)，\(T\) 中 \(u\) 到 \(v\) 的路径上，权值最大的边权是多少？
- 这可以通过 树上倍增（Binary Lifting） 来高效解决。
- 令 \(up[u][k]\) 表示从节点 \(u\) 向上跳 \(2^k\) 步到达的祖先节点。
- 令 \(maxEdge[u][k]\) 表示从 \(u\) 到 \(up[u][k]\) 的路径上的最大边权。
- 预处理时间：\(O(V \log V)\)。
- 查询时间：\(O(\log V)\)（用于求 \(\text{LCA}(u,v)\) 及路径上的最大边权）。
步骤 3：检查每一条非树边
- 对于每条不在 \(T\) 中的边 \(e = (u, v, w)\)：
- 查询 \(T\) 中 \(u\) 到 \(v\) 路径上的最大边权 \(maxW\)。
- 如果 \(w == maxW\)，则不唯一（因为可以用 \(e\) 替换那条权值为 \(maxW\) 的树边）。
- 如果所有非树边都满足 \(w > maxW\)，则 MST 唯一。
步骤 4：处理权值相等边的特殊情况
- 注意：如果路径上有多条边的权值都等于 \(maxW\)，且 \(w(e) == maxW\)，那么替换其中任何一条都会得到另一棵 MST。
- 因此，只要相等，就不唯一。
例子
考虑一个简单图：
顶点：A, B, C
边：
(A, B) 权值 1
(B, C) 权值 1
(A, C) 权值 2
- 使用 Kruskal：先选 (A,B) 权值1，再选 (B,C) 权值1，MST 总权值 = 2。
- 检查非树边 (A,C) 权值2：在 MST 中，A 到 C 的路径是 A-B-C，最大边权 = 1。
- 因为 2 > 1，所以无法用 (A,C) 替换得到相同权值的另一棵 MST。因此唯一。
另一个例子：
顶点：A, B, C
边：
(A, B) 权值 1
(B, C) 权值 2
(A, C) 权值 2
- MST：选 (A,B) 权值1 和 (B,C) 权值2，总权值=3。
- 非树边 (A,C) 权值2：在 MST 中 A 到 C 的路径是 A-B-C，最大边权 = max(1,2) = 2。
- 因为 2 == 2，所以可以用 (A,C) 替换 (B,C)，得到另一棵 MST {(A,B), (A,C)}，总权值也是 3。因此不唯一。
复杂度分析
- 步骤 1：计算 MST：\(O(E \log V)\)。
- 步骤 2：预处理树上路径最大边权：\(O(V \log V)\)。
- 步骤 3：检查每条非树边：\(O(E \log V)\)（因为每次查询 \(O(\log V)\)）。
总复杂度：\(O(E \log V)\)，与计算 MST 的复杂度相当，非常高效。
算法实现要点
- 在实现 Kruskal 时，记录哪些边在 MST 中。
- 构建 MST 的邻接表表示（用于树上倍增）。
- 实现倍增的预处理和查询函数。
- 遍历所有非树边进行判断。
总结
判定最小生成树唯一性的高效算法核心是：
- 先求一棵 MST \(T\)。
- 预处理 \(T\) 上任意两点路径的最大边权。
- 对每条非树边，检查其权值是否等于 \(T\) 中对应路径的最大边权；若是，则不唯一。
这个算法清晰且高效，结合了 MST 算法与树上路径查询技术，是图论中一个很好的综合应用题。