c语言实现 城市燃气管道铺设的问题 实践用并查集实现Kruskal算法

实现城市燃气管道铺设的问题，可以考虑使用Kruskal算法，该算法可以得到最小生成树，即最小的管道铺设方案。

并查集是Kruskal算法的一个重要组成部分，用于检查新加入的边是否形成环路。下面是C语言实现Kruskal算法的示例代码，其中用到了并查集的数据结构。

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

#define MAX_VERTEX_NUM 20

// 定义边的结构体
typedef struct {
    int u; // 起点
    int v; // 终点
    int w; // 权值
} Edge;

// 定义并查集结构体
typedef struct {
    int parent[MAX_VERTEX_NUM];
    int rank[MAX_VERTEX_NUM];
} UnionFind;

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

// 查找根节点
int findRoot(UnionFind *uf, int x) {
    if (uf->parent[x] == x) {
        return x;
    } else {
        int root = findRoot(uf, uf->parent[x]);
        uf->parent[x] = root;
        return root;
    }
}

// 合并两个集合
void unionSet(UnionFind *uf, int x, int y) {
    int rootX = findRoot(uf, x);
    int rootY = findRoot(uf, y);
    if (rootX != rootY) {
        if (uf->rank[rootX] > uf->rank[rootY]) {
            uf->parent[rootY] = rootX;
        } else if (uf->rank[rootX] < uf->rank[rootY]) {
            uf->parent[rootX] = rootY;
        } else {
            uf->parent[rootY] = rootX;
            uf->rank[rootX]++;
        }
    }
}

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

// Kruskal算法
void kruskal(Edge edges[], int n, int m) {
    UnionFind uf;
    makeSet(&uf, n);

    qsort(edges, m, sizeof(Edge), cmp);

    int count = 0;
    int sum = 0;
    for (int i = 0; i < m; i++) {
        int rootU = findRoot(&uf, edges[i].u);
        int rootV = findRoot(&uf, edges[i].v);
        if (rootU != rootV) {
            unionSet(&uf, rootU, rootV);
            printf("%d -> %d : %d\n", edges[i].u, edges[i].v, edges[i].w);
            sum += edges[i].w;
            count++;
        }
        if (count == n - 1) {
            break;
        }
    }

    printf("Total cost: %d\n", sum);
}

// 测试
int main() {
    int n = 6, m = 10;
    Edge edges[] = {
        {0, 1, 6},
        {0, 2, 1},
        {0, 3, 5},
        {1, 2, 5},
        {1, 4, 3},
        {2, 3, 5},
        {2, 4, 6},
        {2, 5, 4},
        {3, 5, 2},
        {4, 5, 6},
    };
    kruskal(edges, n, m);
    return 0;
}

以上代码中，我们将边按权值从小到大排序，然后遍历每条边，如果该边的起点和终点不在同一个集合中，则将它们合并，并输出该边的信息及权值。最后输出总的铺设成本。