kruskal最小生成树C语言代码

Kruskal算法是一种用于求解无向图最小生成树的贪心算法。以下是使用C语言实现Kruskal算法的一个简单版本：

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

// 结构体表示边，包含起点、终点和权重
typedef struct Edge {
    int src, dest;
    int weight;
} Edge;

// 边比较函数，用于排序
bool compareEdges(const void *a, const void *b) {
    return ((Edge *)a)->weight < ((Edge *)b)->weight;
}

// 找到并返回一个未加入集合的边，用于最小生成树构建
Edge* findMin(int graph[], int n, int e) {
    Edge *min = &graph[0];
    for (int i = 1; i < e; i++) {
        if (graph[i].weight < min->weight) {
            min = &graph[i];
        }
    }
    return min;
}

// Kruskal's algorithm实现
void kruskalMST(Edge edges[], int m, int n) {
    // 初始化所有顶点属于不同的集合
    bool parent[n + 1] = {false};
    
    // 创建并填充edges数组
    for (int i = 0; i < m; i++) {
        edges[i].src = i + 1;
        edges[i].dest = i + 2;
        edges[i].weight = 0; // 这里假设输入已经包含了边的权重
    }

    // 按权重升序排列边
    qsort(edges, m, sizeof(Edge), compareEdges);

    int count = 0;
    for (int i = 0; i < m && count < n - 1; i++) {
        Edge *e = findMin(edges, n, i);
        
        // 如果这条边连接两个不同的集合，则添加它
        if (!parent[e->src] || !parent[e->dest]) {
            printf("Adding edge %d-%d with weight %d\n", e->src, e->dest, e->weight);
            parent[e->src] = true;
            parent[e->dest] = true;
            count++;
        }
    }
}

int main() {
    int vertices, edges_num;
    printf("Enter number of vertices and edges: ");
    scanf("%d %d", &vertices, &edges_num);

    Edge edges[edges_num]; // 根据实际需要调整数组大小

    // 输入边的信息，这里仅作示例，实际应用需根据实际情况填写
    // 假设输入如：1-2, w1, 2-3, w2, ... 等形式
    for (int i = 0; i < edges_num; i++) {
        int src, dest, weight;
        scanf("%d %d %d", &src, &dest, &weight);
        edges[i].src = src;
        edges[i].dest = dest;
        edges[i].weight = weight;
    }

    kruskalMST(edges, edges_num, vertices);
    return 0;
}

这个程序首先初始化所有顶点为不同的集合，然后对边按权重排序。接着，依次选择最小权重的边，如果这条边连接的是两个不同的集合，就将它们合并成一棵树，并更新最小生成树的节点数。