Kruskal 算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。
1. 把图中的所有边按代价从小到大排序;
2. 把图中的n个顶点看成独立的n棵树组成的森林;
3. 按权值从小到大选择边,所选的边连接的两个顶点Ui和Vi,应属于两颗不同的树,则成为最小生成树的一条边,并将这两颗树合并作为一颗树。重复此操作,直到所有顶点都在一颗树内或者有n-1条边为止。
以下是一个无向图和按权值从小到大排列的边集数组。
以下是算法实现
#include <stdio.h>
#include <string.h>
#include <algorithm>
// 顶点个数的最大值
#define MAXN 11
// 边的个数的最大值
#define MAXM 20
using namespace std;
// 边
struct edge {
// 边的顶点、权值
int u, v, w;
// 边的数组
} edges[MAXM];
// parent[i]为顶点 i 所在集合对应的树中的根结点
int parent[MAXN];
// 顶点个数、边的个数
int n, m;
// 循环变量
int i, j;
// 初始化
void UFset(){
for (i = 1; i <= n; i++){
parent[i] = -1;
}
}
// 查找并返回节点 x 所属集合的根结点
int Find(int 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){
// r1 为 R1 的根结点,r2 为 R2 的根结点
int r1 = Find(R1), r2 = Find(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;
}
}
// 实现从小到大排序的比较函数
bool cmp(edge a, edge b){
return a.w <= b.w;
}
void Kruskal(){
// 生成树的权值
int weight = 0;
// 已选用的边的数目
int num = 0;
// 选用边的两个顶点
int u, v;
// 初始化 parent[]数组
UFset();
for (i = 0; i < m; i++){
u = edges[i].u;
v = edges[i].v;
if (Find(u) != Find(v)){
printf("%d %d %d\n", u, v, edges[i].w);
weight += edges[i].w;
num++;
Union(u, v);
};
if (num >= n - 1){
break;
}
};
printf("weight of MST is %d\n", weight);
}
int main(){
// 边的起点和终点及权值
int u, v, w;
// 读入顶点个数 n
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i++){
// 读入边的起点和终点
scanf("%d%d%d", &u, &v, &w);
edges[i].u = u;
edges[i].v = v;
edges[i].w = w;
}
sort(edges, edges + m, cmp);
Kruskal();
return 0;
}
克鲁斯卡尔算法采用快排则时间复杂度为O(N log N)
对比普里姆和克鲁斯卡尔算法,普里姆算法对于稠密图,即边数非常多的情况下更好一些;而克鲁斯卡尔算法主要针对边来展开,边数少时效率比较高,所以对于稀疏图有较大的优势。