krusal算法求解最小生成树c语言代码实现

以下是 Kruskal 算法求解最小生成树的 C 语言代码实现：

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

#define MAX_VERTICES 100
#define MAX_EDGES 10000

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

int parent[MAX_VERTICES];

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

void unionSet(int i, int j) {
    int x = find(i);
    int y = find(j);
    parent[x] = y;
}

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

void kruskal(Edge edges[], int numVertices, int numEdges) {
    int i, j, k;
    Edge e;
    for (i = 0; i < numVertices; i++) {
        parent[i] = i;
    }
    qsort(edges, numEdges, sizeof(Edge), compare);
    for (i = 0, j = 0; i < numVertices - 1 && j < numEdges; i++) {
        while (find(edges[j].u) == find(edges[j].v)) {
            j++;
        }
        e = edges[j++];
        unionSet(e.u, e.v);
        printf("(%d, %d) %d\n", e.u, e.v, e.weight);
    }
}

int main() {
    int numVertices, numEdges, i;
    Edge edges[MAX_EDGES];
    scanf("%d %d", &numVertices, &numEdges);
    for (i = 0; i < numEdges; i++) {
        scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].weight);
    }
    kruskal(edges, numVertices, numEdges);
    return 0;
}

希望能够帮到你！