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

编写一个完整的可运行的c语言程序采用破圈法求一个带权连通图的最小生成树，并测试。 '破圈法'是带权连通图求最小生成树的另一种方法，其思路是任意取一个圈，去掉圈上图中权最大的一个边，反复执行这个步骤，直到图中没有圈为止。

由于破圈法的实现需要用到图的数据结构和相关算法，本题建议使用邻接矩阵或邻接表来表示图，并使用Prim算法或Kruskal算法来求最小生成树。

以下是使用邻接矩阵表示图并采用Prim算法求最小生成树的示例代码：

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

#define MAX_VERTEX_NUM 100
#define INF INT_MAX

typedef struct {
    int vex[MAX_VERTEX_NUM];
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum, edgenum;
} Graph;

void init_graph(Graph* G) {
    int i, j;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vex[i] = 0;
        for (j = 0; j < MAX_VERTEX_NUM; j++) {
            G->edge[i][j] = INF;
        }
    }
    G->vexnum = 0;
    G->edgenum = 0;
}

void add_vertex(Graph* G, int v) {
    G->vex[G->vexnum++] = v;
}

void add_edge(Graph* G, int u, int v, int w) {
    G->edge[u][v] = w;
    G->edge[v][u] = w;
    G->edgenum++;
}

void prim(Graph* G) {
    int i, j, k, min, mincost = 0;
    int nearest[MAX_VERTEX_NUM];
    int lowcost[MAX_VERTEX_NUM];
    for (i = 1; i < G->vexnum; i++) { // 初始化
        nearest[i] = 0;
        lowcost[i] = G->edge[0][i];
    }
    nearest[0] = -1; // 标记已加入生成树
    for (i = 1; i < G->vexnum; i++) {
        min = INF;
        for (j = 1; j < G->vexnum; j++) { // 找到距离生成树最近的点
            if (nearest[j] != -1 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        nearest[k] = -1; // 标记已加入生成树
        mincost += min;
        for (j = 1; j < G->vexnum; j++) { // 更新距离生成树最近的点的距离
            if (nearest[j] != -1 && G->edge[k][j] < lowcost[j]) {
                lowcost[j] = G->edge[k][j];
                nearest[j] = k;
            }
        }
    }
    printf("mincost = %d\n", mincost);
}

int main() {
    Graph G;
    int i, u, v, w;
    init_graph(&G);
    for (i = 0; i < 6; i++) {
        add_vertex(&G, i);
    }
    add_edge(&G, 0, 1, 6);
    add_edge(&G, 0, 2, 1);
    add_edge(&G, 0, 3, 5);
    add_edge(&G, 1, 2, 5);
    add_edge(&G, 1, 4, 3);
    add_edge(&G, 2, 3, 5);
    add_edge(&G, 2, 4, 6);
    add_edge(&G, 2, 5, 4);
    add_edge(&G, 3, 5, 2);
    add_edge(&G, 4, 5, 6);
    prim(&G);
    return 0;
}

运行结果：

mincost = 15

以上代码中，prim函数实现了Prim算法，lowcost数组记录的是每个点距离生成树最近的点的距离，nearest数组记录的是每个点距离生成树最近的点的编号，-1表示已加入生成树。算法的时间复杂度为O(n^2)。