次小生成树的定义

设 G=(V,E,w)是连通的无向图，T 是图G 的一个最小生成树。如果有另一棵树T1，满

足不存在树T',ω（T'）<ω（T1） ，则称T1是图G的次小生成树。

求解次小生成树的算法

约定：由T 进行一次可行交换得到的新的生成树所组成的集合，称为树T的邻集,记为N(T)。

定理 3：设T是图G的最小生成树，如果T1满足ω(T1)=min{ω(T')| T'∈N(T)},则T1是G

的次小生成树。

证明：如果 T1 不是G 的次小生成树，那么必定存在另一个生成树T',T'=T 使得

ω(T)≤ω(T')<ω(T1)，由T1的定义式知T不属于N(T)，则

E(T')/E(T)={a1,a2

1,……,at}，E(T)/E(T')={b1,b2,……,bt}，其中t≥2。根据引理1 知，存在一

个排列bi1,bi2,……,bit，使得T+aj-bij仍然是G 的生成树，且均属于N(T),所以ω(aj)≥ω(bij)，

所以ω(T')≥ω(T+aj-bij)≥ω(T1)，故矛盾。所以T1是图G 的次小生成树。

通过上述定理，我们就有了解决次小生成树问题的基本思路。

首先先求该图的最小生成树T。时间复杂度O(Vlog2V+E)

然后，求T的邻集中权值和最小的生成树，即图G 的次小生成树。

如果只是简单的枚举，复杂度很高。首先枚举两条边的复杂度是O(VE)，再判断该交换是否

可行的复杂度是O(V)，则总的时间复杂度是O(V2E)。这样的算法显得很盲目。经过简单的

分析不难发现，每加入一条不在树上的边，总能形成一个环，只有删去环上的一条边，才能

保证交换后仍然是生成树，而删去边的权值越大，新得到的生成树的权值和越小。我们可以

以此将复杂度降为O(VE)。这已经前进了一大步，但仍不够好。

回顾上一个模型——最小度限制生成树，我们也曾面临过类似的问题，并且最终采用动态规

划的方法避免了重复计算，使得复杂度大大降低。对于本题，我们可以采用类似的思想。首

先做一步预处理，求出树上每两个结点之间的路径上的权值最大的边，然后，枚举图中不在

树上的边，有了刚才的预处理，我们就可以用O(1)的时间得到形成的环上的权值最大的边。

如何预处理呢？因为这是一棵树，所以并不需要什么高深的算法，只要简单的BFS 即可。

预处理所要的时间复杂度为O(V2)。

这样，这一步时间复杂度降为O(V2)。

综上所述，次小生成树的时间复杂度为O(V2)。

练习

题目：

题目描述：

最小生成树大家都已经很了解，次小生成树就是图中构成的树的权值和第二小的树，此值也可能等于最小生成树的权值和，你的任务就是设计一个算法计算图的最小生成树。

输入：

存在多组数据，第一行一个正整数t，表示有t组数据。

每组数据第一行有两个整数n和m（2<=n<=100），之后m行，每行三个正整数s，e，w，表示s到e的双向路的权值为w。

输出：

输出次小生成树的值，如果不存在输出-1。

样例输入：

2

3 3

1 2 1

2 3 2

3 1 3

4 4

1 2 2

2 3 2

3 4 2

4 1 2

样例输出：

4

6

ac代码（注释写的比较清楚）：

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100000 int father[210]; // 并查集 int visit[210]; // 记录最小生成树用到的边的下标 int windex; // 记录最小生成树用到边的数量 typedef struct node { int st, ed, w; } node; /** * 预处理并查集数组 */ void preProcess() { int i, len = sizeof(father) / sizeof(father[0]); for (i = 0; i < len; i ++) { father[i] = i; } } /** * kruskal使用贪心算法，将边按权值从小到大排序 */ int cmp(const void *p, const void *q) { const node *a = p; const node *b = q; return a->w - b->w; } /** * 并查集寻找起始结点，路径压缩优化 */ int findParent(int x) { int parent; if (x == father[x]) { return x; } parent = findParent(father[x]); father[x] = parent; return parent; } /** * 求最小生成树 */ int minTree(node *points, int m, int n) { preProcess(); int i, count, flag, pa, pb; for (i = count = flag = windex = 0; i < m; i ++) { pa = findParent(points[i].st); pb = findParent(points[i].ed); if (pa != pb) { visit[windex ++] = i; father[pa] = pb; count ++; } if (count == n - 1) { flag = 1; break; } } return flag; } /** * 求次小生成树 */ int secMinTree(node *points, int m, int n) { int i, j, min, tmp, pa, pb, count, flag; for (i = 0, min = MAX; i < windex; i ++) { preProcess(); // 求次小生成树 for (j = count = tmp = flag = 0; j < m; j ++) { if (j != visit[i]) { pa = findParent(points[j].st); pb = findParent(points[j].ed); if (pa != pb) { count ++; tmp += points[j].w; father[pa] = pb; } if (count == n - 1) { flag = 1; break; } } } if (flag && tmp < min) min = tmp; } min = (min == MAX) ? -1 : min; return min; } int main(void) { int i, t, n, m, flag, min; node *points; scanf("%d", &t); while (t --) { scanf("%d %d", &n, &m); points = (node *)malloc(sizeof(node) * m); for (i = 0; i < m; i ++) { scanf("%d %d %d", &points[i].st, &points[i].ed, &points[i].w); } qsort(points, m, sizeof(points[0]), cmp); flag = minTree(points, m, n); if (flag == 0) { // 无法生成最小生成树 printf("-1n"); continue; } else { min = secMinTree(points, m, n); printf("%dn", min); } free(points); } return 0; }