c语言实现克鲁斯卡尔算法

克鲁斯卡尔算法是一种求解最小生成树的算法，主要思想是从小到大逐渐加入边，直到所有的节点都被连接为止。下面是一个用C语言实现克鲁斯卡尔算法的示例代码：

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

#define MAX 100

// 定义边结构体
typedef struct Edge {
    int u;  // 边的起点
    int v;  // 边的终点
    int w;  // 边的权值
} Edge;

// 初始化并查集
void init(int *parent, int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

// 查找节点所在的集合
int find(int *parent, int i) {
    if (parent[i] == i) {
        return i;
    }
    return find(parent, parent[i]);
}

// 合并两个集合
void merge(int *parent, int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

// 克鲁斯卡尔算法实现
void kruskal(Edge *edges, int n, int m) {
    int parent[MAX];
    int count = 0;
    int i = 0;
    int sum = 0;

    init(parent, n);

    while (count < n - 1 && i < m) {
        Edge e = edges[i++];
        int x = find(parent, e.u);
        int y = find(parent, e.v);

        if (x != y) {
            printf("(%d, %d) %d\n", e.u, e.v, e.w);
            merge(parent, x, y);
            count++;
            sum += e.w;
        }
    }

    printf("Weight of MST: %d\n", sum);
}

// 主函数
int main() {
    Edge edges[MAX];
    int n, m;

    printf("Enter the number of vertices: ");
    scanf("%d", &n);

    printf("Enter the number of edges: ");
    scanf("%d", &m);

    printf("Enter the edges in the format u v w:\n");
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w);
    }

    kruskal(edges, n, m);

    return 0;
}

在这个示例代码中，我们首先定义了一个边结构体，包含起点、终点和权值三个成员变量。然后我们实现了一个初始化并查集的函数，一个查找节点所在集合的函数，一个合并两个集合的函数，最后是克鲁斯卡尔算法的实现。在主函数中，我们先读取输入的节点个数和边的个数，然后读取每条边的起点、终点和权值，最后调用克鲁斯卡尔算法求解最小生成树。