最小生成树Kruskal算法，C语言实现

最小生成树Kruskal算法是一种用于求解无向图中最短路径的贪心算法，它通过不断合并边来构建一棵连通且权值之和最小的树。以下是C语言实现Kruskal算法的一个简单步骤：

1. **排序边**：首先对所有边按照权重从小到大排序。

2. **初始化并集**：将所有顶点视为独立的集合，可以用数组或哈希表表示每个顶点所属的集合。

3. **遍历边**：
- 检查当前边是否连接两个不同的集合（即它们的起始点和终点所在的集合不同）。
- 如果可以形成一条新的边且不会形成环路，则合并这两个集合，并记录下这条边。

4. **重复步骤3直到生成树包含n-1条边**：因为生成树需要覆盖n个顶点，所以最少需要n-1条边。

5. **结果**：最后剩下的树就是最小生成树。

下面是C语言的基本伪代码示例：

#include <stdio.h>
#include <stdlib.h>

// 结构体定义边
typedef struct Edge {
    int src, dest, weight;
} Edge;

// 并查集结构体
typedef struct UnionFind {
    int parent[vertices];
    int size[vertices];
} UF;

// 边比较函数
int compareEdges(Edge a, Edge b) {
    return a.weight < b.weight;
}

// Kruskal算法
void kruskal(int vertices, Edge edges[], int numEdges) {
    // 排序边
    qsort(edges, numEdges, sizeof(Edge), compareEdges);

    // 初始化并查集
    for (int i = 0; i < vertices; i++) {
        uf.parent[i] = i;
        uf.size[i] = 1;
    }

    int count = 0;
    while (count < vertices - 1) {
        Edge current = edges[count++]; // 取下一个最小的边

        if (!unionFind(current.src, current.dest, &uf)) { // 合并节点，如果没形成环则添加
            printf("Adding edge (%d, %d) with weight %d\n", current.src, current.dest, current.weight);
        }
    }
}

// 查找并返回集合根
int findSet(int v, UF *uf) {
    if (v != uf->parent[v]) {
        uf->parent[v] = findSet(uf->parent[v], uf);
    }
    return uf->parent[v];
}

// 判断并合并两个集合
int unionFind(int u, int v, UF *uf) {
    int rootU = findSet(u, uf);
    int rootV = findSet(v, uf);

    if (rootU == rootV) return 0; // 已经在同一个集合内，不需要合并

    if (uf->size[rootU] > uf->size[rootV]) {
        uf->parent[rootV] = rootU;
        uf->size[rootU] += uf->size[rootV];
    } else {
        uf->parent[rootU] = rootV;
        uf->size[rootV] += uf->size[rootU];
    }
    return 1;
}

int main() {
    // 输入数据...
    return 0;
}