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

本文将使用 C 语言实现 Kruskal 算法，并提供代码、存储结构、基本运算、模块构成、流程图和调用关系表，帮助您理解 Kruskal 算法的原理和实现。

代码实现

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

#define MAX_VERTEX_NUM 100 //最大顶点数
#define MAX_EDGE_NUM 100 //最大边数

//边结构体
typedef struct {
    int tail; //边的起点
    int head; //边的终点
    int weight; //边的权值
} Edge;

//图结构体
typedef struct {
    int vertexNum; //顶点数
    int edgeNum; //边数
    Edge edges[MAX_EDGE_NUM]; //边数组
} Graph;

//并查集结构体
typedef struct {
    int parent[MAX_VERTEX_NUM]; //父节点数组
    int rank[MAX_VERTEX_NUM]; //秩数组
} UnionFindSet;

//初始化并查集
void MakeSet(UnionFindSet *set, int n) {
    for (int i = 0; i < n; i++) {
        set->parent[i] = i;
        set->rank[i] = 0;
    }
}

//查找节点所在集合的代表元
int Find(UnionFindSet *set, int x) {
    if (set->parent[x] != x) {
        set->parent[x] = Find(set, set->parent[x]);
    }
    return set->parent[x];
}

//合并两个集合
void Union(UnionFindSet *set, int x, int y) {
    int xRoot = Find(set, x);
    int yRoot = Find(set, y);
    if (xRoot == yRoot) {
        return;
    }
    if (set->rank[xRoot] < set->rank[yRoot]) {
        set->parent[xRoot] = yRoot;
    } else if (set->rank[xRoot] > set->rank[yRoot]) {
        set->parent[yRoot] = xRoot;
    } else {
        set->parent[yRoot] = xRoot;
        set->rank[xRoot]++;
    }
}

//边比较函数，用于排序
int cmp(const void *a, const void *b) {
    Edge *e1 = (Edge *)a;
    Edge *e2 = (Edge *)b;
    return e1->weight - e2->weight;
}

//破圈法求最小生成树
void Kruskal(Graph *graph) {
    //按权值从小到大排序
    qsort(graph->edges, graph->edgeNum, sizeof(Edge), cmp);
    //初始化并查集
    UnionFindSet set;
    MakeSet(&set, graph->vertexNum);
    //记录删除的边
    Edge removedEdges[MAX_EDGE_NUM];
    int removedEdgeNum = 0;
    //遍历所有边
    for (int i = 0; i < graph->edgeNum; i++) {
        Edge e = graph->edges[i];
        //如果边的两个端点不在同一个集合中，说明不会形成环，可以加入最小生成树中
        if (Find(&set, e.tail) != Find(&set, e.head)) {
            Union(&set, e.tail, e.head);
            printf('边 (%d, %d) 权值为 %d 加入最小生成树\n', e.tail, e.head, e.weight);
        } else {
            //否则，删除边
            removedEdges[removedEdgeNum++] = e;
        }
    }
    //输出删除的边
    printf('删除的边：\n');
    for (int i = 0; i < removedEdgeNum; i++) {
        Edge e = removedEdges[i];
        printf('(%d, %d) 权值为 %d\n', e.tail, e.head, e.weight);
    }
}

int main() {
    int n, m; //顶点数和边数
    Graph graph;
    printf('请输入顶点数和边数：');
    scanf('%d %d', &n, &m);
    graph.vertexNum = n;
    graph.edgeNum = m;
    printf('请输入每条边的起点、终点和权值：\n');
    for (int i = 0; i < m; i++) {
        Edge e;
        scanf('%d %d %d', &e.tail, &e.head, &e.weight);
        graph.edges[i] = e;
    }
    Kruskal(&graph);
    return 0;
}

存储结构

边结构体: 包括边的起点 tail、终点 head 和权值 weight。
图结构体: 包括顶点数 vertexNum、边数 edgeNum 和边数组 edges。
并查集结构体: 包括父节点数组 parent 和秩数组 rank。

基本运算

初始化并查集: MakeSet(set, n)，将每个节点的父节点设为自身，秩设为0。
查找节点所在集合的代表元: Find(set, x)，递归查找父节点，直到找到根节点。
合并两个集合: Union(set, x, y)，先找到两个节点所在集合的代表元，再根据秩的大小合并两个集合。

模块构成

初始化并查集模块: MakeSet(set, n)。
查找集合代表元模块: Find(set, x)。
合并集合模块: Union(set, x, y)。
边比较函数模块: cmp(a, b)，用于边的排序。
破圈法求最小生成树模块: Kruskal(graph)，按权值从小到大排序，遍历所有边，如果边的两个端点不在同一个集合中，说明不会形成环，可以加入最小生成树中，否则，删除边。

各模块简要说明

初始化并查集模块: 将每个节点的父节点设为自身，秩设为0。
查找集合代表元模块: 递归查找父节点，直到找到根节点，同时进行路径压缩，即将路径上的所有节点的父节点设为根节点。
合并集合模块: 先找到两个节点所在集合的代表元，再根据秩的大小合并两个集合，将秩小的集合合并到秩大的集合中，如果秩相等，则将一个集合的根节点作为另一个集合的子节点，同时将秩加1。
边比较函数模块: 用于边的排序，按权值从小到大排序。
破圈法求最小生成树模块: 按权值从小到大排序，遍历所有边，如果边的两个端点不在同一个集合中，说明不会形成环，可以加入最小生成树中，否则，删除边。

流程图

Kruskal流程图

调用关系表

| 模块 | 调用者 | | ---------------------- | --------------- | | 初始化并查集模块 | Kruskal | | 查找集合代表元模块 | Kruskal, Union | | 合并集合模块 | Kruskal, Union | | 边比较函数模块 | Kruskal | | 破圈法求最小生成树模块 | main, Kruskal | | main | 无调用者 | | Kruskal | main | | UnionFindSet | MakeSet, Find, Union |

其中，UnionFindSet 为并查集结构体。

总结

本文详细介绍了 Kruskal 算法的 C 语言实现，包括代码、存储结构、基本运算、模块构成、流程图和调用关系表，希望能够帮助您更好地理解 Kruskal 算法的原理和实现。