用c语言编写一个完整的可运行的代码采用破圈法求一个带权连通图的最小生成树输出边、权值以及删除的边破圈法是带权连通图求最小生成树的另一种方法其思路是任意取一个圈去掉圈上图中权最大的一个边反复执行这个步骤直到图中没有圈为止通过输入边顶点跟权值确定最小生成树

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

#define MAXVEX 100 // 最大顶点数
#define INFINITY 65535 // 无穷大

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

typedef struct {
    int vexs[MAXVEX]; // 顶点集合
    int arc[MAXVEX][MAXVEX]; // 邻接矩阵，表示边的权值
    int numVertexes; // 顶点数目
    int numEdges; // 边数目
} MGraph;

// 创建邻接矩阵
void CreateMGraph(MGraph *G) {
    int i, j, k, weight;
    printf("请输入顶点数目和边数目:\n");
    scanf("%d%d", &G->numVertexes, &G->numEdges);
    for (i = 0; i < G->numVertexes; i++) {
        printf("请输入第%d个顶点:\n", i+1);
        scanf("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->numVertexes; i++) {
        for (j = 0; j < G->numVertexes; j++) {
            G->arc[i][j] = INFINITY; // 初始化邻接矩阵
        }
    }
    for (k = 0; k < G->numEdges; k++) {
        printf("请输入边(vi, vj)的下标i, j和权值:\n");
        scanf("%d%d%d", &i, &j, &weight);
        G->arc[i][j] = weight;
        G->arc[j][i] = weight; // 无向图，矩阵对称
    }
}

// 打印邻接矩阵
void PrintMGraph(MGraph G) {
    int i, j;
    printf("邻接矩阵:\n");
    for (i = 0; i < G.numVertexes; i++) {
        for (j = 0; j < G.numVertexes; j++) {
            if (G.arc[i][j] == INFINITY) {
                printf("∞\t");
            } else {
                printf("%d\t", G.arc[i][j]);
            }
        }
        printf("\n");
    }
}

// 查找连通图的最小生成树
void MiniSpanTree_Prim(MGraph G, int start) {
    int i, j, k, min, sum = 0;
    int adjvex[MAXVEX]; // 保存相关顶点下标
    int lowcost[MAXVEX]; // 保存相关顶点间边的权值
    adjvex[start] = 0; // 第一个顶点下标为0
    lowcost[start] = 0; // 初始化第一个顶点的权值为0
    for (i = 1; i < G.numVertexes; i++) { // 循环除第一个顶点外的全部顶点
        lowcost[i] = G.arc[start][i]; // 将与start有边的顶点的权值存入数组
        adjvex[i] = start; // 初始化都为start的下标
    }
    for (i = 1; i < G.numVertexes; i++) {
        min = INFINITY; // 初始化最小值为无穷大
        j = 1; k = 0;
        while (j < G.numVertexes) { // 循环全部顶点
            if (lowcost[j] != 0 && lowcost[j] < min) { // 如果权值不为0且权值小于当前最小值
                min = lowcost[j]; // 将当前权值设为最小值
                k = j; // 将当前下标设为最小值下标
            }
            j++;
        }
        printf("(%d, %d)\n", adjvex[k], k); // 输出最小生成树的一条边
        sum += min; // 累加权值
        lowcost[k] = 0; // 将当前顶点的权值设为0，表示已经完成任务
        for (j = 1; j < G.numVertexes; j++) { // 循环所有顶点
            if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) { // 如果权值不为0且权值小于原来的权值
                lowcost[j] = G.arc[k][j]; // 将较小的权值存入lowcost
                adjvex[j] = k; // 将下标为k的顶点存入adjvex
            }
        }
    }
    printf("最小生成树的权值为:%d\n", sum);
}

// 查找连通图的最小生成树，采用破圈法
void MiniSpanTree_Kruskal(MGraph G) {
    int i, j, k, n, m, sum;
    int parent[MAXVEX]; // 用于存储每个顶点的父节点
    Edge edges[MAXVEX]; // 用于存储边
    for (i = 0; i < G.numVertexes; i++) {
        parent[i] = 0; // 初始化每个顶点的父节点为0
    }
    for (i = 0; i < G.numVertexes; i++) {
        for (j = i+1; j < G.numVertexes; j++) {
            if (G.arc[i][j] < INFINITY) { // 如果边存在
                edges[m].u = i; // 存储边的起点
                edges[m].v = j; // 存储边的终点
                edges[m].weight = G.arc[i][j]; // 存储边的权值
                m++; // 边数加1
            }
        }
    }
    for (i = 0; i < m; i++) { // 对所有边按权值从小到大排序
        for (j = i+1; j < m; j++) {
            if (edges[i].weight > edges[j].weight) {
                Edge temp = edges[i];
                edges[i] = edges[j];
                edges[j] = temp;
            }
        }
    }
    printf("最小生成树的边及权值为:\n");
    sum = 0; k = 0; n = 0;
    while (n < G.numVertexes-1) { // 循环直到生成树的边数为顶点数减1
        int u = edges[k].u; // 取出边的起点
        int v = edges[k].v; // 取出边的终点
        int w = edges[k].weight; // 取出边的权值
        int tu = parent[u]; // 找到起点的父节点
        int tv = parent[v]; // 找到终点的父节点
        if (tu != tv) { // 如果不在同一个集合
            printf("(%d, %d)\n", u, v); // 输出边
            n++; // 边数加1
            sum += w; // 累加权值
            parent[tu] = tv; // 将两个集合合并
        }
        k++; // 下一条边
    }
    printf("最小生成树的权值为:%d\n", sum);
}

int main() {
    MGraph G;
    int start;
    CreateMGraph(&G);
    PrintMGraph(G);
    printf("请输入起始顶点的下标:\n");
    scanf("%d", &start);
    printf("Prim算法求最小生成树:\n");
    MiniSpanTree_Prim(G, start);
    printf("Kruskal算法求最小生成树:\n");
    MiniSpanTree_Kruskal(G);
    return 0;
}
``