克鲁斯卡尔算法c代码

克鲁斯卡尔算法是一种用于求解最小生成树的算法。以下是C语言实现克鲁斯卡尔算法的代码，其中使用了并查集来判断是否形成环路：

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

#define MAX_EDGE_NUM 20
#define MAX_VERTEX_NUM 10

typedef struct Edge {
    int u, v;   // 边的两个顶点
    int weight; // 边的权值
} Edge;

int Find(int *parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

void Union(int *parent, int x, int y) {
    parent[x] += parent[y];
    parent[y] = x;
}

void Kruskal(Edge *edges, int n, int e) {
    int i, j, u, v;
    int k = 0;
    int m = 0;
    int *parent = (int*)malloc((n+1)*sizeof(int));
    Edge *result = (Edge*)malloc(n*sizeof(Edge));

    for (i = 0; i <= n; ++i) {
        parent[i] = -1;
    }
    for (i = 1; i <= e; ++i) {
        u = edges[i].u;
        v = edges[i].v;
        if (Find(parent, u) != Find(parent, v)) {
            Union(parent, Find(parent, u), Find(parent, v));
            result[k++] = edges[i];
        }
        if (k == n-1) {
            break;
        }
    }

    printf("The result of Kruskal algorithm:\n");
    for (i = 0; i < k; ++i) {
        printf("(%d, %d) %d\n", result[i].u, result[i].v, result[i].weight);
        m += result[i].weight;
    }
    printf("The minimum cost is %d\n", m);

    free(parent);
    free(result);
}

int main() {
    Edge edges[MAX_EDGE_NUM];
    int n, e;
    int i;

    printf("Please input the number of vertexes and edges:\n");
    scanf("%d%d", &n, &e);

    printf("Please input all edges with their weights:\n");
    for (i = 1; i <= e; ++i) {
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].weight);
    }

    Kruskal(edges, n, e);

    return 0;
}