克鲁斯卡尔算法 c语言

克鲁斯卡尔算法是一种用于求解最小生成树的算法，其基本思想是通过不断地选择边，将图中所有节点连接起来，并且保证边的权值之和最小。下面是使用 C 语言实现的基本代码：

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

#define MAX 1000 // 最大节点数
#define INF 0x3f3f3f3f // 无穷大

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

int n, m; // 节点数和边数
Edge edges[MAX]; // 边集合
int parent[MAX]; // 节点的父节点

int find(int x) { // 查找节点 x 的根节点
    while (x != parent[x]) {
        parent[x] = parent[parent[x]]; // 路径压缩
        x = parent[x];
    }
    return x;
}

void kruskal() {
    int cnt = 0, ans = 0; // 已选边数和答案
    for (int i = 1; i <= n; i++) parent[i] = i; // 初始化每个节点的父节点
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        int pu = find(u), pv = find(v); // 找到两个端点的根节点
        if (pu != pv) { // 如果两个端点不连通
            parent[pu] = pv; // 将两个端点的根节点合并
            cnt++; // 已选边数加 1
            ans += w; // 答案加上此边的权值
            if (cnt == n - 1) break; // 已经选了 n-1 条边，得到最小生成树
        }
    }
    printf("%d\n", ans); // 输出最小生成树的权值之和
}

int main() {
    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);
    }
    kruskal();
    return 0;
}

在该算法中，我们需要先输入节点数和边数，然后输入每条边的两个端点和权值。接着，我们对边进行排序，并依次加入最小生成树中，同时使用并查集维护已选边的连通性。最后，输出最小生成树的权值之和即可。

需要注意的是，如果输入的图不连通，则无法构造最小生成树。此时，我们需要在算法中进行额外处理，例如输出 -1 或者抛出异常等。