题目链接

最小生成树的最长边

题目描述

给定一个带权无向连通图，求其任意一棵最小生成树 (MST) 中，权重最大的边的权重值。

解题思路

这个问题的核心是求解最小生成树，并找出其中的最长边。使用 Kruskal 算法 可以非常自然地解决这个问题。

Kruskal 算法

Kruskal 算法是一种基于贪心策略的最小生成树算法。其基本思想是：

  1. 将图中所有的边按照权重从小到大进行排序。
  2. 初始化一个空的边集合，用于构成最小生成树。
  3. 依次遍历排序后的边。对于当前遍历到的边，如果将它加入到集合中不会与已有的边形成环，则将这条边加入集合。
  4. 重复步骤3，直到集合中有 条边为止（ 是顶点数）。

为了高效地检测是否形成环，我们通常使用并查集 (Disjoint Set Union, DSU) 数据结构。

关键性质

由于 Kruskal 算法是严格按照边权从小到大的顺序来考察和添加边的，那么它成功加入到最小生成树中的最后一条边（即第 条边），必然是这 条边中权重最大的那一条。

因此，问题就简化为：运行 Kruskal 算法来构建最小生成树，在构建过程中，最后一条被加入的边的权重就是我们要求的答案。

算法流程

  1. 将图的所有 条边存储到一个列表中。
  2. 对这个边列表按照权重进行升序排序。
  3. 初始化一个并查集，其中包含 个元素，每个元素自成一个集合。
  4. 初始化 max_edge_weight = 0 和 edges_added = 0。
  5. 遍历排序后的边列表： a. 取出当前权重最小的边 。 b. 使用并查集的 find 操作判断 和 是否已经连通。 c. 如果它们不连通，则说明加入这条边不会形成环： i. 使用 union 操作将 和 合并到同一个集合。 ii. 更新 max_edge_weight = w。 iii. edges_added 计数加 1。 iv. 如果 edges_added 达到 ，则 MST 构建完成，可以提前结束循环。
  6. 循环结束后，max_edge_weight 中存储的值即为最终答案。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

struct Edge {
    int u, v, w;
};

bool compareEdges(const Edge& a, const Edge& b) {
    return a.w < b.w;
}

struct DSU {
    vector<int> parent;
    DSU(int n) {
        parent.resize(n + 1);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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].w;
    }

    sort(edges.begin(), edges.end(), compareEdges);

    DSU dsu(n);
    int max_edge_weight = 0;
    int edges_count = 0;

    for (const auto& edge : edges) {
        if (dsu.find(edge.u) != dsu.find(edge.v)) {
            dsu.unite(edge.u, edge.v);
            max_edge_weight = edge.w;
            edges_count++;
            if (edges_count == n - 1) {
                break;
            }
        }
    }

    cout << max_edge_weight << endl;

    return 0;
}

import java.util.*;

class Edge implements Comparable<Edge> {
    int u, v, w;

    public Edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.w, other.w);
    }
}

class DSU {
    private int[] parent;

    public DSU(int n) {
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }
    }

    public int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    public void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<Edge> edges = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            edges.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(edges);

        DSU dsu = new DSU(n);
        int maxEdgeWeight = 0;
        int edgesCount = 0;

        for (Edge edge : edges) {
            if (dsu.find(edge.u) != dsu.find(edge.v)) {
                dsu.unite(edge.u, edge.v);
                maxEdgeWeight = edge.w;
                edgesCount++;
                if (edgesCount == n - 1) {
                    break;
                }
            }
        }
        System.out.println(maxEdgeWeight);
    }
}

import sys

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))

    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            self.parent[root_i] = root_j
            return True
        return False

def main():
    input = sys.stdin.readline
    try:
        n, m = map(int, input().split())
    except ValueError:
        return

    edges = []
    for _ in range(m):
        u, v, w = map(int, input().split())
        edges.append((w, u, v))

    edges.sort()

    dsu = DSU(n)
    max_edge_weight = 0
    edges_count = 0

    for w, u, v in edges:
        if dsu.unite(u, v):
            max_edge_weight = w
            edges_count += 1
            if edges_count == n - 1:
                break
    
    print(max_edge_weight)

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法：Kruskal 算法
  • 时间复杂度： 或 。瓶颈在于对 条边进行排序。并查集的操作（带路径压缩和按秩合并优化）的平均时间复杂度接近常数，总共为 ，其中 是反阿克曼函数，增长极其缓慢。因此，排序是主要的时间开销。
  • 空间复杂度：，用于存储边列表和并查集的父节点数组。