本文共 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;}
     
    
   

参考：

转载地址：https://blog.csdn.net/zhj_fly/article/details/74026126 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！