当前位置：首页 > 牛客 > 牛客4633题：Kruskal算法求解最小生成树问题

牛客4633题：Kruskal算法求解最小生成树问题

4个月前 (08-09)

一、题目解读

牛客4633题要求求解一个带权无向图中的最小生成树，并输出其最大边权值。题目核心在于构建一棵包含所有节点且总权值最小的生成树，需判断是否存在合法解，若不存在则返回-1。问题本质属于图论中的最小生成树问题，可通过Kruskal算法高效解决。

二、解题思路

采用Kruskal算法，结合并查集检测环路。首先对边按权值升序排序，依次遍历边：若连接的两个节点不在同一集合（即不构成环路），则合并集合并记录当前边权值。当合并的边数达到n-1时（形成生成树），退出循环。最终输出最大边权或-1。该思路利用贪心策略，每次选择最小权值的可行边，避免生成树权值增大。

三、解题步骤

1. 输入与初始化：读取节点数N和边数M，创建Edge数组存储边信息，初始化并查集UnionFind（N个独立节点）。

2. 边排序：按边权值升序排序edges，确保后续处理优先选择小权值边。

3. Kruskal核心逻辑：遍历排序后的边，对每条边(u,v)：

○ 通过find()获取u和v的根节点，若不同则合并（unite返回true），更新最大边权maxWood并计数边数edgeCount。

○ 当边数达到N-1时，生成树已形成，退出循环。

4. 结果判断：若edgeCount = N-1，输出maxWood；否则说明无合法生成树，输出-1。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 并查集数据结构用于检测环路
struct UnionFind {
    vector<int> parent;
    UnionFind(int n) : parent(n+1) {
        for(int i = 1; i <= n; ++i) // 初始化每个节点为独立集合
            parent[i] = i;
    }
    int find(int x) { // 路径压缩优化查找
        if(parent[x]!= x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY) return false; // 已连通，存在环
        parent[rootY] = rootX; // 合并集合
        return true;
    }
};

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight; // 按权值排序
    }
};

int main() {
    int N, M;
    cin >> N >> M; // 输入节点数和边数

    vector<Edge> edges(M);
    for(int i = 0; i < M; ++i)
        cin >> edges[i].u >> edges[i].v >> edges[i].weight; // 读入边信息

    // Kruskal算法核心步骤
    sort(edges.begin(), edges.end()); // 边排序
    UnionFind uf(N);
    int maxWood = 0, edgeCount = 0;
    for(const auto& e : edges) {
        if(uf.unite(e.u, e.v)) { // 合并可行边
            maxWood = max(maxWood, e.weight);
            if(++edgeCount == N - 1) break; // 生成树形成，退出
        }
    }
    cout << (edgeCount == N - 1? maxWood : -1) << endl; // 输出结果
    return 0;
}