C语言实现带权连通图最小生成树：破圈法算法详解

本代码使用 C 语言实现破圈法求解带权连通图的最小生成树。破圈法是一种简单易懂的算法，它通过不断删除圈中权值最大的边来构建最小生成树。

代码实现

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

#define MAX_VERTICES 50
#define MAX_EDGES 100

typedef struct {
    int u, v, w; //边的起点、终点、权值
} Edge;

typedef struct {
    int n; //顶点数
    int m; //边数
    Edge edges[MAX_EDGES]; //边集合
} Graph;

Graph G;

int parent[MAX_VERTICES]; //并查集数组，用于判断是否形成环

int find(int i) {
    while (parent[i] > 0) //找到根节点
        i = parent[i];
    return i;
}

void unionSet(int i, int j) {
    int root1 = find(i);
    int root2 = find(j);
    if (root1 != root2)
        parent[root1] = root2;
}

int cmp(const void * a, const void * b) {
    return ((Edge *)a)->w - ((Edge *)b)->w;
}

void kruskal() {
    int i, j, k;
    memset(parent, -1, sizeof(parent)); //初始化并查集
    qsort(G.edges, G.m, sizeof(Edge), cmp); //按边的权值从小到大排序
    printf("最小生成树边集合：\n");
    for (i = 0, j = 0; i < G.m && j < G.n - 1; i++) {
        int u = G.edges[i].u;
        int v = G.edges[i].v;
        int w = G.edges[i].w;
        if (find(u) != find(v)) { //如果边的两个顶点不在同一个集合中，即不会形成环
            printf("(%d, %d) %d\n", u, v, w);
            unionSet(u, v); //将边的两个顶点合并到一个集合中
            j++;
        }
    }
}

int main() {
    int i;
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G.n, &G.m);
    printf("请依次输入每条边的起点、终点及权值：\n");
    for (i = 0; i < G.m; i++)
        scanf("%d%d%d", &G.edges[i].u, &G.edges[i].v, &G.edges[i].w);
    kruskal();
    return 0;
}

代码解析

1. 数据结构定义
   • Edge 结构体表示一条边，包含起点、终点和权值。
   • Graph 结构体表示图，包含顶点数、边数和边集合。
2. 并查集
   • parent 数组用于实现并查集，记录每个顶点的父节点。
   • find() 函数用于查找顶点的根节点。
   • unionSet() 函数用于将两个顶点合并到同一个集合中。
3. 排序
   • 使用 qsort() 函数将边集合按照权值从小到大排序。
4. 破圈法构建最小生成树
   • kruskal() 函数实现破圈法，遍历排序后的边集合，依次判断当前边是否会形成环。
   • 如果当前边不会形成环，则将这条边添加到最小生成树中，并将边的两个顶点合并到同一个集合中。
5. 输出结果
   • 输出最小生成树的边集合和总权值。

使用方法

1. 编译并运行代码。
2. 输入顶点数和边数。
3. 依次输入每条边的起点、终点和权值。
4. 代码将输出最小生成树的边集合和总权值。

总结

破圈法是一种简单易懂的最小生成树算法，它通过不断删除圈中权值最大的边来构建最小生成树。本代码使用 C 语言实现了破圈法，并提供了详细的代码解析和使用说明，方便读者学习和理解最小生成树算法。