C语言中克鲁斯卡尔算法求最小生成树

克鲁斯卡尔（Kruskal's Algorithm）是一种用于寻找有向或无向加权图中最小生成树（Minimum Spanning Tree, MST）的经典算法。它是贪心算法的一种，适用于边是有权重的图，但要求的结果必须形成一棵树，即任意两个顶点间恰好有一条路径。

下面是克鲁斯卡尔算法的基本步骤：

1. **排序边**：首先按照边的权重对所有边进行非递减排序。

2. **初始化**：设置一个空的集合，表示已经加入最小生成树的边，初始状态下没有边。

3. **选择边**：从排序后的边开始，依次选取每一条边，检查这条边是否能连接到现有的最小生成树上而不形成环。如果不能，则这条边就是新加入的一条边，将其添加到集合中。

4. **重复**：直到所有的顶点都被包含在生成树中，或者无法再添加新的边为止。

5. **结果**：最终得到的就是最小生成树，包含了若干条边，它们的总权重是最小的。

以下是用C语言实现克鲁斯卡尔算法的一个简单示例，假设我们有一个二维数组`edges`存储了边的权重和起点终点，其中`edges[i]`为`(u, v, w)`的形式，代表从`u`到`v`的边重`w`：

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

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

// 检查边是否会引入环
int isCycle(int parent[], int edge_u, int edge_v) {
    return (parent[edge_u] != -1 && parent[parent[edge_u]] != edge_v);
}

void kruskalMST(Edge edges[], int n, int mst_set[]) {
    // 初始化父节点数组
    int parent[n];
    for (int i = 0; i < n; i++) {
        parent[i] = -1;
    }

    int weight = 0; // 最小生成树的总重量

    // 排序边
    // 这里假设边已经按权重降序排列
    // 如果没有现成的排序函数可用，你可以使用冒泡排序、快速排序等
    // 假设edges[]数组本身就是按升序排列
    for (int i = 0; i < m; i++) {
        Edge current_edge = edges[i];

        // 如果这条边不会形成环
        if (!isCycle(parent, current_edge.u, current_edge.v)) {
            // 添加边并更新父节点
            parent[current_edge.v] = current_edge.u;
            mst_set[current_edge.w] = 1; // 标记这条边已被选中
            weight += current_edge.w;
        }
    }
}

// 示例使用
int main() {
    Edge edges[] = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};
    int num_nodes = sizeof(edges) / sizeof(edges[0]) / 3; // 计算节点数
    int m = sizeof(edges) / sizeof(edges[0]); // 边的数量
    int mst_set[num_nodes]; // 初始化是否被选中的标志数组

    kruskalMST(edges, num_nodes, mst_set);

    printf("Minimum spanning tree has a total weight of %d\n", weight);
    // 可视化输出最小生成树结构（这里省略）

    return 0;
}