Kruskal算法介绍与实现

本文主要是介绍Kruskal算法介绍与实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最小生成树（MinimumSpanning Tree,MST）或者称为最小代价生成树：对无向连通图的生成树，各边的全值总和称为生成树的权，权最小的生成树称为最小生成树。

构造最小生成树的准则有三条：

（1）必须只使用该网络中的边来构造最小生成树；

（2）必须使用且仅使用n-1条边来连接网络中的n个顶点；

（3）不能使用产生回路的边。

构造最小生成树的算法主要有：克鲁斯卡尔（Kruskal）算法、Boruvka算法、和普里姆（Prim）算法，他们均遵循以上准则，且都采用了一种逐步求解的策略。

Kruskal算法的基本思想是以边为主导地位，始终都是选择当前可用的最小权值的边，步骤如下：

（1）设一个有n个顶点的连通网络为G（V,E），最初先构造一个只有n个顶点，没有边的非连通图T{V,Ø}，图中每个顶点自成一个连通分量；

（2）当在E中选择一条具有最小权值的边时，若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则，即这条边的两个顶点落在同一个连通分量上，则将此边舍去（此后永不选用这条边），重新选择一条权值最小的边；

（3）如此重复下去，直到所有顶点在同一个连通分量上为止。

Kruskal算法实现：

以下图无向网为例：

利用Kruskal算法求上图所示的无向网的最小生成树，并输出依次选择的各条边及最终求得的最小生成树的权。数据输入格式：第一行为顶点个数n和边数m，第二行开始为每条边的数据：u,v,w，分别表示这条边的两个顶点及边上的权值。顶点序号从1开始计起。

解：Code：

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;#define MAXN 11		//顶点个数的最大值
#define MAXM 20		//边的个数的最大值
struct edge			//边
{int u, v, w;
}edges[MAXM];		//边的数组
int parent[MAXN];	//parent[i]为顶点i所在集合对应的树中的根结点
int n, m;			//顶点个数、边的个数
int i, j;			//循环变量
void UFset()		//初始化 
{for(i = 1; i <= n; i++) parent[i] = -1;
}
int Find(int x)		//查找并返回结点x所属集合的根结点
{int s;			//查找位置for(s = x; parent[s] >=0; s = parent[s]) ;while(s != x)	//优化方案——压缩路径，使后续的查找操作加速{int tmp = parent[x];parent[x] = s;x = tmp;}return s;
}
//运用并查集，将两个不同集合的元素进行合并，使两个集合中任意两个元素都连通
void Union(int R1, int R2)
{int r1 = Find(R1), r2 = Find(R2);		//r1和r2分别为R1和R2的根结点int tmp = parent[r1] + parent[r2];		//两个集合结点数之和（负数）//如果R2所在树结点个数 > R1所在树结点个数（注意parent[r1]是负数）if(parent[r1] > parent[r2]){parent[r1] = r2;parent[r2] = tmp;}else{parent[r2] = r1;parent[r1] = tmp;}
}
int cmp(const void *a, const void *b)		//实现从小到大的比较函数
{edge aa = *(const edge *)a, bb = *(const edge *)b;return aa.w-bb.w;
}
void Kruskal()
{int sumweight = 0;		//生成树的权值int num = 0;			//已选用的边的数目UFset();				//初始化parent数组for(i = 0; i < m; i++){if(Find(edges[i].u) != Find(edges[i].v)){printf("%d %d %d\n", edges[i].u, edges[i].v, edges[i].w);sumweight += edges[i].w; num++;Union(edges[i].u, edges[i].v);}if(num >= n-1) break;}printf("The weight of MST is : %d\n", sumweight);
}
void main()
{scanf("%d%d", &n, &m);	//读入顶点个数和边数for(int i = 0; i < m; i++)scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w);	//读入边的起点和终点printf("The edges chosen are :\n");qsort(edges, m, sizeof(edges[0]), cmp);	//对边按权值从小到大排序Kruskal();
}

运行结果：