计算机基础

引言 (Introduction)

最小生成树（Minimum Spanning Tree, MST）解决的是一个经典问题：在带权连通图中，找出一棵连接所有节点且边权和最小的树。MST 应用广泛——从网络布线、电路设计到聚类分析（如单链聚类），MST 都是基础建模工具。

MST 的两种算法恰好代表了两种不同的算法设计范式：Kruskal 基于「全局排序 + 并查集维护连通性」，Prim 基于「局部贪心 + 优先队列」。学习这两种算法，同时也是学习并查集这一强大数据结构的绝佳入口。

1. 并查集

1.1 问题定义

并查集（Union-Find / Disjoint Set Union, DSU）维护一组不相交的集合，支持两种操作：

  • Find(x)：查找元素 $x$ 所属集合的代表元。
  • Union(x, y)：合并 $x$ 和 $y$ 所在的两个集合。

1.2 基础实现与两大优化

优化一：路径压缩（Path Compression）——在 Find 操作时，将查找路径上所有节点直接指向根节点。这使得后续 Find 操作接近 $O(1)$。

优化二：按秩合并（Union by Rank）——始终将较低的树合并到较高的树下。这保证了树的高度不超过 $\log n$。

两者结合，均摊时间复杂度为 $O(\alpha(n))$，其中 $\alpha$ 是反阿克曼函数，在实际范围（$n < 2^{65536}$）内不超过 5，可视为常数。

1.3 完整代码 

from typing import List

