反圈法求最小支撑树c语言

反圈法求最小支撑树是一种基于贪心策略的算法，可以用来求解带权无向图的最小生成树。具体步骤如下：

1. 将带权无向图的所有边按照权值从小到大排序。

2. 从权值最小的边开始，依次将每条边加入生成树中，如果此时形成了环，则将环上权值最大的边删除。直到生成树中包含了所有的节点。

以下是 C 语言实现代码：

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

#define MAXN 100005
#define INF 0x3f3f3f3f

struct Edge {
    int u;
    int v;
    int w;
} edges[MAXN];

int parent[MAXN];
int rank[MAXN];

int find(int x) {
    if (x != parent[x]) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void merge(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (rank[px] > rank[py]) {
        parent[py] = px;
    } else {
        parent[px] = py;
        if (rank[px] == rank[py]) {
            rank[py]++;
        }
    }
}

int cmp(const void *a, const void *b) {
    return ((struct Edge *)a)->w - ((struct Edge *)b)->w;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }
    // 按照权值从小到大排序
    qsort(edges, m, sizeof(struct Edge), cmp);
    // 初始化并查集
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
    // 依次将每条边加入生成树中
    int cnt = 0;
    int ans = 0;
    for (int i = 0; i < m && cnt < n - 1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;
        // 判断是否形成环
        if (find(u) != find(v)) {
            merge(u, v);
            ans += w;
            cnt++;
        }
    }
    printf("%d\n", ans);
    return 0;
}

其中，parent 数组表示节点的父节点，rank 数组表示节点的秩。find 函数和 merge 函数分别为并查集的查找和合并操作。cmp 函数是用来排序的比较函数。在主函数中，先读入图的节点数和边数，然后依次读入每条边的起点、终点和权值。接着对边按照权值从小到大排序，初始化并查集，然后依次将每条边加入生成树中，如果不形成环则将其加入生成树中，否则忽略该边。最后统计生成树的权值即为最小支撑树的权值。