最小生成树（克鲁斯卡尔算法） c语言

以下是C语言实现最小生成树（克鲁斯卡尔算法）的代码：

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

#define MAX_VERTICES 20
#define MAX_EDGES MAX_VERTICES * (MAX_VERTICES - 1) / 2

typedef struct {
    int u, v, w;
} Edge;

int parent[MAX_VERTICES];
Edge edge[MAX_EDGES];

int find(int u) {
    while (u != parent[u]) {
        u = parent[u];
    }
    return u;
}

void union_set(int u, int v) {
    parent[u] = v;
}

void kruskal(int n, int m) {
    int i, j, count = 0;
    int min_cost = 0;

    for (i = 0; i < n; i++) {
        parent[i] = i;
    }

    for (i = 0; i < m; i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;

        int p_u = find(u);
        int p_v = find(v);

        if (p_u != p_v) {
            union_set(p_u, p_v);
            min_cost += w;
            count++;
            if (count == n - 1) {
                break;
            }
        }
    }

    if (count == n - 1) {
        printf("Minimum cost of the spanning tree: %d\n", min_cost);
    } else {
        printf("No spanning tree exists.\n");
    }
}

int main() {
    int n, m, i;

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

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

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

    kruskal(n, m);

    return 0;
}

其中，`parent`数组用于实现并查集，`find`函数用于查找节点所在的集合，`union_set`函数用于将两个节点所在的集合合并。`kruskal`函数用于实现克鲁斯卡尔算法，其中`n`表示节点的个数，`m`表示边的个数，`edge`数组用于存储边的信息，包括起点、终点和权值。最后输出生成树的最小权值和。