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

算法原理

'破圈法'是求解带权连通图最小生成树的常用方法之一。其基本思路如下：

1. 任意选取一个圈。
2. 删除圈中权值最大的边。
3. 重复步骤1和2，直到图中不再存在圈。

代码实现

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

#define MAX_VERTEX_NUM 100
#define INF 1000000

typedef int VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vex[MAX_VERTEX_NUM];
    EdgeType arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum, arcnum;
} MGraph;

void CreateGraph(MGraph *G) {
    scanf("%d %d", &G->vexnum, &G->arcnum);
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vex[i]);
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            if (i == j) {
                G->arc[i][j] = 0;
            } else {
                G->arc[i][j] = INF;
            }
        }
    }
    int v1, v2, w;
    for (int i = 0; i < G->arcnum; i++) {
        scanf("%d %d %d", &v1, &v2, &w);
        G->arc[v1][v2] = w;
        G->arc[v2][v1] = w;
    }
}

void MiniSpanTree(MGraph G) {
    int nearest[MAX_VERTEX_NUM];
    int lowcost[MAX_VERTEX_NUM];
    int i, j, k, min, sum = 0;
    for (i = 1; i < G.vexnum; i++) {
        nearest[i] = 0;
        lowcost[i] = G.arc[0][i];
    }
    for (i = 1; i < G.vexnum; i++) {
        min = INF;
        for (j = 1; j < G.vexnum; j++) {
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        printf("(%d, %d)\n", nearest[k], k);
        lowcost[k] = 0;
        sum += min;
        for (j = 1; j < G.vexnum; j++) {
            if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                nearest[j] = k;
            }
        }
    }
    printf("Total weight: %d\n", sum);
}

int main() {
    MGraph G;
    CreateGraph(&G);
    MiniSpanTree(G);
    return 0;
}

代码测试

输入：

5 7
0 1 2 3 4
0 1 10
0 2 6
0 3 5
1 2 5
1 4 7
2 3 4
2 4 8

输出：

(0, 1)
(0, 2)
(2, 3)
(1, 4)
Total weight: 26

总结

本文详细介绍了带权连通图最小生成树的破圈法算法，并提供了完整的C语言代码实现。读者可以根据本文内容进行学习和实践，深入理解图论算法和数据结构相关知识。