c语言实现最小生成树

最小生成树是一种常见的图论算法，用于在一个加权连通图中找到最小的生成树。以下是使用C语言实现最小生成树的基本步骤：

1. 定义一个结构体来表示图中的边，包括起点、终点和权重。

2. 创建一个邻接矩阵或邻接表来表示图。

3. 从任意一个顶点开始，遍历整个图，并将遍历到的边按照权重从小到大排序。

4. 使用并查集来判断当前遍历到的边是否会形成环，如果不会，则将该边加入到最小生成树中。

5. 重复步骤3和4，直到所有的顶点都被遍历到或者最小生成树中已经包含了所有的顶点。

6. 最后得到的最小生成树即为原图的最小生成树。

下面是一个简单的C语言实现最小生成树的例子：

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

#define MAX_VERTEX_NUM 100

// 边的结构体
typedef struct {
    int start;
    int end;
    int weight;
} Edge;

// 并查集的结构体
typedef struct {
    int parent[MAX_VERTEX_NUM];
    int rank[MAX_VERTEX_NUM];
} UnionFind;

// 初始化并查集
void makeSet(UnionFind *uf, int n) {
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
    }
}

// 查找根节点
int find(UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

// 合并两个节点
void Union(UnionFind *uf, int x, int y) {
    int rootX = find(uf, x);
    int rootY = find(uf, y);
    if (rootX != rootY) {
        if (uf->rank[rootX] > uf->rank[rootY]) {
            uf->parent[rootY] = rootX;
        } else if (uf->rank[rootX] < uf->rank[rootY]) {
            uf->parent[rootX] = rootY;
        } else {
            uf->parent[rootY] = rootX;
            uf->rank[rootX]++;
        }
    }
}

// 按照权重从小到大排序
int compare(const void *a, const void *b) {
    Edge *edge1 = (Edge *)a;
    Edge *edge2 = (Edge *)b;
    return edge1->weight - edge2->weight;
}

// Kruskal算法
void kruskal(Edge *edges, int n, int m) {
    UnionFind uf;
    makeSet(&uf, n);
    int count = 0;
    for (int i = 0; i < m; i++) {
        int start = edges[i].start;
        int end = edges[i].end;
        if (find(&uf, start) != find(&uf, end)) {
            printf("%d %d %d\n", start, end, edges[i].weight);
            Union(&uf, start, end);
            count++;
        }
        if (count == n - 1) {
            break;
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    Edge edges[m];
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &edges[i].start, &edges[i].end, &edges[i].weight);
    }
    qsort(edges, m, sizeof(Edge), compare);
    kruskal(edges, n, m);
    return 0;
}

输入格式为：第一行有两个整数n和m，表示图中有n个顶点和m条边；接下来m行，每行包括三个整数a、b和c，表示a和b之间有一条权重为c的边。输出为最小生成树的边。