克鲁斯卡尔求最小生成树c语言

下面是使用 C 语言实现的克鲁斯卡尔算法求最小生成树的代码：

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

#define MAX_EDGE_NUM 100     // 边的最大数量
#define MAX_VERTEX_NUM 100   // 顶点的最大数量

typedef struct {
    int u, v;   // 边的两个端点
    int w;      // 边的权值
} edge;

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

int find(int x, int *p)
{
    if (p[x] != x) {
        p[x] = find(p[x], p);
    }
    return p[x];
}

void merge(int x, int y, int *p)
{
    int px = find(x, p);
    int py = find(y, p);
    if (px != py) {
        p[px] = py;
    }
}

void kruskal(edge *edges, int n, int m)
{
    int p[MAX_VERTEX_NUM], i, cnt = 0, sum = 0;
    for (i = 0; i < n; i++) {
        p[i] = i;
    }
    qsort(edges, m, sizeof(edge), cmp);
    for (i = 0; i < m && cnt < n - 1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        if (find(u, p) != find(v, p)) {
            merge(u, v, p);
            cnt++;
            sum += edges[i].w;
        }
    }
    printf("最小生成树的权值为 %d\n", sum);
}

int main()
{
    int n, m, i;
    edge edges[MAX_EDGE_NUM];
    printf("请输入顶点数量和边数量：");
    scanf("%d %d", &n, &m);
    printf("请输入每条边的起点、终点和权值：\n");
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }
    kruskal(edges, n, m);
    return 0;
}

在这个程序中，我们使用了结构体来表示一条边，包括其起点、终点和权值。我们还使用了并查集来判断加入一条边是否会形成环，以及将两个连通块合并。在最后的输出中，我们输出了最小生成树的权值。