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

模型化描述

给定一个无向图，求其最小生成树。其中，图的顶点数为vertexCount，边数为edgeNum，每条边的起始顶点、结束顶点和权值分别为edges[i].start、edges[i].end和edges[i].weight。使用破圈法（Kruskal算法）求解。

求解算法简要描述

Kruskal算法是一种贪心算法，通过不断加入权值最小且不会形成环的边，逐步构建最小生成树。

具体步骤如下：

初始化每个节点的父节点为-1，圈的数量为顶点数。
将所有边按权重从大到小排序。
遍历每条边，如果两个节点不在同一个圈中，就合并两个圈，圈的数量减1，并将该边加入最小生成树。
重复步骤3直到图中没有圈或者处理完所有边。

最终得到的最小生成树即为所求。

代码实现

#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;
}

测试用例

请输入顶点和边的数目:
5 7
请输入每条边的起始顶点、结束顶点和权值:
0 1 2
0 2 6
0 3 4
1 2 3
1 4 5
2 3 7
3 4 8
(0, 1) weight=2
(1, 2) weight=3
(0, 3) weight=4
(1, 4) weight=5

总结

本文介绍了使用Kruskal算法求解无向图的最小生成树的思路和代码实现，并提供了测试用例。希望能够帮助读者更好地理解和应用该算法。