目录
概念
思路
代码
概念
克鲁斯卡尔算法查找最小生成树的方法是:将连通网中所有的边按照权值大小做升序排序,从权值最小的边开始选择,只要此边不和已选择的边一起构成环路,就可以选择它组成最小生成树。对于 N 个顶点的连通网,挑选出 N-1 条符合条件的边,这些边组成的生成树就是最小生成树。
举个例子,图 1 是一个连通网,克鲁斯卡尔算法查找图 1 对应的最小生成树,需要经历以下几个步骤:
图 1 连通网
1) 将连通网中的所有边按照权值大小做升序排序:
2) 从 B-D 边开始挑选,由于尚未选择任何边组成最小生成树,且 B-D 自身不会构成环路,所以 B-D 边可以组成最小生成树。
图 2 B-D 边组成最小生成树
3) D-T 边不会和已选 B-D 边构成环路,可以组成最小生成树:
图 3 D-T 边组成最小生成树
4) A-C 边不会和已选 B-D、D-T 边构成环路,可以组成最小生成树:
图 4 A-C 边组成最小生成树
5) C-D 边不会和已选 A-C、B-D、D-T 边构成环路,可以组成最小生成树:
图 5 C-D 边组成最小生成树
6) C-B 边会和已选 C-D、B-D 边构成环路,因此不能组成最小生成树:
图 6 C-B 边不能组成最小生成树
7) B-T 、A-B、S-A 三条边都会和已选 A-C、C-D、B-D、D-T 构成环路,都不能组成最小生成树。而 S-A 不会和已选边构成环路,可以组成最小生成树。
图 7 S-A 边组成最小生成树
8) 如图 7 所示,对于一个包含 6 个顶点的连通网,我们已经选择了 5 条边,这些边组成的生成树就是最小生成树。
图 8 最小生成树
思路
整个K算法中,其实简单的说就包含两个步骤:文章来源:https://www.toymoban.com/news/detail-773825.html
- 找出路径中最短的边;
- 看这个边会不会对现有的边形成环路,如果会就丢弃,如果不会就记录;
难点就是判断会不会有环,这里可以使用到并查集的思想去做,也可以直接使用一个集合,把所有的节点放入集合,如果下一次选中的边两个节点都在集合中可以被找到,那就说明会导致环路。文章来源地址https://www.toymoban.com/news/detail-773825.html
代码
#include <stdio.h>
#include <stdlib.h>
#define N 9 // 图中边的数量
#define P 6 // 图中顶点的数量
//构建表示边的结构体
struct edge {
//一条边有 2 个顶点
int initial;
int end;
//边的权值
int weight;
};
//qsort排序函数中使用,使edges结构体中的边按照权值大小升序排序
int cmp(const void* a, const void* b) {
return ((struct edge*)a)->weight - ((struct edge*)b)->weight;
}
//克鲁斯卡尔算法寻找最小生成树,edges 存储用户输入的图的各个边,minTree 用于记录组成最小生成树的各个边
void kruskal_MinTree(struct edge edges[], struct edge minTree[]) {
int i, initial, end, elem, k;
//每个顶点配置一个标记值
int assists[P];
int num = 0;
//初始状态下,每个顶点的标记都不相同
for (i = 0; i < P; i++) {
assists[i] = i;
}
//根据权值,对所有边进行升序排序
qsort(edges, N, sizeof(edges[0]), cmp);
//遍历所有的边
for (i = 0; i < N; i++) {
//找到当前边的两个顶点在 assists 数组中的位置下标
initial = edges[i].initial - 1;
end = edges[i].end - 1;
//如果顶点位置存在且顶点的标记不同,说明不在一个集合中,不会产生回路
if (assists[initial] != assists[end]) {
//记录该边,作为最小生成树的组成部分
minTree[num] = edges[i];
//计数+1
num++;
elem = assists[end];
//将新加入生成树的顶点标记全部改为一样的
for (k = 0; k < P; k++) {
if (assists[k] == elem) {
assists[k] = assists[initial];
}
}
//如果选择的边的数量和顶点数相差1,证明最小生成树已经形成,退出循环
if (num == P - 1) {
break;
}
}
}
}
void display(struct edge minTree[]) {
int cost = 0, i;
printf("最小生成树为:\n");
for (i = 0; i < P - 1; i++) {
printf("%d-%d 权值:%d\n", minTree[i].initial, minTree[i].end, minTree[i].weight);
cost += minTree[i].weight;
}
printf("总权值为:%d", cost);
}
int main() {
int i;
struct edge edges[N], minTree[P - 1];
for (i = 0; i < N; i++) {
scanf("%d %d %d", &edges[i].initial, &edges[i].end, &edges[i].weight);
}
kruskal_MinTree(edges, minTree);
display(minTree);
return 0;
}
到了这里,关于算法提升:图的最小生成树算法-克鲁斯卡尔(Kruskal)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!