克鲁斯特卡尔算法最小生成树c语言

以下是使用C语言实现克鲁斯卡尔算法求解最小生成树的示例代码：

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

#define MAX_VERTEX_NUM 20
#define MAX_EDGE_NUM 100

typedef struct {
    int vexs[MAX_VERTEX_NUM]; // 存储顶点的数组
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的二维数组
    int n, e; // n表示顶点数，e表示边数
} pragh;

typedef struct {
    int u, v; // 边的起点和终点
    int w; // 边的权值
} edge;

// 初始化图
void init(pragh *G) {
    int i, j;
    G->n = 0;
    G->e = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        for (j = 0; j < MAX_VERTEX_NUM; j++) {
            G->edges[i][j] = 0;
        }
    }
}

// 添加边
void add_edge(pragh *G, int u, int v, int w) {
    G->edges[u][v] = w;
    G->edges[v][u] = w;
    G->e++;
}

// 获取边集合
void get_edges(pragh *G, edge *edges) {
    int i, j, k = 0;
    for (i = 0; i < G->n; i++) {
        for (j = i + 1; j < G->n; j++) {
            if (G->edges[i][j] != 0) {
                edges[k].u = i;
                edges[k].v = j;
                edges[k].w = G->edges[i][j];
                k++;
            }
        }
    }
}

// 比较函数，用于排序
int cmp(const void *a, const void *b) {
    return ((edge *)a)->w - ((edge *)b)->w;
}

// 查找顶点所在的集合
int find(int *parent, int f) {
    while (parent[f] > 0) {
        f = parent[f];
    }
    return f;
}

// 克鲁斯卡尔算法求最小生成树
void kruskal(pragh G) {
    int i, j, u, v, m, n = G.n;
    int parent[MAX_VERTEX_NUM] = {0};
    edge edges[MAX_EDGE_NUM];
    get_edges(&G, edges);
    qsort(edges, G.e, sizeof(edge), cmp);
    for (i = 0; i < G.e; i++) {
        u = edges[i].u;
        v = edges[i].v;
        m = find(parent, u);
        n = find(parent, v);
        if (m != n) {
            parent[m] = n;
            printf("(%d, %d) %d\n", u, v, edges[i].w);
        }
    }
}

// 创建图
void create_graph(pragh *G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &G->n, &G->e);
    printf("请输入顶点信息：\n");
    for (i = 0; i < G->n; i++) {
        scanf("%d", &G->vexs[i]);
    }
    printf("请输入边的信息：\n");
    for (k = 0; k < G->e; k++) {
        printf("请输入边（vi, vj）的下标i，下标j和权值w：\n");
        scanf("%d%d%d", &i, &j, &w);
        add_edge(G, i, j, w);
    }
}

int main(void) {
    pragh G;
    create_graph(&G);
    printf("最小生成树的边为：\n");
    kruskal(G);
    return 0;
}