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

破圈法是求解最小生成树的一种经典算法，下面是C语言实现的示例代码。

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

// 边的结构体
typedef struct Edge {
    int u, v;   // 两个端点
    int w;      // 权值
} Edge;

接着，我们需要编写一个比较函数来对边按权值从小到大进行排序：

// 比较函数
int cmp(const void* a, const void* b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

然后，我们可以使用Kruskal算法来找出最小生成树：

// 破圈法求解最小生成树
void break_circle(Edge edges[], int n, int m) {
    int i, j, k;
    int parent[n+1], rank[n+1]; // 并查集
    Edge tree[n]; // 最小生成树
    int cnt = 0; // 记录加入的边数
    int sum = 0; // 记录总权值

    // 初始化并查集
    for (i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    // 对边按权值从小到大排序
    qsort(edges, m, sizeof(Edge), cmp);

    // 构造最小生成树
    for (i = 0; i < m; i++) {
        // 判断是否在同一个集合中
        if (find(parent, edges[i].u) == find(parent, edges[i].v)) {
            continue;
        }

        // 加入边
        tree[cnt++] = edges[i];
        sum += edges[i].w;

        // 合并集合
        union_set(parent, rank, edges[i].u, edges[i].v);

        // 判断是否构成了环
        if (cnt == n - 1) {
            break;
        }
    }

    // 输出结果
    printf("最小生成树的边及其权值为：\n");
    for (i = 0; i < cnt; i++) {
        printf("(%d, %d) %d\n", tree[i].u, tree[i].v, tree[i].w);
    }
    printf("最小权值和为：%d\n", sum);
}

其中，我们使用了并查集来判断两个点是否在同一个集合中，也使用了一个 `cnt` 变量来记录加入的边数，当 `cnt == n - 1` 时，说明已经找到了最小生成树。

最后，我们需要编写并查集的 `find` 和 `union_set` 函数：

// 并查集的find操作
int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

// 并查集的union操作
void union_set(int parent[], int rank[], int x, int y) {
    int root_x = find(parent, x);
    int root_y = find(parent, y);
    if (rank[root_x] < rank[root_y]) {
        parent[root_x] = root_y;
    } else if (rank[root_x] > rank[root_y]) {
        parent[root_y] = root_x;
    } else {
        parent[root_y] = root_x;
        rank[root_x]++;
    }
}

这样，我们就完成了破圈法求解最小生成树的C语言实现。