用C语言编写完整可运行的代码采用破圈法求一个带权连通图的最小生成树扩展目的：深入了解图的复杂操作、图遍历算法和最小生成树的概念以及最小生成树的构造运算。内容：编写一个程序采用破圈法求一个带权连通图的最小生成树并测试。破圈法是带权连通图求最小生成树的另一种方法其思路是任意取一个圈去掉圈上图中权最大的一个边反复执行这个步骤直到图中没有圈为止。

#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;
}
``