问题背景
次小生成树（Second Minimum Spanning Tree, SMST）是图论中一个重要的变种问题。给定一个带权无向连通图，要求找出权值仅次于最小生成树（MST）的生成树。该问题在网络冗余设计、备用路由规划、电力系统备份等场景中具有实际意义。
与MST的唯一性判定直接相关：若图存在多棵MST，则次小生成树的权值等于MST的权值。若MST唯一，则需要通过”替换边”策略寻找略大于MST的最优解。
核心算法思想
替换边策略
假设已求得一棵MST T。对于每条非树边 (u, v, w)，将其加入 T 会形成一个环。从该环中去掉一条权值最大的树边（不能是刚加入的边），即可得到一棵新的生成树。次小生成树必然存在于这些新生成树之中。
关键问题转化为：对于每条非树边 (u, v)，找到MST中 u 到 v 路径上的最大边权。
LCA预处理路径最大值
利用LCA（最近公共祖先）预处理方法，可以在 O(1) 或 O(log n) 时间内回答路径最大值查询。具体做法：
– 从MST的根节点出发进行DFS，记录每个节点的深度
– 使用倍增法预处理 up[k][v]（v的2^k级祖先）和 maxEdge[k][v]（v到该祖先路径上的最大边权）
严格次小与非严格次小
- 非严格次小：允许权值等于MST（存在多棵MST时）
- 严格次小：要求权值严格大于MST
本文实现严格次小生成树，需在路径最大值等于非树边权时，寻找次大值进行替换。
Java完整实现
import java.util.*;
/**
* 次小生成树求解器
* 基于Kruskal求MST，再用LCA预处理路径最大边权
*/
public class SecondMST {
static class Edge implements Comparable<Edge> {
int u, v, w;
boolean inMST; // 是否在MST中
Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(this.w, o.w);
}
}
private int n, m;
private List<Edge> edges;
private List<int[]>[] tree; // MST的邻接表 (to, weight)
private int[] parent; // 并查集
private int LOG; // 倍增层数
private int[][] up; // up[k][v]: v的2^k祖先
private int[][] maxEdge; // maxEdge[k][v]: v到2^k祖先路径上的最大边权
private int[][] secondMaxEdge; // 严格次大边权
private int[] depth;
public SecondMST(int n) {
this.n = n;
this.edges = new ArrayList<>();
this.parent = new int[n + 1];
this.LOG = 32 - Integer.numberOfLeadingZeros(n);
}
public void addEdge(int u, int v, int w) {
edges.add(new Edge(u, v, w));
}
private int find(int x) {
return parent[x] == x ? x : (parent[x] = find(parent[x]));
}
private boolean union(int x, int y) {
int fx = find(x), fy = find(y);
if (fx == fy) return false;
parent[fx] = fy;
return true;
}
/**
* Kruskal算法求MST
* @return MST的总权值
*/
public long kruskal() {
for (int i = 1; i <= n; i++) parent[i] = i;
Collections.sort(edges);
tree = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) tree[i] = new ArrayList<>();
long mstWeight = 0;
int count = 0;
for (Edge e : edges) {
if (union(e.u, e.v)) {
e.inMST = true;
mstWeight += e.w;
tree[e.u].add(new int[]{e.v, e.w});
tree[e.v].add(new int[]{e.u, e.w});
count++;
if (count == n - 1) break;
}
}
return mstWeight;
}
/**
* DFS预处理深度和倍增表
*/
private void dfs(int u, int fa, int w) {
up[0][u] = fa;
maxEdge[0][u] = w;
secondMaxEdge[0][u] = -1; // 到父节点只有一条边，无次大值
for (int[] next : tree[u]) {
int v = next[0], weight = next[1];
if (v == fa) continue;
depth[v] = depth[u] + 1;
dfs(v, u, weight);
}
}
/**
* 构建LCA倍增表
*/
public void buildLCA() {
up = new int[LOG][n + 1];
maxEdge = new int[LOG][n + 1];
secondMaxEdge = new int[LOG][n + 1];
depth = new int[n + 1];
depth[1] = 0;
dfs(1, 0, 0);
for (int k = 1; k < LOG; k++) {
for (int v = 1; v <= n; v++) {
int mid = up[k - 1][v];
up[k][v] = up[k - 1][mid];
// 合并两段路径的最大和次大值
int[] candidates = {maxEdge[k-1][v], secondMaxEdge[k-1][v],
maxEdge[k-1][mid], secondMaxEdge[k-1][mid]};
maxEdge[k][v] = -1;
secondMaxEdge[k][v] = -1;
for (int val : candidates) {
if (val > maxEdge[k][v]) {
secondMaxEdge[k][v] = maxEdge[k][v];
maxEdge[k][v] = val;
} else if (val != maxEdge[k][v] && val > secondMaxEdge[k][v]) {
secondMaxEdge[k][v] = val;
}
}
}
}
}
/**
* 查询u到v路径上的最大边权和严格次大边权
*/
private int[] queryMax(int u, int v) {
int max1 = -1, max2 = -1; // max1为最大，max2为严格次大
if (depth[u] < depth[v]) {
int tmp = u; u = v; v = tmp;
}
// 将u提升到与v同一深度
int diff = depth[u] - depth[v];
for (int k = LOG - 1; k >= 0; k--) {
if ((diff >> k & 1) == 1) {
int[] candidates = {max1, max2, maxEdge[k][u], secondMaxEdge[k][u]};
max1 = -1; max2 = -1;
for (int val : candidates) {
if (val > max1) { max2 = max1; max1 = val; }
else if (val != max1 && val > max2) { max2 = val; }
}
u = up[k][u];
}
}
if (u == v) return new int[]{max1, max2};
for (int k = LOG - 1; k >= 0; k--) {
if (up[k][u] != up[k][v]) {
int[] candidates = {max1, max2, maxEdge[k][u], secondMaxEdge[k][u],
maxEdge[k][v], secondMaxEdge[k][v]};
max1 = -1; max2 = -1;
for (int val : candidates) {
if (val > max1) { max2 = max1; max1 = val; }
else if (val != max1 && val > max2) { max2 = val; }
}
u = up[k][u];
v = up[k][v];
}
}
// 最后一步到LCA
int[] candidates = {max1, max2, maxEdge[0][u], secondMaxEdge[0][u],
maxEdge[0][v], secondMaxEdge[0][v]};
max1 = -1; max2 = -1;
for (int val : candidates) {
if (val > max1) { max2 = max1; max1 = val; }
else if (val != max1 && val > max2) { max2 = val; }
}
return new int[]{max1, max2};
}
/**
* 求解严格次小生成树
* @return [MST权值, 严格次小生成树权值]，若不存在返回null
*/
public long[] solve() {
long mstWeight = kruskal();
buildLCA();
long secondMST = Long.MAX_VALUE;
for (Edge e : edges) {
if (e.inMST) continue; // 只考虑非树边
int[] res = queryMax(e.u, e.v);
int maxOnPath = res[0];
int secondMaxOnPath = res[1];
if (e.w > maxOnPath) {
// 用非树边替换最大边，得到更大的生成树
secondMST = Math.min(secondMST, mstWeight - maxOnPath + e.w);
} else if (e.w == maxOnPath && secondMaxOnPath != -1) {
// 需要严格次大值替换
secondMST = Math.min(secondMST, mstWeight - secondMaxOnPath + e.w);
}
}
if (secondMST == Long.MAX_VALUE) return null;
return new long[]{mstWeight, secondMST};
}
public static void main(String[] args) {
// 示例图：5个节点，7条边
SecondMST solver = new SecondMST(5);
solver.addEdge(1, 2, 1);
solver.addEdge(1, 3, 2);
solver.addEdge(2, 3, 3);
solver.addEdge(2, 4, 4);
solver.addEdge(3, 4, 5);
solver.addEdge(3, 5, 6);
solver.addEdge(4, 5, 7);
long[] result = solver.solve();
if (result != null) {
System.out.println("MST权值: " + result[0]);
System.out.println("严格次小生成树权值: " + result[1]);
} else {
System.out.println("不存在次小生成树");
}
// 验证：MST应为 1+2+4+6 = 13
// 次小生成树：用边(3,4,5)替换(2,4,4)，得到 1+2+5+6 = 14
// 或用边(2,3,3)替换(1,3,2)，得到 1+3+4+6 = 14
}
}
算法复杂度分析
- Kruskal求MST：
O(m log m)，m为边数 - DFS预处理：
O(n) - 倍增表构建：
O(n log n) - 枚举非树边：共
m - n + 1条，每条查询O(log n) - 总时间复杂度：
O(m log m + m log n) - 空间复杂度：
O(n log n + m)
算法扩展
第K小生成树
将边按权值排序后，利用MST的基尔霍夫矩阵树定理或拟阵交理论，可以推广到第K小生成树问题，复杂度显著上升。
带约束的生成树
次小生成树的思路可推广到度约束生成树、边数受限生成树等问题，核心仍是”替换边”策略配合适当的数据结构。
次小生成树展示了如何将MST作为基准，通过局部替换探索次优解。这种”基准+微调”的策略在组合优化中十分普遍，是理解更复杂优化问题的重要阶梯。
