最小生成树kruskal和prim C语言

最小生成树算法有两个经典实现：Kruskal's算法和Prim's算法。它们都是用于求解无向加权图的最小生成树。

**Kruskal's算法（克鲁斯卡尔算法）**:
这是一种贪心算法，步骤如下：
1. 将所有边按照权重从小到大排序。
2. 初始化一个空的最小生成树集合。
3. 遍历排序后的边，对于每条边，检查它是否能把当前的树连通成更大的树。如果不是，则加入最小生成树。
4. 重复步骤3，直到形成一个包含所有顶点的树。

**C语言实现Kruskal's算法示例**:

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

// 边的结构体
typedef struct Edge {
    int src, dest, weight;
} Edge;

bool compareEdges(Edge a, Edge b) { return a.weight < b.weight; }

void kruskal(int vertices, Edge* edges) {
    // 其他部分包括排序、并查集等操作
}

int main() {
    int num_vertices, num_edges, i;
    Edge edges[] = ...; // 初始化边数组
    kruskal(num_vertices, edges);
    return 0;
}

**Prim's算法（普里姆算法）**:
这同样是贪心算法，区别在于它从任意一个顶点开始，每次选择当前未加入生成树且连接生成树的边中最短的那一条。它维护了一个已访问顶点集合和一个活跃边集合。

**C语言实现Prim's算法示例**:

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

typedef struct Node {
    int vertex;
    int weight;
} Node;

void prim(int vertices, int edges[], bool graph[]) {
    // 其他部分包括优先队列、邻接矩阵/邻接表的操作
}

int main() {
    int num_vertices, num_edges, i;
    bool graph[vertices][vertices] = ...; // 初始化邻接矩阵
    prim(num_vertices, edges, graph);
    return 0;
}