kruskal最小生成树算法代码

Kruskal's algorithm（克鲁斯卡尔算法）是一种用于寻找无向加权图的最小生成树的贪心算法。以下是一个简单的C语言版本实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.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;
}

void kruskal(int vertices, Edge *edges) {
    // 初始化边集合为无序数组
    Edge *edgeSet = (Edge*)malloc(sizeof(Edge)*vertices*vertices);
    int i, j, m = vertices * (vertices - 1) / 2, e = 0;

    for (i = 0; i < vertices; i++) {
        for (j = i + 1; j < vertices; j++) {
            edgeSet[e].src = i;
            edgeSet[e].dest = j;
            edgeSet[e].weight = edges[i][j].weight; // 假设edges数组已存储所有边的权重
            e++;
        }
    }

    // 按照边的权重对边进行排序
    qsort(edgeSet, m, sizeof(Edge), compareEdges);

    int parent[vertices];     // 存储每个顶点的父亲节点
    for (i = 0; i < vertices; i++) {
        parent[i] = i;
    }

    int minCost = 0; // 最小生成树的总权重

    for (i = 0; i < m; i++) { 
        Edge currentEdge = edgeSet[i];

        // 查找边所在集合中的代表顶点
        int x = find(parent, currentEdge.src);
        int y = find(parent, currentEdge.dest);

        // 如果它们属于不同的集合
        if (x != y) {
            // 将它们合并到同一个集合，并增加最小生成树的权重
            union(parent, x, y);
            minCost += currentEdge.weight;
        } else {
            break; // 已经找到m个不重复的边
        }
    }

    printf("Minimum Spanning Tree with total cost: %d\n", minCost);
}

// 寻找代表顶点的索引
int find(int parent[], int vertex) {
    if (parent[vertex] == vertex)
        return vertex;
    return parent[vertex] = find(parent, parent[vertex]);
}

// 合并两个集合
void union_(int parent[], int x, int y) {
    int set_x = find(parent, x);
    int set_y = find(parent, y);

    if (set_x != set_y) {
        parent[set_x] = set_y;
    }
}

int main() {
    int V, E;
    printf("Enter number of vertices and edges: ");
    scanf("%d %d", &V, &E);
    
    // 创建适当的边数据结构（这里假设边的数据已存在）
    Edge edges[V][E];
    // ... (填充边信息)

    clock_t start_time = clock();
    kruskal(V, edges);
    double time_taken = ((double)(clock() - start_time)) / CLOCKS_PER_SEC;
    printf("Time taken by Kruskal's Algorithm: %.6f seconds\n", time_taken);

    return 0;
}

这个程序首先读取顶点数和边的数量，然后创建一个边集合，按照权重排序。接着使用`find`和`union_`函数处理并查集，每次选择当前边连接不在同一集合的顶点。当添加第m条边后，我们就得到了最小生成树。