克鲁斯卡尔算法求最小生成树的c语言代码

以下是基于邻接矩阵的克鲁斯卡尔算法求最小生成树的C语言代码实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct {
    int from, to; // 边的起点和终点
    int weight;   // 边的权重
} Edge;

// 邻接矩阵存储图
typedef struct {
    int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边的权重，若两点之间无边则为0
    int vertexNum;                               // 顶点数
    int edgeNum;                                 // 边数
} Graph;

// 初始化图
void initGraph(Graph *G, int vertexNum)
{
    G->vertexNum = vertexNum;
    G->edgeNum = 0;
    for (int i = 0; i < vertexNum; i++) {
        for (int j = 0; j < vertexNum; j++) {
            G->matrix[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(Graph *G, int from, int to, int weight)
{
    G->matrix[from][to] = weight;
    G->matrix[to][from] = weight;
    G->edgeNum++;
}

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

// 查找顶点所在集合的根节点
int findRoot(int parent[], int x)
{
    int root = x;
    while (parent[root] != -1) {
        root = parent[root];
    }
    return root;
}

// 克鲁斯卡尔算法求最小生成树
void Kruskal(Graph *G)
{
    Edge edges[MAX_VERTEX_NUM * MAX_VERTEX_NUM];
    int parent[MAX_VERTEX_NUM];
    int edgeCount = 0;
    int result = 0;

    // 将边全部存入数组中
    for (int i = 0; i < G->vertexNum; i++) {
        for (int j = i + 1; j < G->vertexNum; j++) {
            if (G->matrix[i][j] != 0) {
                edges[edgeCount].from = i;
                edges[edgeCount].to = j;
                edges[edgeCount].weight = G->matrix[i][j];
                edgeCount++;
            }
        }
    }

    // 对边按权值从小到大排序
    qsort(edges, edgeCount, sizeof(Edge), cmp);

    // 初始化parent数组
    for (int i = 0; i < G->vertexNum; i++) {
        parent[i] = -1;
    }

    // 遍历所有边
    for (int i = 0; i < edgeCount; i++) {
        int root1 = findRoot(parent, edges[i].from);
        int root2 = findRoot(parent, edges[i].to);
        if (root1 != root2) { // 如果不在同一个集合中，则加入生成树
            printf("(%d, %d) weight=%d\n", edges[i].from, edges[i].to, edges[i].weight);
            result += edges[i].weight;
            parent[root1] = root2;
        }
    }
    printf("The total weight is %d.\n", result);
}

int main()
{
    Graph G;
    int vertexNum, edgeNum, from, to, weight;

    printf("Please enter the number of vertices and edges:\n");
    scanf("%d %d", &vertexNum, &edgeNum);

    initGraph(&G, vertexNum);

    printf("Please enter the edges and weights:\n");
    for (int i = 0; i < edgeNum; i++) {
        scanf("%d %d %d", &from, &to, &weight);
        addEdge(&G, from, to, weight);
    }

    printf("The minimum spanning tree is:\n");
    Kruskal(&G);

    return 0;
}

其中，邻接矩阵存储图，将边按权值从小到大排序，使用并查集查找顶点所在集合的根节点。最后输出生成树的边和权重。