用C语言写克鲁斯卡尔算法

好的，下面是用C语言实现克鲁斯卡尔算法的代码：

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

#define MAX_VERTICES 1000
#define MAX_EDGES 10000

typedef struct {
    int u;
    int v;
    int weight;
} Edge;

typedef struct {
    int parent;
    int rank;
} Subset;

Edge edges[MAX_EDGES];
Subset subsets[MAX_VERTICES];

int find(int i) {
    if (subsets[i].parent != i) {
        subsets[i].parent = find(subsets[i].parent);
    }
    return subsets[i].parent;
}

void unionSet(int x, int y) {
    int xroot = find(x);
    int yroot = find(y);

    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;
    } else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

int compare(const void* x, const void* y) {
    Edge* a = (Edge*)x;
    Edge* b = (Edge*)y;
    return a->weight - b->weight;
}

void kruskal(int num_vertices, int num_edges) {
    int mst_weight = 0;
    int mst_size = 0;

    for (int i = 0; i < num_vertices; i++) {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }

    qsort(edges, num_edges, sizeof(Edge), compare);

    for (int i = 0; i < num_edges; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int weight = edges[i].weight;

        if (find(u) != find(v)) {
            unionSet(u, v);
            printf("(%d, %d) %d\n", u, v, weight);
            mst_weight += weight;
            mst_size++;
            if (mst_size == num_vertices - 1) {
                break;
            }
        }
    }

    printf("MST weight: %d\n", mst_weight);
}

int main() {
    int num_vertices = 6;
    int num_edges = 9;

    edges[0].u = 0;
    edges[0].v = 1;
    edges[0].weight = 5;
    edges[1].u = 0;
    edges[1].v = 2;
    edges[1].weight = 1;
    edges[2].u = 0;
    edges[2].v = 3;
    edges[2].weight = 4;
    edges[3].u = 1;
    edges[3].v = 2;
    edges[3].weight = 3;
    edges[4].u = 1;
    edges[4].v = 4;
    edges[4].weight = 8;
    edges[5].u = 2;
    edges[5].v = 3;
    edges[5].weight = 6;
    edges[6].u = 2;
    edges[6].v = 4;
    edges[6].weight = 7;
    edges[7].u = 3;
    edges[7].v = 4;
    edges[7].weight = 2;
    edges[8].u = 4;
    edges[8].v = 5;
    edges[8].weight = 9;

    kruskal(num_vertices, num_edges);

    return 0;
}

上述代码实现了一个简单的克鲁斯卡尔算法，用于计算给定无向图的最小生成树。在代码中，我们使用了并查集来检查两个节点是否在同一个集合中。我们还使用了快速排序算法来按照边的权重对边进行排序。最后，我们遍历排好序的边，并使用并查集来判断是否将该边添加到最小生成树中。如果添加该边不会导致环形成，则将该边添加到最小生成树中，并更新最小生成树的权重。