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

由于本题需要实现图的相关操作，需要使用图的数据结构来存储图，这里采用邻接矩阵来表示带权连通图。

首先，我们需要定义一个结构体来表示带权边：

typedef struct {
    int start; // 起点
    int end; // 终点
    int weight; // 权重
} Edge;

然后，我们定义一个图的结构体，包含图的邻接矩阵和顶点个数：

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct {
    int vertexNum; // 顶点个数
    int edgeNum; // 边个数
    int adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
} Graph;

接下来，我们需要实现读入图的函数，根据输入的顶点个数和边个数，构造邻接矩阵：

void readGraph(Graph* graph) {
    scanf("%d%d", &graph->vertexNum, &graph->edgeNum);
    int i, j;
    for (i = 0; i < graph->vertexNum; i++) {
        for (j = 0; j < graph->vertexNum; j++) {
            graph->adjMatrix[i][j] = 0; // 初始化为0，表示没有边
        }
    }
    int start, end, weight;
    for (i = 0; i < graph->edgeNum; i++) {
        scanf("%d%d%d", &start, &end, &weight);
        graph->adjMatrix[start][end] = weight;
        graph->adjMatrix[end][start] = weight; // 无向图需要同时设置两个方向的权值
    }
}

然后，我们需要实现破圈法求最小生成树的函数，首先需要实现找圈的函数：

int findCycle(Graph* graph, int* p, int* q) {
    int i, j, k;
    for (i = 0; i < graph->vertexNum; i++) {
        for (j = i + 1; j < graph->vertexNum; j++) {
            if (graph->adjMatrix[i][j] != 0) { // 如果有边
                int flag = 0;
                for (k = 0; k < graph->vertexNum; k++) {
                    if (k != i && k != j && graph->adjMatrix[i][k] != 0 && graph->adjMatrix[j][k] != 0) { // 如果存在三角形
                        if (graph->adjMatrix[i][j] > graph->adjMatrix[i][k] && graph->adjMatrix[i][j] > graph->adjMatrix[j][k]) { // 如果(i,j)是最大边
                            *p = i;
                            *q = j;
                            return 1;
                        }
                        flag = 1;
                    }
                }
                if (flag == 0) { // 如果不存在三角形
                    if (graph->adjMatrix[i][j] > graph->adjMatrix[i][*p] && graph->adjMatrix[i][j] > graph->adjMatrix[j][*p]) { // 如果(i,j)是最大边
                        *p = i;
                        *q = j;
                    }
                }
            }
        }
    }
    return 0;
}

该函数通过枚举所有可能的边，找到一个圈，并返回圈上权值最大的边的起点和终点。

接下来，我们需要实现破圈操作，即去掉圈上权值最大的边：

void breakCycle(Graph* graph, int p, int q) {
    int i, j, k;
    for (i = 0; i < graph->vertexNum; i++) {
        for (j = 0; j < graph->vertexNum; j++) {
            if (graph->adjMatrix[i][j] != 0) { // 如果有边
                if ((i == p && j == q) || (i == q && j == p)) { // 如果是圈上的边
                    graph->adjMatrix[i][j] = 0; // 去掉这条边
                    graph->adjMatrix[j][i] = 0;
                }
            }
        }
    }
}

最后，我们需要实现破圈法求最小生成树的函数：

void minSpanningTree(Graph* graph) {
    int p, q;
    while (findCycle(graph, &p, &q)) { // 只要还存在圈
        breakCycle(graph, p, q); // 去掉圈上权值最大的边
    }
}

该函数不断寻找圈并去掉圈上权值最大的边，直到图中不存在圈为止，此时图的最小生成树就被构造出来了。

最后，我们需要实现主函数，读入图并求解最小生成树：

int main() {
    Graph graph;
    readGraph(&graph);
    minSpanningTree(&graph);
    // 输出最小生成树的邻接矩阵
    int i, j;
    for (i = 0; i < graph.vertexNum; i++) {
        for (j = 0; j < graph.vertexNum; j++) {
            printf("%d ", graph.adjMatrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}

完整代码如下