C语言生成克鲁斯卡尔算法求最短路径

以下是C语言实现克鲁斯卡尔算法求最短路径的示例代码：

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

#define MAX 1000

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

struct Graph {
    int V, E;
    struct Edge* edge;
};

struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
    return graph;
}

int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

void Union(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

int myComp(const void* a, const void* b) {
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->w > b1->w;
}

void KruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V];
    int e = 0;
    int i = 0;
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
    int parent[V];
    for (int j = 0; j < V; ++j)
        parent[j] = -1;
    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];
        int x = find(parent, next_edge.u);
        int y = find(parent, next_edge.v);
        if (x != y) {
            result[e++] = next_edge;
            Union(parent, x, y);
        }
    }
    printf("Following are the edges in the constructed MST\n");
    int minimumCost = 0;
    for (i = 0; i < e; ++i) {
        printf("%d - %d : %d\n", result[i].u, result[i].v, result[i].w);
        minimumCost += result[i].w;
    }
    printf("Minimum Cost Spanning tree : %d", minimumCost);
}

int main() {
    int V = 4;
    int E = 5;
    struct Graph* graph = createGraph(V, E);

    graph->edge[0].u = 0;
    graph->edge[0].v = 1;
    graph->edge[0].w = 10;

    graph->edge[1].u = 0;
    graph->edge[1].v = 2;
    graph->edge[1].w = 6;

    graph->edge[2].u = 0;
    graph->edge[2].v = 3;
    graph->edge[2].w = 5;

    graph->edge[3].u = 1;
    graph->edge[3].v = 3;
    graph->edge[3].w = 15;

    graph->edge[4].u = 2;
    graph->edge[4].v = 3;
    graph->edge[4].w = 4;

    KruskalMST(graph);

    return 0;
}