题解 | #最小生成树#

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

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

// 定义图的结构体
struct Graph {
    int V, E;
    struct Edge* edges; // 保存图的所有边
};

// 创建图的函数
struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph)); // 分配图的内存空间
    graph->V = V; // 图的顶点数
    graph->E = E; // 图的边数
    graph->edges = (struct Edge*)malloc(E * sizeof(struct Edge)); // 分配边数组的内存空间
    return graph;
}

// 寻找节点的根节点（用于判断两个节点是否属于同一个集合）
int findParent(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return findParent(parent, parent[i]);
}

// 合并两个集合
void unionSet(int parent[], int x, int y) {
    int xSet = findParent(parent, x);
    int ySet = findParent(parent, y);
    parent[xSet] = ySet;
}

// 用于 qsort 的比较函数，按照边的权重升序排序
int compareEdges(const void* a, const void* b) {
    struct Edge* edgeA = (struct Edge*)a;
    struct Edge* edgeB = (struct Edge*)b;
    return edgeA->weight - edgeB->weight;
}

// 主函数，实现 Kruskal 算法找到最小生成树的总权重
int miniSpanningTree(int n, int m, int** cost, int costRowLen, int* costColLen ) {
    // 创建图
    struct Graph* graph = createGraph(n, m * 2);

    // 将输入转换为图的边集合
    for (int i = 0; i < m; ++i) {
        graph->edges[i].src = cost[i][0] - 1;
        graph->edges[i].dest = cost[i][1] - 1;
        graph->edges[i].weight = cost[i][2];

        graph->edges[i + m].src = cost[i][1] - 1;
        graph->edges[i + m].dest = cost[i][0] - 1;
        graph->edges[i + m].weight = cost[i][2];
    }

    int V = graph->V; // 顶点数
    int E = graph->E; // 边数

    qsort(graph->edges, E, sizeof(struct Edge), compareEdges); // 对边按权重排序

    int parent[V]; // 用于记录节点的父节点
    memset(parent, -1, sizeof(parent)); // 初始化节点的父节点为 -1，表示各自是独立的集合

    int totalCost = 0; // 记录最小生成树的总权重
    int e = 0; // 边的计数器
    int edgesConsidered = 0; // 已考虑的边的计数器

    // 进行 Kruskal 算法，逐个考虑边
    while (edgesConsidered < V - 1) {
        struct Edge nextEdge = graph->edges[e++];
        int x = findParent(parent, nextEdge.src);
        int y = findParent(parent, nextEdge.dest);

        // 判断两个节点是否属于同一个集合，如果不是，则将这两个节点合并到一个集合中，并将边的权重添加到总权重中
        if (x != y) {
            totalCost += nextEdge.weight;
            unionSet(parent, x, y);
            edgesConsidered++;
        }
    }

    free(graph->edges); // 释放边数组内存
    free(graph); // 释放图的内存

    // 如果最终形成的最小生成树的边数不是 V-1，则说明图不是完全连接的，返回 -1 表示无法构建最小生成树
    if (edgesConsidered != V - 1) {
        return -1; // 图不是完全连接的
    }

    return totalCost; // 返回最小生成树的
}