次小生成树算法分析（各种实现方法）
最小生成树算法分析

因为本人感觉也不能很好的表达出最小生成树的本质所在，所以下面是摘抄了集百家之长所写的有关最小生成树的算法分析。

提供实践机会：本校题题目链接 && 北大题题目链接（数据弱爆了）

一、 最小生成树的算法想必大家都很了解，主要有kruskal和prim。但如果要求次小生成树(即第二小的生成树)呢？

一种容易想到的方法是枚举删除最小生成树上的边，再求最小生成树。用kruskal这种算法的复杂度为O(n*elog2e)，当图比较稠密时，复杂度接近O(n^3)。

但有一种更简单的方法：先求最小生成树T，枚举添加不在T中的边，则添加后一定会形成环。找到环上边值第二大的边(即环中属于T中的最大边)，把它删掉，计算当前生成树的权值，取所有枚举修改的生成树的最小值，即为次小生成树。

这种方法在实现时有更简单的方法：首先求最小生成树T，然后从每个结点u遍历最小生成树T，用一个二维数组max[u][v]记录结点u到结点v的路劲上边的最大值(即最大边的值)。然后枚举不在T中的边(u,v)，计算T- max[u][v] + w(u,v)的最小值，即为次小生成树的权值。显然，这种方法的时间复杂度为O(n^2 + e)。

可见，第二种算法将原来的时间复杂度O(n^3)提高到了O(n^2)。

算法实现：（原创代码可能有点混乱，等有时间了在改写成自己的）

#include <iostream>#include <algorithm>#include <queue>const int INF = 0x7fffffff;const int MAX = 10001;int n,m;int num;int p[MAX];int max[101][101];struct Edge//原始图{int from;int to;int w;bool flag;}e[MAX];struct Tree//最小生成树{int to;int w;int next;}tree[202];int index[101];struct Node//生成树的结点{int seq;//结点编号int max;//从某个点到它的路径中的最大边的长度};bool cmp(const Edge &a, const Edge &b){return a.w < b.w;}void makeSet(){for(int i = 0; i <= n; i++){p[i] = i;}}int findSet(int x){if(x != p[x])p[x] = findSet(p[x]);return p[x];}void addEdge(int from, int to, int w){tree[num].to = to;tree[num].w = w;tree[num].next = index[from];index[from] = num++;}int kruscal(){int i,j;int x, y;int edgeNum = 0;int result = 0;makeSet();std::sort(e,e+m,cmp);for(i = 0; i < m; i++){x = findSet(e[i].from);y = findSet(e[i].to);if(x != y){edgeNum++;addEdge(e[i].from,e[i].to,e[i].w);addEdge(e[i].to,e[i].from,e[i].w);e[i].flag = true;p[x] = y;result += e[i].w;}}return edgeNum == n-1 ? result : -1;}void bfs(int p){int i,j;bool used[101];memset(used,0,sizeof(used));std::queue<Node> que;Node now,adj;now.max = 0;now.seq = p;que.push(now);used[p] = true;while(!que.empty()){Node q = que.front();que.pop();for(i = index[q.seq]; i != -1; i = tree[i].next){adj.seq = tree[i].to;adj.max = tree[i].w;if(!used[adj.seq]){if(q.max > adj.max)adj.max = q.max;max[p][adj.seq] = adj.max;used[adj.seq] = true;que.push(adj);}}}}void second_MST(){int i,j;int mst = kruscal();for(i = 1; i <= n; i++)bfs(i);int smst = INF;for(i = 0; i < m; i++){if(!e[i].flag){if(mst + e[i].w - max[e[i].from][e[i].to] < smst)smst = mst + e[i].w - max[e[i].from][e[i].to];}}if(smst == mst)printf("Not Unique!\n");elseprintf("%d\n",mst);}int main(){int i,j;int cases;int a,b,w;scanf("%d",&cases);while(cases--){scanf("%d %d",&n,&m);for(i = 0; i < m; i++){scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].w);e[i].flag = false;}num = 0;memset(index,-1,sizeof(index));second_MST();}return 0;}

二、次小生成树，顾名思义就是在所有的生成树中第二小的生成树，（最小的当然是最小生成树了，废话了），话说求次小生成树有两种方法：

1：首先求出最小生成树T，然后枚举最小生成树上的边，计算除了枚举的当前最小生成树的边以外的所有边形成的最小生成树Ti，然后求最小的Ti就是次小生成树。

