在图论中，最小生成树是一个经典问题，它要求在给定的连通图中找到一棵包含所有顶点的树，使得这棵树的边的权值之和最小。常用的求解最小生成树的算法有Kruskal算法和Prim算法。这两种算法都是基于贪心策略的。
一、Kruskal算法
Kruskal算法的基本思想是从所有的边中选取权值最小的边，如果这条边不会与已经选取的边形成环，就将其加入到最小生成树中。重复这个过程直到选取了n-1条边，其中n是顶点的数量。
以下是Kruskal算法的C语言实现：
```c

include

include

define MAX_VERTICES 1000 // 最大顶点数

define INF 0x3f3f3f3f // 无穷大

typedef struct Edge {
int src, dest, weight;
struct Edge next;
} Edge;
int parent[MAX_VERTICES]; // 并查集数组
int rank[MAX_VERTICES]; // 并查集秩数组
Edge edges[MAX_VERTICES]; // 边的数组
int num_edges, num_vertices; // 边的数量和顶点的数量
// 并查集初始化
void init_union_find(int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// 查找元素所属的集合
int find_union_find(int x) {
if (parent[x] != x) {
parent[x] = find_union_find(parent[x]);
}
return parent[x];
}
// 合并两个集合
void union_union_find(int x, int y) {
int root_x = find_union_find(x);
int root_y = find_union_find(y);
if (root_x != root_y) {
if (rank[root_x] < rank[root_y]) {
parent[root_x] = root_y;
} else if (rank[root_x] > rank[root_y]) {
parent[root_y] = root_x;
} else {
parent[root_x] = root_y;
rank[root_y]++;
}
}
}
// Kruskal算法实现
void kruskal(int n) {
int cost, min_cost;
Edge *e;
init_union_find(n); // 初始化并查集数组和秩数组
for (int i = 0; i < num_edges; i++) { // 遍历所有边
e = edges[i];
cost = e->weight; // 边的权值保存在结构体中，此处取出来作为cost变量使用
min_cost = INF; // 初始化最小权值为无穷大，用于与当前权值进行比较并更新最小权值。
for (int j = 0; j < num_vertices; j++) { // 检查选取的边是否会与已选取的边形成环
if (find_union_find(e->src) != find_union_find(e->dest)) { // 如果选取的边连接的两个顶点属于不同的集合，说明这条边不会与已选取的边形成环。此时计算这条边的权值是否小于当前的最小权值。如果小于当前的最小权值，则更新最小权值。如果等于当前的最小权值，则进行下一步合并操作。如果大于当前的最小权值，则无需进行任何操作。最后将这条边加入到最小生成树中。完成添加一条边的操作后，将这条边的两个顶点合并到同一个集合中。此时需要检查合并操作是否会引起环的出现。如果会引起环的出现，则说明选取的边是无效的，需要继续遍历下一条边。如果不会引起环的出现，则说明选取的边是有效的，需要继续进行添加操作。直到添加了n-