1. 问题

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。

2. 解析

1.Prim算法：

1).初始化：Vnew= {x}，其中x为集合V中的任一节点（起始点），Enew= {},为空；

2).重复下列操作，直到Vnew= V：

a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；

2.kruscal算法：

先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

3. 设计

使用优先队列优化的prim算法：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=100000+10;
 4 const int maxm=100000+10;
 5 int n,m;
 6 int vis[maxn];        //用来判断该点是否在最小生成树中 
 7 struct node{          //存边的信息 
 8     int to,dis;
 9     bool operator <(const node &a)const{
10         return dis>a.dis;
11     }
12 };
13 vector<node>e[maxn];             //用vector容器来存边 
14 priority_queue<node>q;           //优先队列优先选择边权最小的边 
15 /*----------以下为prim算法----------*/ 
16 void prim(){
17     int ans=0;                   //表明最小生成树的权值 
18     int cnt=0;                   //表明在最小生成树中的点的数量 
19     q.push((node){1,0});
20     while(!q.empty()&&cnt<n){
21         node k=q.top();q.pop();
22         if(vis[k.to])continue;   //表明该点已经在最小生成树中 
23         vis[k.to]=1;
24         ans+=k.dis;
25         cnt++;
26         for(int i=0;i<e[k.to].size();++i){
27             if(!vis[e[k.to][i].to]){
28                 q.push((node){e[k.to][i].to,e[k.to][i].dis});
29             }
30         }
31     }
32     printf("%d
",cnt==n?ans:-1);
33 }
34 /*----------以上为prim算法----------*/ 
35 void init(){                    //初始化 
36     while(!q.empty())q.pop();
37     for(int i=1;i<=n;++i)e[i].clear(),vis[i]=0;
38 }
39 int main(){
40     while(scanf("%d %d",&n,&m)!=EOF){    //n代表点的数量，m代表边的数量 
41         init();
42         for(int i=1;i<=m;++i){
43             int x,y,z;
44             scanf("%d %d %d",&x,&y,&z);
45             e[x].push_back((node){y,z});
46             e[y].push_back((node){x,z});
47         }
48         prim();
49     }
50     return 0;
51 }

kruscal算法：

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 const int maxn=100000+10;
 5 const int maxm=100000+10;
 6 int n,m;
 7 struct edge{
 8     int from,to,cost;
 9 }e[maxm];
10 bool cmp(struct edge &a,struct edge &b){
11     return a.cost<b.cost;
12 }
13 /*----------以下为通过并查集维护联通快----------*/
14 int fa[maxn];
15 int find(int x){
16     return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
17 }
18 void baba(int x,int y){
19     int fx=find(x),fy=find(y);
20     fa[fx]=fy;
21 }
22 /*----------以上为通过并查集维护联通快----------*/
23 /*----------以下为kruskal----------*/
24 int kruskal(){
25     int cnt=1;                     //表明包含在最小生成树内的点的数量 
26     int res=0;                     //表明最小生成树的边权和 
27     sort(e+1,e+1+m,cmp);           //将每条边按照权值从小到大进行排序 
28     for(int i=1;i<=m;++i){
29         int fx=find(e[i].from),fy=find(e[i].to);
30         if(fx==fy)continue;        //若在同一联通块内，则调过本次循环 
31         baba(e[i].from,e[i].to);   //联通e[i].from和e[i].to 
32         cnt++;
33         res+=e[i].cost;
34         if(cnt==n)break;
35     }
36     return cnt==n?res:-1;   //若cnt不等于n,则表明无法生成最小生成树,输出-1 
37 }
38 /*----------以上为kruskal----------*/
39 void init(){  //初始化 
40     for(int i=1;i<=n;++i)fa[i]=i;
41 }
42 int main(){
43     while(scanf("%d %d",&n,&m)!=EOF){   //n表示点的数量,m表示边的数量 
44         init();
45         for(int i=1;i<=m;++i){
46             scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].cost);
47         }
48         printf("%d
",kruskal());
49     }
50 }

4. 分析

//n为点的数量，m为边的数量

使用优先队列的Prim复杂度为：mlogn

Kruscal算符复杂度为：mlogm

5. 源码

Kruscal：https://github.com/JayShao-Xie/algorithm-work/blob/master/kruskal.cpp

Prim：https://github.com/JayShao-Xie/algorithm-work/blob/master/prim.cpp