2：首先计算出最小生成树T，然后对最小生成树上任意不相邻的两个点 （i,j）添加最小生成树以外的存在的边形成环，然后寻找i与j之间最小生成树上最长的边删去，计算map[i][j]（最小生成树以外存在的边） 与 maxd[i][j]（最小生成树上最长的边）差值，求出最小的来，w(T)再加上最小的差值就是次小生成树了。

这道题的题意是：判断该图的最小生成树是否唯一，有两种办法；

1：求其最小生成树，如果最小生成树的长度与次小生成树的长度相等（这里只要判断最小差值是否为0即可），则不唯一。否则唯一。

算法二，就是一中给的方法，这里不再赘述；

算法一的实现（本人原创）：

Kruscal实现版：

 #include <iostream>#include <algorithm>#include <string>#include <cstring>#include <cstdio>using namespace std;const int VN = 5e2+10;const int EN = 2e5+10;int V,E,f[VN],p[VN];struct Edge{int x,y,w;}edge[EN];bool cmp(Edge a,Edge b){    return a.w < b.w;}void SetFather(){    for(int i = 0;i <= V;++i)      f[i] = i;}int Kruskal(){    SetFather();    int ans = 0,vertex = 0;    sort(edge,edge+E,cmp);    for(int i = 0;i != E;++i)    {        int x = edge[i].x;        int y = edge[i].y;        int u,v;        for(u = x;u != f[u];u = f[u])          f[u] = f[f[u]];        for(v = y;v != f[v];v = f[v])          f[v] = f[f[v]];        if(u != v){           f[u] = v;           p[vertex++] = i;           ans += edge[i].w;        }        if(vertex == V-1)break;    }    return ans;}int SKruskal(int del){    SetFather();    int ans = 0,vertex = 0;    for(int i = 0;i != E;++i)    {        if(i == del)continue;        int x = edge[i].x;        int y = edge[i].y;        int u,v;        for(u = x;u != f[u];u = f[u])          f[u] = f[f[u]];        for(v = y;v != f[v];v = f[v])          f[v] = f[f[v]];        if(u != v){           f[u] = v;           vertex++;           //p[vertex++] = i;           ans += edge[i].w;        }        if(vertex == V-1)break;    }    if(vertex < V-1) ans = -1;    return ans;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&V,&E);        for(int i = 0;i != E;++i)          scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].w);        int TotCost = Kruskal();        bool flag = 0;        for(int i = 0;i != V-1;i++){          if(SKruskal(p[i]) == TotCost){              flag = 1;              break;          }        }        if(flag)          printf("Yes\n");        else          printf("No\n");    }    return 0;}        

Prim实现版

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int inf = 0x7fffffff;const int size = 501;int firstpath[size][size];int secondpath[size][size];int pre[size];int d[size];int tree[size];int t=0;bool flag[size];int V,E;int qmax(int x,int y){   if(x>y)return x;   else return y;}void prime(int u){   int i,j;   for(i=1;i<=V;++i)    {      flag[i]=false;      d[i]=inf;    }   for(i=1;i<=V;++i)    for(j=i;j<=V;++j)     secondpath[i][j]=secondpath[j][i]=-1;   t=0;   tree[t++]=u;   flag[u]=true;   for(i=1;i<V;++i)    {       int min=inf;       int k;       for(j=1;j<=V;++j)        {           if(d[j]>firstpath[u][j])            {              d[j]=firstpath[u][j];              pre[j]=u;            }           if(!flag[j] && d[j]<min)            {               min=d[j];               k=j;            }        }        for(j=0,u=k;j<t;++j)         {           secondpath[tree[j]][u]=qmax(secondpath[tree[j]][pre[u]],d[u]);           secondpath[u][tree[j]]=secondpath[tree[j]][u];         }       firstpath[pre[u]][u]=firstpath[u][pre[u]]=inf;       flag[u]=true;       tree[t++]=u;    }   for(i=1;i<=V;++i)    for(j=i+1;j<=V;++j)     if(firstpath[i][j]!=inf && firstpath[i][j]==secondpath[j][i])      {        printf("Yes\n");        return ;      }   printf("No\n");}int main(){   int i,T,j,x,y,z;   scanf("%d",&T);   while(T--)    {      scanf("%d%d",&V,&E);      for(i=1;i<=V;++i)       for(j=i;j<=V;++j)        firstpath[i][j]=firstpath[j][i]=inf;      for(i=0;i<E;++i)       {          scanf("%d%d%d",&x,&y,&z);          firstpath[x][y]=firstpath[y][x]=z;       }      prime(1);    }   return 0;}