Prim算法
算法步骤
S:当前已经在联通块中的所有点的集合 1. dist[i] = inf 2. for n 次 t<-S外离S最近的点 利用t更新S外点到S的距离 st[t] = true n次迭代之后所有点都已加入到S中 联系：Dijkstra算法是更新到起始点的距离，Prim是更新到集合S的距离
算法复杂度
O（n2）
代码
题目：https://www.acwing.com/problem/content/description/860/
#include<bits/stdc++.h> using namespace std; const int N=550,INF=0x3f3f3f3f; int n,m; int dist[N]; int g[N][N]; bool st[N]; int prim() { int ans=0; memset(dist,0x3f,sizeof(dist)); int i,j; for(i=0;i<n;i++) { int t=-1; for(j=1;j<=n;j++) { if(!st[j]&&(t==-1||dist[t]>dist[j])) t=j; } //如果不是第一个点，并且距离为INF，代表不联通 if(i&&dist[t]==INF) return INF; //非第一个点，且联通，将点加入，一定要先加入后更新 if(i) ans+=dist[t]; //如果先更新，则会出现g[t][t]小于dist[j]，会出现自环 for(j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]); //标记到集合 st[t]=true; } return ans; } int main() { int i,j; cin>>n>>m; //初始化两点距离 memset(g,0x3f,sizeof(g)); while(m--) { int u,v,w; cin>>u>>v>>w; g[u][v]=g[v][u]=min(g[u][v],w); } int t=prim(); if(t==INF) puts("impossible"); else cout<<t; return 0; }
Kruskal算法
算法步骤
代码
题目：https://www.acwing.com/problem/content/description/861/
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,m; int p[N]; struct node { int u,v,w; bool operator< (const node &W)const { return w<W.w; } }edges[N]; int find(int x) { if(p[x]!=x) p[x]=find(p[x]); return p[x]; } int main() { int i,j; cin>>n>>m; for(i=0;i<m;i++) { int u,v,w; cin>>u>>v>>w; edges[i]={u,v,w}; } //排序 sort(edges,edges+m); //初始化 for(i=0;i<n;i++) p[i]=i; //记录边权值和，边数 int cnt=0; int ans=0; for(i=0;i<m;i++) { int u,v,w; u=edges[i].u,v=edges[i].v,w=edges[i].w; //找到对应的祖先 int a=find(u); int b=find(v); //若不在一个集合，就归入 if(a!=b) { ans+=w; cnt++; //指定的是u，v的祖先，归一 p[a]=b; } } //若不为n-1条边，则代表不联通 if(cnt<n-1) cout<<"impossible"; else cout<<ans; return 0; }