目录

概念

思路

代码

概念

克鲁斯卡尔算法查找最小生成树的方法是：将连通网中所有的边按照权值大小做升序排序，从权值最小的边开始选择，只要此边不和已选择的边一起构成环路，就可以选择它组成最小生成树。对于 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算法中，其实简单的说就包含两个步骤：

1. 找出路径中最短的边；
2. 看这个边会不会对现有的边形成环路，如果会就丢弃，如果不会就记录；

难点就是判断会不会有环，这里可以使用到并查集的思想去做，也可以直接使用一个集合，把所有的节点放入集合，如果下一次选中的边两个节点都在集合中可以被找到，那就说明会导致环路。

代码

#include 
#include 
#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];//计数+1num++;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;
}