C语言实现带权连通图最小生成树 - 破圈法

'破圈法'是求带权连通图的最小生成树的一种方法，其思路是任意取一个圈，去掉圈上权最大的一个边，反复执行这个步骤，直到图中没有圈为止。

代码实现

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

#define MAX_VERTEX_NUM 100
#define MAX_EDGE_NUM 1000

typedef struct {
    int from;
    int to;
    int weight;
} Edge;  // 定义边

typedef struct {
    int vertex;
    int parent;
} UnionFind;  // 定义并查集结构体

void swap(Edge* a, Edge* b) {
    Edge temp = *a;
    *a = *b;
    *b = temp;
}

void sort(Edge edgeList[], int edgeNum) {
    for (int i = 0; i < edgeNum - 1; i++) {
        for (int j = i + 1; j < edgeNum; j++) {
            if (edgeList[i].weight > edgeList[j].weight) {
                swap(&edgeList[i], &edgeList[j]);
            }
        }
    }
}

int find(UnionFind ufSet[], int x) {
    int root = x;
    while (ufSet[root].parent >= 0) {
        root = ufSet[root].parent;
    }
    while (x != root) {
        int parent = ufSet[x].parent;
        ufSet[x].parent = root;
        x = parent;
    }
    return root;
}

void merge(UnionFind ufSet[], int x, int y) {
    int root1 = find(ufSet, x);
    int root2 = find(ufSet, y);
    if (ufSet[root1].parent < ufSet[root2].parent) {
        ufSet[root1].parent += ufSet[root2].parent;
        ufSet[root2].parent = root1;
    } else {
        ufSet[root2].parent += ufSet[root1].parent;
        ufSet[root1].parent = root2;
    }
}

void kruskal(Edge edgeList[], int edgeNum, int vertexNum) {
    UnionFind* ufSet = (UnionFind*)malloc(sizeof(UnionFind) * vertexNum);
    for (int i = 0; i < vertexNum; i++) {
        ufSet[i].vertex = i;
        ufSet[i].parent = -1;
    }
    int edgeCount = 0;
    int minWeightSum = 0;
    for (int i = 0; i < edgeNum; i++) {
        int from = edgeList[i].from;
        int to = edgeList[i].to;
        if (find(ufSet, from) != find(ufSet, to)) {
            merge(ufSet, from, to);
            edgeCount++;
            minWeightSum += edgeList[i].weight;
            if (edgeCount == vertexNum - 1) {
                break;
            }
        }
    }
    printf("Minimum weight sum: %d\n", minWeightSum);
    free(ufSet);
}

int main() {
    int vertexNum, edgeNum;
    printf("Please enter the number of vertices and edges: ");
    scanf("%d %d", &vertexNum, &edgeNum);
    Edge* edgeList = (Edge*)malloc(sizeof(Edge) * edgeNum);
    printf("Please enter the edges and weights:\n");
    for (int i = 0; i < edgeNum; i++) {
        scanf("%d %d %d", &edgeList[i].from, &edgeList[i].to, &edgeList[i].weight);
    }
    sort(edgeList, edgeNum);
    kruskal(edgeList, edgeNum, vertexNum);
    free(edgeList);
    return 0;
}

代码说明

1. 数据结构定义

   • Edge 结构体表示图中的边，包含边的起点 (from)、终点 (to) 和权值 (weight)。
   • UnionFind 结构体表示并查集中的节点，包含节点编号 (vertex) 和父节点编号 (parent)。

2. 函数说明

   • swap 函数：交换两个 Edge 结构体。
   • sort 函数：对边列表进行排序，从小到大排序权值。
   • find 函数：查找并查集中节点的根节点。
   • merge 函数：合并并查集中两个集合。
   • kruskal 函数：使用 Kruskal 算法求最小生成树，并输出最小生成树的总权值。
   • main 函数：输入顶点数、边数和权值，调用 kruskal 函数求解最小生成树。

使用方法

1. 编译并运行代码。
2. 输入顶点数、边数和权值，以空格隔开。
3. 输出最小生成树的总权值。

示例

输入：

4 5
0 1 1
0 2 3
1 2 2
1 3 4
2 3 5

输出：

Minimum weight sum: 6

总结

本代码实现了求带权连通图的最小生成树算法，使用破圈法，可以帮助理解最小生成树算法的原理和实现。