最小生成树（Minimum Spanning Tree）

最小生成树（Minimum Spanning Tree，MST）是图论中的经典问题：在一个带权无向图中，找到连接所有顶点且总权重最小的树。

什么是最小生成树？

生成树：连接图中所有顶点且无环的边集。

最小生成树：总权重最小的那个生成树。

原始图：          最小生成树：
    1                    1
   /|\                  /|
  2 3 4                2 |
 /  \|/ \                \|
5----6----7            5--6--7

总权重: 最小           总权重: 最小

MST 的性质：

边的数量 = 顶点数 - 1
不存在环
总权重最小

应用场景：

网络布线（光缆、网线）
电路板设计
城市道路规划
聚类分析

算法一：Kruskal 算法

核心思想

贪心：每次选最短的边，只要不形成环就加入。

Kruskal 步骤：
1. 把所有边按权重从小到大排序
2. 依次遍历每条边：
   - 如果这条边连接的两个顶点不在同一个集合 → 加入
   - 否则 → 跳过（会形成环）
3. 直到选了 n-1 条边

实现（并查集）

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # 已在同一集合
        # 按秩合并
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal(n, edges):
    """
    n: 顶点数
    edges: [(u, v, w), ...] 边列表
    """
    # 1. 按权重排序
    edges.sort(key=lambda x: x[2])
    
    # 2. 初始化并查集
    uf = UnionFind(n)
    
    mst_weight = 0
    mst_edges = []
    edge_count = 0
    
    for u, v, w in edges:
        if uf.union(u, v):
            mst_weight += w
            mst_edges.append((u, v, w))
            edge_count += 1
            if edge_count == n - 1:
                break
    
    return mst_weight, mst_edges

时间复杂度

步骤	时间复杂度
排序所有边	O(E log E)
并查集操作	O(E · α(N)) ≈ O(E)
总复杂度	O(E log E)

E = 边数，α = Ackermann 函数（近似常数）

算法二：Prim 算法

核心思想

贪心 + 切分：从一个顶点开始，每次选择跨越”已选集合”和”未选集合”的最小边。

Prim 步骤：
1. 任选一个起始顶点，加入已选集合
2. 重复直到所有顶点都被选中：
   - 找到连接已选集合和未选集合的最小边
   - 将该边的另一顶点加入已选集合

实现（堆优化）

import heapq

def prim(n, edges):
    """
    n: 顶点数
    edges: [(u, v, w), ...] 边列表
    """
    # 建邻接表
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))
    
    # 从顶点 0 开始
    visited = [False] * n
    visited[0] = True
    
    # 候选边堆：(权重, 目标顶点, 来源顶点)
    heap = [(w, v, u) for u, v, w in graph[0]]
    heapq.heapify(heap)
    
    mst_weight = 0
    edge_count = 0
    
    while heap and edge_count < n - 1:
        w, v, u = heapq.heappop(heap)
        
        if visited[v]:
            continue
        
        visited[v] = True
        mst_weight += w
        edge_count += 1
        
        # 添加新顶点相邻的边
        for nv, nw in graph[v]:
            if not visited[nv]:
                heapq.heappush(heap, (nw, nv, v))
    
    return mst_weight

时间复杂度

实现方式	时间复杂度
朴素实现	O(V²)
堆优化	O(E log V)
斐波那契堆	O(E + V log V)

LeetCode 实战

题目 1：找到最小生成树中的第 K 小的边

LeetCode 1482 - 制作 m 束花的最少天数（变形）

其实 MST 直接题不多，更多是最小连接成本的应用：

题目 2：连接n个城市的最少成本

LeetCode 1584 - 连接所有点的最小费用

class Solution:
    def minCostConnectPoints(self, points):
        """曼哈顿距离作为边的权重"""
        n = len(points)
        edges = []
        
        # 构建所有边（优化：只用相邻点）
        # 但为了通用性，这里用完全图
        for i in range(n):
            for j in range(i + 1, n):
                dist = abs(points[i][0] - points[j][0]) + \
                       abs(points[i][1] - points[j][1])
                edges.append((i, j, dist))
        
        # Kruskal
        edges.sort(key=lambda x: x[2])
        uf = UnionFind(n)
        
        total = 0
        count = 0
        
        for u, v, w in edges:
            if uf.union(u, v):
                total += w
                count += 1
                if count == n - 1:
                    break
        
        return total

题目 3：最小连接成本（变形）

LeetCode 1167 - 连接棒料棒的最小成本

class Solution:
    def connectSticks(self, sticks):
        """哈夫曼思想：用最小堆贪心"""
        if len(sticks) == 1:
            return 0
        
        heapq.heapify(sticks)
        total = 0
        
        while len(sticks) > 1:
            # 取最短的两根
            a = heapq.heappop(sticks)
            b = heapq.heappop(sticks)
            
            cost = a + b
            total += cost
            
            # 合并后放回堆
            heapq.heappush(sticks, cost)
        
        return total

题目 4：Kruskal vs Prim 选择

# 选择原则：
# - 稀疏图 (E ≈ V): Kruskal O(E log E) 更优
# - 稠密图 (E ≈ V²): Prim O(E log V) 更优
# - 一般用 Kruskal，更容易实现

def mst(n, edges, method='kruskal'):
    if method == 'kruskal':
        return kruskal(n, edges)
    else:  # prim
        return prim(n, edges)

两种算法对比

特性	Kruskal	Prim
核心思想	选边	选点
适合图	稀疏图	稠密图
时间复杂度	O(E log E)	O(E log V)
实现难度	低（并查集）	中（堆）
贪心策略	全局最短边	切分最小边

代码简洁性：Kruskal 更简单。

实际应用：大多数场景用 Kruskal，因为实际图多为稀疏。

扩展：次小生成树

次小生成树：总权重第二小的生成树。

求法：

先求 MST
枚举每条非 MST 的边，加入 MST
去掉形成的环中的最大边
取最小值

def second_mst(n, edges):
    # 1. 求 MST
    mst_weight, mst_edges = kruskal(n, edges)
    mst_edge_set = set(mst_edges)
    
    # 2. 枚举非 MST 边
    result = float('inf')
    for u, v, w in edges:
        if (u, v, w) not in mst_edge_set:
            # 求 MST 中 u-v 路径上的最大边
            max_edge = max_on_path(u, v, mst_adj)
            result = min(result, mst_weight + w - max_edge)
    
    return result

💡 小结

MST 核心要点：

算法	核心	时间复杂度	适合场景
Kruskal	选最短边（不形成环）	O(E log E)	稀疏图
Prim	从点出发扩展	O(E log V)	稠密图

Kruskal 代码模板：

def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # 按权重排序
    uf = UnionFind(n)
    total = 0
    for u, v, w in edges:
        if uf.union(u, v):
            total += w
    return total

UnionFind 模板：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

相关阅读：线段树（Segment Tree）