克鲁斯卡尔算法 C语言 并从起点到终点输出最小生成树 代码请加注释

以下是克鲁斯卡尔算法的C语言实现，并输出最小生成树：

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

#define MAX_EDGE_NUM 100 // 最大边数
#define MAX_VERTEX_NUM 100 // 最大顶点数

// 边的结构体
typedef struct Edge {
    int start; // 起点
    int end; // 终点
    int weight; // 权重
} Edge;

// 并查集数组
int parent[MAX_VERTEX_NUM];

/**
 * 并查集查找
 * @param x 要查找的元素
 * @return x所在集合的代表元素
 */
int find(int x) {
    if (parent[x] == x) {
        return x;
    } else {
        return find(parent[x]);
    }
}

/**
 * 并查集合并
 * @param x 集合1的代表元素
 * @param y 集合2的代表元素
 */
void unionSet(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}

/**
 * 比较函数，用于快速排序
 * @param e1 边1
 * @param e2 边2
 * @return 边1的权重是否小于边2的权重
 */
int edgeComp(const void *e1, const void *e2) {
    Edge *edge1 = (Edge *) e1;
    Edge *edge2 = (Edge *) e2;
    return edge1->weight - edge2->weight;
}

/**
 * 克鲁斯卡尔算法
 * @param edges 边数组
 * @param edgeNum 边的数量
 * @param vertexNum 顶点的数量
 * @param start 起点
 * @param end 终点
 */
void kruskal(Edge *edges, int edgeNum, int vertexNum, int start, int end) {
    int i, j;
    int edgeCount = 0; // 已选边的数量
    int totalWeight = 0; // 总权重

    // 初始化并查集数组
    for (i = 0; i < vertexNum; i++) {
        parent[i] = i;
    }

    // 对边按权重排序
    qsort(edges, edgeNum, sizeof(Edge), edgeComp);

    // 遍历每条边
    for (i = 0; i < edgeNum; i++) {
        Edge edge = edges[i];

        // 如果起点和终点已经在同一集合中，则跳过
        if (find(edge.start) == find(edge.end)) {
            continue;
        }

        // 加入这条边
        unionSet(edge.start, edge.end);
        edgeCount++;
        totalWeight += edge.weight;

        // 如果已选边的数量达到了顶点数减一，则说明已经构成了一棵生成树，可以退出循环
        if (edgeCount == vertexNum - 1) {
            break;
        }
    }

    // 输出最小生成树的权重
    printf("最小生成树的权重为：%d\n", totalWeight);
}

int main() {
    int vertexNum, edgeNum;
    Edge edges[MAX_EDGE_NUM];
    int i, start, end;

    // 读入顶点数、边数、起点、终点
    printf("请输入顶点数：");
    scanf("%d", &vertexNum);
    printf("请输入边数：");
    scanf("%d", &edgeNum);
    printf("请输入起点和终点：");
    scanf("%d%d", &start, &end);

    // 读入每条边的起点、终点、权重
    printf("请输入每条边的起点、终点、权重：\n");
    for (i = 0; i < edgeNum; i++) {
        scanf("%d%d%d", &edges[i].start, &edges[i].end, &edges[i].weight);
    }

    // 运行克鲁斯卡尔算法，并输出最小生成树
    kruskal(edges, edgeNum, vertexNum, start, end);

    return 0;
}

注释已经在代码中给出。