Prim
与dijistra比较像，分为朴素版和堆优化版。
朴素版Prim，时间复杂度O(n^2)，一般用于稠密图。
算法流程：初始化距离矩阵为0x3f3f3f3f.
循环n次，找到距离集合最短的点t，用t更新其他点到集合的距离。
注意：与dijistra不同的在与距离的更新方式。
Prim最小生成树
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 510;
int g[maxn][maxn],n,m;
int dis[maxn];
bool st[maxn];
int prim(){
int ans=0;
memset(dis,0x3f,sizeof dis);
for(int i=0;i<n;i++){
int t = -1;
for(int j=1;j<=n;j++){
if(!st[j] && (t==-1 || dis[j]<dis[t]))
t = j;
}
if(i && dis[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
if(i) ans += dis[t];
for(int i=1;i<=n;i++) dis[i] = min(dis[i],g[t][i]);
st[t] = true;
}
return ans;
}
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=min(g[a][b],c);
}
int t = prim();
if(t == 0x3f3f3f3f) puts("impossible");
else cout<<t;
return 0;
}
堆优化版Prim，时间复杂度O(m*logn)，一般不常用。
Kruskal
时间复杂度O(m*logm)，一般用于稀疏图。
算法流程：
1.将所有边按照权重大小，从小到大排序。
2.枚举每条边a,b。如果a,b不连通，则将边加入集合。
Kruskal
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 2e5 + 10;
const int N=1e5 + 10;
int n,m,p[N];
struct Edge{
int a,b,c;
}edges[maxn];
bool cmp(Edge a,Edge b){
return a.c < b.c;
}
int find(int x){
if(p[x] != x) return p[x] = find(p[x]);
}
int kluskal(){
sort(edges + 1,edges + 1 + m,cmp);
int ans=0,cnt=0;
for(int i=1;i<=m;i++){
int a = edges[i].a,b = edges[i].b,c = edges[i].c;
a = find(a),b=find(b);
if(a != b){
p[a] = b;
ans += c;
cnt++;
}
}
if(cnt < n-1) return -1;
else return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) p[i] = i;
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
edges[i]={a,b,c};
}
int t = kluskal();
if(t==-1) puts("impossible");
else cout<<t<<endl;
return 0;
}
判断二分图
O(m+n)