使用kurska算法写一个C语言程序求最短路径

Kruskal算法是一种用于求解最小生成树的贪心算法。下面是一个使用C语言实现Kruskal算法求解最短路径的示例程序。

首先，我们需要定义一个结构体来表示边：

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

其中，u和v表示边的两个端点，w表示边的权值。

接下来，我们需要定义一个比较函数，用于对边进行排序：

int cmp(const void* a, const void* b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

然后，我们可以使用Kruskal算法来求解最短路径：

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;
}

void KruskalMST(Edge edges[], int V, int E) {
    Edge result[V];
    int i = 0, j = 0;
    qsort(edges, E, sizeof(Edge), cmp);
    int parent[V];
    memset(parent, -1, sizeof(parent));
    while (i < V - 1 && j < E) {
        Edge next_edge = edges[j++];
        int x = find(parent, next_edge.u);
        int y = find(parent, next_edge.v);
        if (x != y) {
            result[i++] = next_edge;
            Union(parent, x, y);
        }
    }
    printf("Edges in the MST:\n");
    int minimum_cost = 0;
    for (i = 0; i < V - 1; i++) {
        printf("%d - %d: %d\n", result[i].u, result[i].v, result[i].w);
        minimum_cost += result[i].w;
    }
    printf("Minimum Cost: %d\n", minimum_cost);
}

在这个函数中，我们首先对所有边进行排序，然后依次取出最小的边，判断其两个端点是否在同一个集合中，如果不在，则将其加入最小生成树中，并将这两个端点合并到同一个集合中。

最后，我们输出最小生成树中的边以及总权值即可。

使用示例：

int main() {
    int V = 4; // 图中顶点数
    int E = 5; // 图中边数
    Edge edges[] = {
        { 0, 1, 10 },
        { 0, 2, 6 },
        { 0, 3, 5 },
        { 1, 3, 15 },
        { 2, 3, 4 }
    };
    KruskalMST(edges, V, E);
    return 0;
}

输出结果：

Edges in the MST:
2 - 3: 4
0 - 3: 5
0 - 1: 10
Minimum Cost: 19