class UnionFind:
    def __init__(self, n: int):
        self.parent: List[int] = list(range(n))
        self.rank: List[int] = [1] * n
        self.count: int = n               # 连通分量数

    def find(self, x: int) -> int:
        """路径压缩：将 x 直接连到根节点"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x: int, y: int) -> bool:
        """按秩合并。返回 True 表示成功合并，False 表示已在同一集合"""
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False

        # 确保 rx 的秩 >= ry 的秩
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx

        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

    def connected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

find 的递归写法：递归调用的同时完成路径压缩。self.parent[x] = self.find(self.parent[x]) 将查找路径上的每个节点直接挂到根上。

2. Kruskal 算法

2.1 算法思想

Kruskal 是一种全局贪心策略：将所有边按权重升序排列，依次选取每条边。如果边的两端属于不同集合（不形成环），则将该边加入 MST，并合并两端所属集合。

正确性依靠 MST 的割性质：对于图的任意一个割，权重最小的横跨边一定属于某棵 MST。Kruskal 的每一步都是一个割的最小权重边。

2.2 完整代码 

from typing import List, Tuple

class Solution:
    def kruskal(self, n: int, edges: List[Tuple[int, int, int]]) -> List[Tuple[int, int, int]]:
        """
        n: 节点数（0..n-1）
        edges: [(u, v, weight), ...]
        返回: MST 的边列表
        """
        edges.sort(key=lambda x: x[2])     # 按权重升序
        uf = UnionFind(n)
        mst: List[Tuple[int, int, int]] = []

        for u, v, w in edges:
            if uf.union(u, v):
                mst.append((u, v, w))
                if len(mst) == n - 1:      # MST 完成
                    break

        return mst if len(mst) == n - 1 else []  # 不连通则返回空

复杂度：排序 $O(E \log E)$，并查集操作 $O(E \cdot \alpha(V)) \approx O(E)$。总复杂度 $O(E \log E)$。

Kruskal 适合稀疏图（$E$ 较小，排序开销可控）。

3. Prim 算法

3.1 算法思想

Prim 是一种局部贪心策略：从任意起点出发，每次选择连接「已访问集合」和「未访问集合」的最小权重边，将对应节点加入。

Prim 与 Dijkstra 的结构高度相似——两者都用优先队列，区别仅在于优先级的定义：Dijkstra 按「起点到该节点的最短距离」排序，Prim 按「到已访问集合的最小边权」排序。

3.2 完整代码 

import heapq
from typing import List, Tuple, Dict

class Solution:
    def prim(self, n: int, graph: Dict[int, List[Tuple[int, int]]]) -> int:
        """
        n: 节点数
        graph: 邻接表 {u: [(v, weight), ...]}
        返回: MST 的总权重，不连通则返回 -1
        """
        visited: set[int] = set()
        heap: List[Tuple[int, int]] = [(0, 0)]  # (权重, 节点)
        total_weight = 0

        while heap and len(visited) < n:
            w, u = heapq.heappop(heap)
            if u in visited:
                continue

            visited.add(u)
            total_weight += w

            for v, weight in graph.get(u, []):
                if v not in visited:
                    heapq.heappush(heap, (weight, v))

        return total_weight if len(visited) == n else -1

复杂度：时间 $O((V + E) \log V)$，空间 $O(V)$。

Prim 适合稠密图（$E$ 接近 $V^2$），此时堆优化 Prim 的开销接近与边数无关。

3.3 Kruskal vs Prim

Kruskal Prim
策略 全局排序，逐边选择 局部贪心，逐点扩张
数据结构 并查集 优先队列
复杂度 $O(E \log E)$ $O((V+E) \log V)$
适用图 稀疏图（$E$ 小） 稠密图（$E$ 大）
是否需要提前建图 否（边列表即可） 是（需要邻接表）

选择法则：给了边列表就用 Kruskal，给了邻接表且图稠密就用 Prim。

4. LeetCode 1584：连接所有点的最小费用

题目：给定平面上的点 points，连接任意两点的代价为曼哈顿距离（$|x_i - x_j| + |y_i - y_j|$）。求连接所有点的最小总代价。

4.1 算法选择

$n \le 1000$，完全图（任意两点之间都有边），边数 $E = \frac{n(n-1)}{2} \approx 5 \times 10^5$。边数较大但尚未到无法承受的程度。Kruskal 需要排序 $5 \times 10^5$ 条边，可过；Prim 不需要先生成所有边，在稠密图上更优。

这里展示 Kruskal 解法（直观）。

from typing import List

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        edges: List[tuple] = []

        # 生成所有边
        for i in range(n):
            xi, yi = points[i]
            for j in range(i + 1, n):
                xj, yj = points[j]
                dist = abs(xi - xj) + abs(yi - yj)
                edges.append((i, j, dist))

        edges.sort(key=lambda x: x[2])
        uf = UnionFind(n)
        total = 0
        cnt = 0

        for u, v, w in edges:
            if uf.union(u, v):
                total += w
                cnt += 1
                if cnt == n - 1:
                    break

        return total

复杂度：建边 $O(n^2)$，排序 $O(n^2 \log n)$。时间可通过，空间 $O(n^2)$。若用 Prim 可省去建边和排序的 $O(n^2)$ 额外空间，但常数更大。

5. LeetCode 684：冗余连接

题目：给定一棵树加上一条额外边形成的图（$n$ 条边，$n$ 个节点），找出这条冗余边。若有多个答案，返回最后出现的那条。

5.1 并查集的直接应用

遍历每条边，若两端已在同一集合中，则这条边就是冗余的（加入它将形成环）。因为要求返回最后出现的，遍历完所有边即可。

from typing import List

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        uf = UnionFind(n + 1)            # 节点从 1 开始编号
        redundant: List[int] = []

        for u, v in edges:
            if not uf.union(u, v):
                redundant = [u, v]       # 已连通 → 这条边是冗余的

        return redundant

复杂度：时间 $O(n \cdot \alpha(n))$，空间 $O(n)$。

关键洞察：在一棵树上添加一条额外边，会恰好形成一个环。并查集的连通性检查就是用来检测这条形成环的边。此题完美展示了并查集在「动态连通性」场景下的强大。

结论 (Conclusion)

本文攻克了 MST 的两大算法与并查集这一核心数据结构：

  1. 并查集：路径压缩 + 按秩合并，均摊 $O(\alpha(n)) \approx O(1)$。用于维护不相交集合和动态连通性。
  2. Kruskal：全局贪心 + 并查集。按边权排序，依次尝试将边加入 MST，使用并查集避免成环。适合稀疏图。
  3. Prim：局部贪心 + 优先队列。从起点出发，每次选择连接「已访问集合」的最小边。适合稠密图。

两道题目（1584、684）分别演示了 MST 的构建和并查集的连通性检测。

下一篇预览：拓扑排序与 DAG——Kahn 算法（入度表 + BFS）、DFS 后序法、环检测（LeetCode 207、210、802）。