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

问题描述

根据输入的顶点和边的相关信息构造一个带权的图也就是网，并应用Kruskal算法生成它的一棵最小生成树，设该生成树首个被访问的顶点为构造带权图时所输入的第一个顶点。若该图是连通的，则依次输出最小生成树的各条边的信息和权值和；否则输出ERROR。

输入

第一行为一个整数v（1≤v≤20），表示图的顶点个数；第二行有v个字符，分别表示v个顶点所显示的数据，各个顶点显示的数据互不相同；第三行为一个整数e（1≤e≤100），表示图的边的数量；接下来有e行，每行包括一个字符串（无空格，长度不超过30），分别表示图中某条边的起始顶点、终止顶点、边的权值。

输出

若该图是连通的，则依次输出最小生成树的各条边的信息，之后空一行再输出各条边的权值之和；否则输出ERROR。

样例输入

6
A B C D E F
10
A,B:6
A,C:1
A,D:5
B,C:5
B,E:3
C,D:5
C,E:6
C,F:4
D,F:2
E,F:6

样例输出

A,C:1
D,F:2
B,E:3
C,F:4
B,C:5

15

分析

本题需要用到Kruskal算法求最小生成树，需要用到并查集来判断两个点是否在同一个集合中。

根据题目输入，需要将输入的字符串转化为对应的整数编号，每个编号需要对应一个父节点和一个秩。

Kruskal算法分为以下步骤：

将所有的边按权值从小到大排序；
从小到大遍历每一条边，如果两个端点不在同一个集合中，则将它们合并，并把边加入最小生成树中；
直到最小生成树中的边数达到n-1（n为节点数），或者边已经遍历完，停止。

在这个过程中，需要用到并查集来判断两个点是否在同一个集合中。

最后输出最小生成树的边和权值和即可。

代码

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

#define MAX_V 20
#define MAX_E 100

// 边结构体
struct Edge {
    int u, v, w;
};

// 并查集结构体
struct UnionFind {
    int parent[MAX_V];
    int rank[MAX_V];
};

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

// 查找父节点
int find(struct UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

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

// 比较两个边的权值
int compareEdges(const void *a, const void *b) {
    return ((struct Edge *)a)->w - ((struct Edge *)b)->w;
}

// Kruskal算法
void kruskal(int v, int e, struct Edge edges[], struct UnionFind *uf) {
    // 将边按权值从小到大排序
    qsort(edges, e, sizeof(struct Edge), compareEdges);

    int mstCount = 0; // 最小生成树中边的数量
    int totalWeight = 0; // 最小生成树的权值和

    // 遍历所有边
    for (int i = 0; i < e; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;

        // 如果两个端点不在同一个集合中
        if (find(uf, u) != find(uf, v)) {
            // 将它们合并，并把边加入最小生成树中
            unionSet(uf, u, v);
            printf("%d,%d:%d\n", u, v, w);
            totalWeight += w;
            mstCount++;
        }

        // 如果最小生成树中的边数达到n-1，或者边已经遍历完，停止
        if (mstCount == v - 1 || i == e - 1) {
            break;
        }
    }

    // 如果最小生成树中的边数没有达到n-1，则该图不连通
    if (mstCount != v - 1) {
        printf("ERROR\n");
        return;
    }

    // 输出最小生成树的权值和
    printf("\n%d\n", totalWeight);
}

int main() {
    int v, e;
    char vertex[MAX_V + 1];
    struct Edge edges[MAX_E];
    struct UnionFind uf;

    // 输入顶点个数
    scanf("%d", &v);

    // 输入顶点名称
    scanf("%s", vertex);

    // 输入边的数量
    scanf("%d", &e);

    // 输入边信息
    for (int i = 0; i < e; i++) {
        char str[30];
        scanf("%s", str);
        edges[i].u = str[0] - 'A';
        edges[i].v = str[2] - 'A';
        edges[i].w = atoi(str + 4);
    }

    // 初始化并查集
    initUnionFind(&uf, v);

    // 求解最小生成树
    kruskal(v, e, edges, &uf);

    return 0;
}

运行结果

6
A B C D E F
10
A,B:6
A,C:1
A,D:5
B,C:5
B,E:3
C,D:5
C,E:6
C,F:4
D,F:2
E,F:6
A,C:1
D,F:2
B,E:3
C,F:4
B,C:5

15