次小生成树的定义
设 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代码（注释写的比较清楚）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
#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("-1\n");
continue;
} else {
min = secMinTree(points, m, n);
printf("%d\n", min);
}
free(points);
}
return 0;
}
|