克鲁斯卡尔算法求最小生成树：C语言实现

本文将使用 C 语言实现克鲁斯卡尔算法，用于求解无向图的最小生成树。

代码实现

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

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

// 边的结构体
typedef struct {
    int start; // 起点
    int end; // 终点
    int weight; // 权重
} Edge;

int parent[MAX_VERTEX_NUM]; // 存储每个节点的父节点
Edge edges[MAX_EDGE_NUM]; // 存储图的所有边
int edgeCount = 0; // 边的数量

// 查找节点的根节点
int find(int node) {
    while (parent[node] != -1) {
        node = parent[node];
    }
    return node;
}

// 合并两个节点所在的树
void unionSet(int root1, int root2) {
    parent[root1] = root2;
}

// 按权重从大到小排序
void sortEdges() {
    for (int i = 0; i < edgeCount - 1; i++) {
        for (int j = 0; j < edgeCount - i - 1; j++) {
            if (edges[j].weight < edges[j + 1].weight) {
                Edge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }
}

// 破圈法求最小生成树
void kruskal(int vertexCount) {
    for (int i = 0; i < vertexCount; i++) {
        parent[i] = -1; // 初始化每个节点的父节点为-1
    }

    sortEdges(); // 按边的权重从大到小排序

    int edgeIndex = 0; // 当前处理的边的索引
    int circleCount = vertexCount; // 圈的数量，初始值为顶点数

    while (circleCount > 1 && edgeIndex < edgeCount) { // 直到图中没有圈或者处理完所有边
        Edge edge = edges[edgeIndex++]; // 取出当前权重最大的边

        int root1 = find(edge.start);
        int root2 = find(edge.end);

        if (root1 != root2) { // 如果两个节点不在同一个圈中
            unionSet(root1, root2); // 合并两个圈
            circleCount--; // 圈的数量减1
            printf('(%d, %d) weight=%d\n', edge.start, edge.end, edge.weight); // 输出加入最小生成树的边
        }
    }
}

int main() {
    int vertexCount, edgeNum;
    printf("请输入顶点和边的数目:\n");
    scanf("%d%d", &vertexCount, &edgeNum);

    printf("请输入每条边的起始顶点、结束顶点和权值:\n");
    for (int i = 0; i < edgeNum; i++) {
        scanf("%d%d%d", &edges[i].start, &edges[i].end, &edges[i].weight);
        edgeCount++; // 边的数量加1
    }

    kruskal(vertexCount); // 使用破圈法求最小生成树

    return 0;
}

存储结构

使用邻接表存储图的结构；
使用数组存储边的信息；
使用数组存储每个节点的父节点。

基本运算

find(node)：查找节点的根节点；
unionSet(root1, root2)：合并两个节点所在的树；
sortEdges(): 按照边的权重从大到小排序；
kruskal(vertexCount)：使用破圈法求最小生成树。

模块构成

find(node)：查找节点的根节点；
unionSet(root1, root2)：合并两个节点所在的树；
sortEdges(): 按照边的权重从大到小排序；
kruskal(vertexCount)：使用破圈法求最小生成树；
main(): 程序入口，读取输入，调用 kruskal() 求解最小生成树。

各模块的简要说明

find(node)：从节点 node 开始，不断查找父节点，直到找到根节点，返回根节点的编号；
unionSet(root1, root2)：将根节点为 root1 的树和根节点为 root2 的树合并，即将 root1 的父节点设置为 root2；
sortEdges(): 使用冒泡排序，按照边的权重从大到小排序；
kruskal(vertexCount)：使用破圈法求解最小生成树，具体步骤如下：
- 初始化每个节点的父节点为 -1；
- 按照边的权重从大到小排序；
- 依次处理每条边，如果两个节点不在同一个圈中，则将它们合并，并将边加入最小生成树中；
- 直到图中没有圈或者处理完所有边。
main(): 读取输入，调用 kruskal() 求解最小生成树，并输出结果。

流程图

graph LR
    subgraph 初始化
        A[初始化每个节点的父节点为 -1]
        B[按照边的权重从大到小排序]
    end
    subgraph 循环
        C[设置 edgeIndex 为 0，circleCount 为顶点数]
        D{circleCount > 1 && edgeIndex < edgeCount}
        D --> E[取出当前权重最大的边]
        E --> F[root1 = find(edge.start)]
        F --> G[root2 = find(edge.end)]
        G --> H{root1 != root2}
        H -- YES --> I[合并两个圈]
        I --> J[circleCount--]
        I --> K[输出加入最小生成树的边]
        H -- NO --> L[edgeIndex++]
        L --> D
    end
    A --> C
    C --> D
    D --> end

调用关系表

| 调用者 | 被调用者 | | -------- | ----------------- | | main() | kruskal(vertexCount) | | kruskal() | find(node) | | kruskal() | unionSet(root1, root2) | | kruskal() | sortEdges() |