本文共 1396 字，大约阅读时间需要 4 分钟。
Kruskal算法是基于贪心的算法，以边为基础进行扩展。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。合并的过程需要用到并查集（具体见）。
Kruskal的时间复杂度分析：
Kruskal算法每次要从都要从剩余的边中选取一个最小的边。通常我们要先对边按权值从小到大排序，这一步的时间复杂度为为O(|Elog|E|)。Kruskal算法的实现通常使用并查集，来快速判断两个顶点是否属于同一个集合。最坏的情况可能要枚举完所有的边，此时要循环|E|次，所以这一步的时间复杂度为O(|E|α(V))，其中α为Ackermann函数，其增长非常慢，我们可以视为常数。所以Kruskal算法的时间复杂度为O(|Elog|E|)。
代码：
#include#include #include #define INF 0xfffffff#define N 550using namespace std;struct Node{ int start, end, len; friend bool operator < (const Node& a, const Node& b){ return a.len < b.len; }};int father[N];int E, V;Node S[N];int GetFather(int cur){ // 并查集 获取父节点+ 路径压缩 return father[cur] == cur ? cur : father[cur] = GetFather(father[cur]);}bool Join(int a, int b){ // 判断a b两点是已连接 int fa = GetFather(a); int fb = GetFather(b); if(fa == fb){ return 1; } else{ father[fa] = fb; // 连接a b return 0; }}int Kruskal(){ int ans = 0; for(int i = 0; i < V; i++) // 边数添加完成后即可返回 if(!Join(S[i].start, S[i].end)) // 判断两点是否已经连接 ans += S[i].len; return ans;}int main(){ int loop; scanf("%d", &loop); while(loop --){ scanf("%d%d", &E, &V); for(int i = 1; i <= V; i ++){ // 初始化father数组 father[i] = i; } for(int i = 0; i < V; i ++) scanf("%d%d%d", &S[i].start, &S[i].end, &S[i].len); sort(S, S+V); int ans = Kruskal(); printf("%d\n", ans); } return 0;}
参考：
转载地址：http://kmgyf.baihongyu.com/