kruskal最小生成树c语言

以下是Kruskal算法的C语言实现，用于求解无向加权图的最小生成树：

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

#define MAX_VERTEX_NUM 20
#define MAX_EDGE_NUM (MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1) / 2)

typedef struct {
    int from, to;   // 边的起点和终点
    int weight;     // 边的权重
} Edge;

int parent[MAX_VERTEX_NUM]; // 并查集数组，用于判断是否形成环

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

// 查找元素所在集合的根节点
int FindSet(int x) {
    while (parent[x] >= 0) {
        x = parent[x];
    }
    return x;
}

// 合并两个集合
void Union(int root1, int root2) {
    if (root1 == root2) {
        return;
    }
    if (parent[root1] > parent[root2]) {
        parent[root2] += parent[root1];
        parent[root1] = root2;
    } else {
        parent[root1] += parent[root2];
        parent[root2] = root1;
    }
}

// Kruskal最小生成树算法
void Kruskal(Edge* edges, int edgeNum, int vertexNum) {
    InitSet(vertexNum); // 初始化并查集
    int count = 0;
    int i = 0;
    while (count < vertexNum - 1 && i < edgeNum) { // 边数不足n-1或者所有边都已考虑完毕则停止循环
        int root1 = FindSet(edges[i].from);
        int root2 = FindSet(edges[i].to);
        if (root1 != root2) {
            printf("(%d, %d) %d\n", edges[i].from, edges[i].to, edges[i].weight);
            Union(root1, root2);
            count++;
        }
        i++;
    }
}

int main() {
    int vertexNum, edgeNum;
    printf("Please input the number of vertices and edges: ");
    scanf("%d %d", &vertexNum, &edgeNum);
    Edge edges[MAX_EDGE_NUM];
    printf("Please input the edges and weights:\n");
    for (int i = 0; i < edgeNum; i++) {
        scanf("%d %d %d", &edges[i].from, &edges[i].to, &edges[i].weight);
    }
    Kruskal(edges, edgeNum, vertexNum);
    return 0;
}

在该代码中，我们使用了并查集来判断是否形成环，并实现了Kruskal算法来求解最小生成树。