最小生成树可以说是图论入门的基础题型，现总结如下。
什么是最小生成树？
我们知道树是一种图，每个结点都有与之相连的许多结点，对于一个树，给定它的边，每个边都有各自的权值，我们希望以最小的代价来使树上个点相连，那么我们就需要去找出一种实现这样的期望的方法，即我们所要求的，就是最小生成树。
常见算法：1、Prim算法：首先将点分为两类，已选择的和未选择的，先随机选一个点作为初始点每一步从所有连接两种类型的点的边中，选取一条权值最小的加入生成树，再将点加入已选择当中。复杂度取决于如何选择最小边，暴力选取复杂度为O(MN)，二叉堆维护为O(MlogN），斐波那契堆维护为O(M+NlogN)。类似Dijkstra，我们需要一个dis数组和vis数组
2、Kruskal算法：使用并查集维护树的连通性，首先将所有边按从小到大排序，并认为每一个点是孤立的，按从小到大的顺序枚举每一条边，如果这条边连接的两个点不在一个连通块内，那么就把这条边加入最小生成树，将两个连通块合并，反之continue复杂度O(mlogm+nk);
二者区别：Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。
Prim代码：
#include<bits/stdc++.h> using namespace std; #define re register #define il inline il int read() { re int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘) x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*f; }//快读，不理解的同学用cin代替即可 #define inf 123456789 #define maxn 5005 #define maxm 200005 struct edge { int v,w,next; }e[maxm<<1]; //注意是无向图，开两倍数组 int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans; //已经加入最小生成树的的点到没有加入的点的最短距离，比如说1和2号节点已经加入了最小生成树，那么dis[3]就等于min(1->3,2->3) bool vis[maxn]; //链式前向星加边 il void add(int u,int v,int w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } //读入数据 il void init() { n=read(),m=read(); for(re int i=1,u,v,w;i<=m;++i) { u=read(),v=read(),w=read(); add(u,v,w),add(v,u,w); } } il int prim() { //先把dis数组附为极大值 for(re int i=2;i<=n;++i) { dis[i]=inf; } //这里要注意重边，所以要用到min for(re int i=head[1];i;i=e[i].next) { dis[e[i].v]=min(dis[e[i].v],e[i].w); } while(++tot<n)//最小生成树边数等于点数-1 { re int minn=inf;//把minn置为极大值 vis[now]=1;//标记点已经走过 //枚举每一个没有使用的点 //找出最小值作为新边 //注意这里不是枚举now点的所有连边，而是1~n for(re int i=1;i<=n;++i) { if(!vis[i]&&minn>dis[i]) { minn=dis[i]; now=i; } } ans+=minn; //枚举now的所有连边，更新dis数组 for(re int i=head[now];i;i=e[i].next) { re int v=e[i].v; if(dis[v]>e[i].w&&!vis[v]) { dis[v]=e[i].w; } } } return ans; } int main() { init(); printf("%d",prim()); return 0; }
Kruskal代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int maxn = 1e5+5; struct node{ int from,to,v; friend bool operator < (const node& a,const node& b) { return a.v<b.v; } }map[2*maxn]; int n,m; int fa[5001]; /*void add(int x,int y,int z) { count++; to[count] = y; v[count] = z; next[count] = head[x] head[x] = count; }*/ int get(int x) { if(fa[x] == x) return x; else return fa[x] = get(fa[x]); } bool Union(int x,int y) { if(get(x) == get(y)) return true; else return false; } int main() { cin>>n>>m; int x,y,z,ans=0; for(int i=1; i<=n; i++) fa[i] = i; for(int i=1; i<=m; i++) { cin>>x>>y>>z; map[i] =(node){x,y,z}; } int num=0; sort(map+1,map+1+m); for(int i=1; i<=m; i++) { if(num==n-1) { cout<<ans; return 0; } if(!Union(map[i].from,map[i].to)){ fa[get(map[i].from)] = get(map[i].to); ans+=map[i].v; num++; } } cout<<"orz"; return 0; }
当然还有其他实现最小生成树的办法，后面会补充
原文：https://www.cnblogs.com/delta-cnc/p/12321251.html