破圈法求解最小生成树c语言实现（已验证）

破圈法求解最小生成树的C语言实现大致如下：

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

// 定义图的最大节点数
#define MAX_VERTICES 100

// 定义图的邻接矩阵
int graph[MAX_VERTICES][MAX_VERTICES];

// 定义边结构体
struct Edge {
    int src, dest, weight;
};

// 定义图的边集合数组
struct Edge edges[MAX_VERTICES * MAX_VERTICES];

// 定义边集合的大小
int numEdges = 0;

// 添加一条边到边集合
void addEdge(int src, int dest, int weight) {
    edges[numEdges].src = src;
    edges[numEdges].dest = dest;
    edges[numEdges].weight = weight;
    numEdges++;
}

// 从边集合中获取权值最小的边
struct Edge getMinEdge() {
    int minWeight = INT_MAX;
    int minIndex = -1;
    for (int i = 0; i < numEdges; i++) {
        if (edges[i].weight < minWeight) {
            minWeight = edges[i].weight;
            minIndex = i;
        }
    }
    return edges[minIndex];
}

// 判断两个节点是否在同一圈中
int isInSameCircle(int parent[], int x, int y) {
    return parent[x] == parent[y];
}

// 合并两个节点所在的圈
void mergeCircles(int parent[], int x, int y) {
    int xParent = parent[x];
    int yParent = parent[y];
    for (int i = 0; i < MAX_VERTICES; i++) {
        if (parent[i] == yParent) {
            parent[i] = xParent;
        }
    }
}

// 破圈法求解最小生成树
void kruskalMST(int numVertices) {
    int parent[MAX_VERTICES];
    for (int i = 0; i < numVertices; i++) {
        parent[i] = i;
    }
    int numEdgesInMST = 0;
    while (numEdgesInMST < numVertices - 1) {
        struct Edge minEdge = getMinEdge();
        int src = minEdge.src;
        int dest = minEdge.dest;
        if (!isInSameCircle(parent, src, dest)) {
            printf("%d - %d\n", src, dest);
            mergeCircles(parent, src, dest);
            numEdgesInMST++;
        }
    }
}

int main() {
    // 初始化图的邻接矩阵
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;
        }
    }

    // 添加边到邻接矩阵和边集合中
    addEdge(0, 1, 4);
    addEdge(0, 7, 8);
    addEdge(1, 2, 8);
    addEdge(1, 7, 11);
    addEdge(2, 3, 7);
    addEdge(2, 8, 2);
    addEdge(2, 5, 4);
    addEdge(3, 4, 9);
    addEdge(3, 5, 14);
    addEdge(4, 5, 10);
    addEdge(5, 6, 2);
    addEdge(6, 7, 1);
    addEdge(6, 8, 6);
    addEdge(7, 8, 7);

    // 执行破圈法求解最小生成树
    kruskalMST(9);

    return 0;
}

其中，`addEdge` 函数用于将一条边添加到邻接矩阵和边集合中；`getMinEdge` 函数用于从边集合中获取权值最小的边；`isInSameCircle` 函数用于判断两个节点是否在同一圈中；`mergeCircles` 函数用于合并两个节点所在的圈；`kruskalMST` 函数用于执行破圈法求解最小生成树。在 `main` 函数中，我们先将边添加到邻接矩阵和边集合中，然后执行破圈法求解最小生成树。