【图论】kruskal算法

一.介绍

 Kruskal（克鲁斯卡尔）算法是一种用于解决最小生成树问题的贪心算法。最小生成树是指在一个连通无向图中，选择一棵包含所有顶点且边权重之和最小的树。

下面是Kruskal算法的基本步骤：

1. 将图中的所有边按照权重从小到大进行排序。
2. 创建一个空的最小生成树集合（并查集实现）。
3. 遍历排序后的边，依次将边加入最小生成树集合中，但要确保加入的边不会形成环路。
   • 如果加入边后不会形成环路，则将该边加入最小生成树集合。
   • 如果加入边后会形成环路，（即在同一集合）则跳过该边。
4. 重复步骤3，直到最小生成树集合中的边数等于图中顶点数减1，或者遍历完所有边。
5. 最终得到的最小生成树集合即为所求的最小生成树。

Kruskal算法的核心思想是通过不断选择权重最小的边，并判断是否形成环路来构建最小生成树。它不需要事先知道图的连通性，而是通过边的选择来逐步连接图中的顶点，直到所有顶点都被连接为止。

需要注意的是，Kruskal算法适用于解决无向图的最小生成树问题，对于有向图则需要使用其他算法，如Prim算法。此外，Kruskal算法也可以处理带有边权重相同的情况。

---

二.模板题

P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

---

三.【AC】代码

#include<bits/stdc++.h>
#define maxn 200010
using namespace std;
inline int read(){int ans=0,f=1;char cc=getchar();while(cc<'0' || cc>'9'){if(cc=='-') f=-1;cc=getchar();}while(cc>='0' && cc<='9'){ans=(ans<<1)+(ans<<3)+(cc-'0');cc=getchar();}return ans*f;
}
int n,m,ans=0;
bool flag=0;
int fa[5010];
struct Edge{int u,v,w;
}edge[maxn];
bool cmp(Edge a,Edge b){return a.w<b.w;
}
inline int find(int x){return x==fa[x] ? x : fa[x]=find(fa[x]);
}
inline void merge(int x,int y){int fx=find(x),fy=find(y);fa[fx]=fy;
}
void kruskal(){sort(edge+1,edge+m+1,cmp);int cnt=0;for(int i=1;i<=m;i++){int x=edge[i].u,y=edge[i].v;if(find(x)==find(y)) continue;ans+=edge[i].w;merge(x,y);cnt++;if(cnt==n-1){flag=1;return;} }
}
int main(){//读入数据 n=read();m=read();for(int i=1;i<=m;i++){edge[i].u=read();edge[i].v=read();edge[i].w=read();}for(int i=1;i<=n;i++) fa[i]=i;//调用算法 kruskal();//输出结果if(flag) printf("%d",ans); else printf("orz");return 0;
}