本文通过具体的算法模板题，给出Prim和Kruskal两种求解最小生成树求解过程和代码~
由浅入深，通俗易懂
题目选自洛谷P3366
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出orz。
输入格式
第一行包含两个整数N,M，表示该图共有N个结点和M条无向边。
接下来M行每行包含三个整数 Xi,Yi,Zi，表示有一条长度为Zi的无向边连接结点 Xi,Yi。
输出格式
如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出orz。
输入输出样例
输入 1
4 51 2 21 3 21 4 32 3 43 4 3
输出 1
7
说明/提示
数据规模：
对于20%的数据，N≤5，M≤20。
对于40%的数据，N≤50，M≤2500。
对于70%的数据，N≤500，M≤104。
对于 100%的数据：1≤N≤5000，1≤M≤2×10^5，1≤Zi≤10^4。
前言
两者区别：Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。
两者其实都是运用贪心的思路
Prim算法思想：
Prim的思想是将任意节点作为根，再找出与之相邻的所有边（用一遍循环即可），再将新节点更新并以此节点作为根继续搜，维护一个数组：dis，作用为已用点到未用点的最短距离。
具体算法流程图解如下：
优化：
但是！由于该题数据比较大，我们应该做一些优化
例如Prim可以用优先队列(也即 堆)来优化算法
Kruskal算法思想：
Kruskal算法的思想比Prin好理解一些。先把边按照权值进行排序，用贪心的思想优先选取权值较小的边，并依次连接，若出现环则跳过此边继续搜，直到已经使用的边的数量比总点数少一即可。
具体算法流程图解如下：
优化：
但是！由于该题数据比较大，我们应该做一些优化
例如Kruskal可以用并查集优化一下
Prim解题代码：
#include<cstdio>#include<queue>#include<cstring>#include<algorithm>#define R register intusing namespace std;int k,n,m,cnt,sum,ai,bi,ci,head[5005],dis[5005],vis[5005];struct Edge{int v,w,next;}e[400005];void add(int u,int v,int w){e[++k].v=v;e[k].w=w;e[k].next=head[u];head[u]=k;}typedef pair <int,int> pii;priority_queue <pii,vector<pii>,greater<pii> > q;void prim(){dis[1]=0;q.push(make_pair(0,1));while(!q.empty()&&cnt<n){int d=q.top().first,u=q.top().second;q.pop();if(vis[u]) continue;cnt++;sum+=d;vis[u]=1;for(R i=head[u];i!=-1;i=e[i].next)if(e[i].w<dis[e[i].v])dis[e[i].v]=e[i].w,q.push(make_pair(dis[e[i].v],e[i].v));}}int main(){memset(dis,127,sizeof(dis));memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);for(R i=1;i<=m;i++){scanf("%d%d%d",&ai,&bi,&ci);add(ai,bi,ci);add(bi,ai,ci);}prim();if (cnt==n)printf("%d",sum);else printf("orz");}
Kruskal解题代码：
#include<iostream>#include<stdio.h>#include<math.h>#include<algorithm>using namespace std;#define MAX_N 5000+5#define MAX_M 200000+5struct edge{int u,v;int w;}E[MAX_M];int f[MAX_N];int n,m;bool cmp(edge a,edge b){return a.w < b.w;}void init(){for(int i=1;i<=n;i++) f[i] = i;}int find(int x){if(f[x] == x) return x;return f[x] = find(f[x]);}void merge(int x,int y){f[find(x)] = find(y);}int Kruskal(){int ans = 0, cnt = 0;init();sort(E+1,E+1+m,cmp);for(int i = 1;i<=m;i++){if(cnt == n-1) break;if(find(E[i].u) != find(E[i].v)){merge(E[i].u,E[i].v);ans += E[i].w;cnt++;}}if(cnt != n-1) return 0;return ans;}int main(){scanf("%d%d",&n,&m);for(int i = 1;i<=m;i++)scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);int ans = Kruskal();if(ans) printf("%d",ans);else printf("orz");return 0;}
