详解次小生成树以及相关的C++求解方法
次小生成树的定义
设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
33
121
232
313
44
122
232
342
412
样例输出：
4
6
ac代码（注释写的比较清楚）：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#defineMAX100000
intfather[210];//并查集
intvisit[210];//记录最小生成树用到的边的下标
intwindex;//记录最小生成树用到边的数量
typedefstructnode{
intst,ed,w;
}node;
/**
*预处理并查集数组
*/
voidpreProcess()
{
inti,len=sizeof(father)/sizeof(father[0]);
for(i=0;i<len;i++){
father[i]=i;
}
}
/**
*kruskal使用贪心算法，将边按权值从小到大排序
*/
intcmp(constvoid*p,constvoid*q)
{
constnode*a=p;
constnode*b=q;
returna->w-b->w;
}
/**
*并查集寻找起始结点，路径压缩优化
*/
intfindParent(intx)
{
intparent;
if(x==father[x]){
returnx;
}
parent=findParent(father[x]);
father[x]=parent;
returnparent;
}
/**
*求最小生成树
*/
intminTree(node*points,intm,intn)
{
preProcess();
inti,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;
}
}
returnflag;
}
/**
*求次小生成树
*/
intsecMinTree(node*points,intm,intn)
{
inti,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;
returnmin;
}
intmain(void)
{
inti,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);
}
return0;
}