最小生成树：Prim算法的堆优化版本

一、问题描述

给定一个无向连通带权图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集，每条边有一个非负权值。
目标是找到图 \(G\) 的一棵最小生成树（Minimum Spanning Tree, MST），即包含所有顶点的、总边权最小的连通无环子图。
Prim算法的基本思想是从一个顶点开始，逐步扩展生成树，每次添加一条当前可选的、权值最小的边（这条边连接已选顶点集和未选顶点集）。
堆优化版本（常称为Prim-Dijkstra优化）的核心改进在于：用优先队列（最小堆）高效地维护和获取“当前可选的最小边”。

二、核心概念与基本Prim算法回顾

1. 基本Prim算法（邻接矩阵实现）步骤

   • 任意选一个起点（如顶点0），加入集合 \(S\)（已在MST中的顶点集），其余顶点在集合 \(T\) 中。
   • 维护一个数组 minDist[v]，记录每个未选顶点 \(v\) 到当前已选集合 \(S\) 的最短边权（即从已选顶点到 \(v\) 的所有边中的最小权值）。
   • 每次从 \(T\) 中选出 minDist 最小的顶点 \(u\)，将其加入 \(S\)，并将 \(u\) 连接到已选顶点集的那条边加入MST。
   • 更新 \(u\) 的所有邻接点 \(v\) 的 minDist[v]：若边 \((u, v)\) 的权值小于 minDist[v]，则更新。
   • 重复直到所有顶点加入 \(S\)。

2. 时间复杂度

   • 邻接矩阵实现：\(O(V^2)\)，适合稠密图。
   • 当图为稀疏图（边数 \(E\) 远小于 \(V^2\)）时，此方法效率较低。

三、堆优化版本的思路

1. 目标
   将“每次从未选顶点中找出 minDist 最小者”的操作，用最小堆（优先队列）实现，从而降低时间复杂度。

2. 数据结构

   • 优先队列（最小堆）heap：存储 (dist, v) 对，其中 dist 是顶点 \(v\) 到已选集合的当前最短边权，\(v\) 是顶点编号。
   • 数组 inMST[v]：标记顶点 \(v\) 是否已加入MST。
   • 数组 minDist[v]：意义同基本Prim，记录当前最短边权。

3. 操作优化

   • 初始时，将起点 \((0, 0)\) 入堆（dist=0 表示从已选集合到自身的距离为0）。
   • 每次从堆中弹出 dist 最小的顶点 \(u\)，若它已 inMST[u] 为真，则跳过（避免重复处理）。
   • 否则将其加入MST，并遍历其邻接边，如果边 \((u, v)\) 的权值 \(w\) 小于 minDist[v]，则更新 minDist[v] = w，并将 (w, v) 加入堆中（允许重复入堆，通过 inMST 标记过滤）。
   • 这样做的好处是：不必每次在未选顶点中线性扫描找最小，而是从堆顶快速获取。

四、逐步详细示例

考虑下图（顶点数 \(V=5\)，边数 \(E=7\)）：

顶点: 0-1-2-3-4
边与权值:
0-1: 2
0-3: 6
1-2: 3
1-3: 8
1-4: 5
2-4: 7
3-4: 9

用邻接表存储图。

步骤1：初始化

• 起点选0。inMST = [False, False, False, False, False]，minDist = [0, ∞, ∞, ∞, ∞]。
• 堆初始：[(0, 0)]。

步骤2：第一次弹出堆顶

• 弹出 (0, 0)，inMST[0] = False，将其加入MST：inMST[0] = True。此时MST包含顶点0，总边权=0。
• 遍历0的邻接边：
  • 邻接点1，边权2。minDist[1] = ∞ > 2，更新 minDist[1] = 2，入堆 (2, 1)。
  • 邻接点3，边权6。minDist[3] = ∞ > 6，更新 minDist[3] = 6，入堆 (6, 3)。
• 堆状态：[(2,1), (6,3)]。

步骤3：第二次弹出堆顶

• 弹出 (2, 1)，inMST[1] = False，加入MST，MST边加入 (0-1:2)，总边权=2。
• 遍历顶点1的邻接边：
  • 邻接点0，已 inMST[0]=True，跳过。
  • 邻接点2，边权3。minDist[2]=∞ > 3，更新 minDist[2]=3，入堆 (3,2)。
  • 邻接点3，边权8。当前 minDist[3]=6，8>6，不更新。
  • 邻接点4，边权5。minDist[4]=∞ > 5，更新 minDist[4]=5，入堆 (5,4)。
• 堆状态：[(3,2), (6,3), (5,4)]。

步骤4：第三次弹出堆顶

• 弹出 (3, 2)，inMST[2]=False，加入MST，MST边加入 (1-2:3)，总边权=5。
• 遍历顶点2的邻接边：
  • 邻接点1，已 inMST[1]=True，跳过。
  • 邻接点4，边权7。当前 minDist[4]=5，7>5，不更新。
• 堆状态：[(5,4), (6,3)]。

步骤5：第四次弹出堆顶

• 弹出 (5, 4)，inMST[4]=False，加入MST，MST边加入 (1-4:5)，总边权=10。
• 遍历顶点4的邻接边：
  • 邻接点1，已 inMST[1]=True，跳过。
  • 邻接点2，已 inMST[2]=True，跳过。
  • 邻接点3，边权9。当前 minDist[3]=6，9>6，不更新。
• 堆状态：[(6,3)]。

步骤6：第五次弹出堆顶

• 弹出 (6, 3)，inMST[3]=False，加入MST，MST边加入 (0-3:6)，总边权=16。
• 遍历顶点3的邻接边：邻接点0、1、4均已在MST中，跳过。
• 堆为空。

最终MST：包含边 (0,1)、(1,2)、(1,4)、(0,3)，总权值=2+3+5+6=16。

五、堆优化版本的复杂度分析

• 每个顶点最多入堆一次（但实际可能因更新而重复入堆，但每个顶点最多被弹出并处理一次）。
• 堆操作：
  • 每个顶点出堆一次，复杂度 \(O(V \log V)\)。
  • 每条边可能触发一次入堆（当发现更小的 minDist 时），复杂度 \(O(E \log V)\)。
• 总时间复杂度：\(O((V+E) \log V)\)。
• 空间复杂度：\(O(V+E)\) 用于存图，\(O(V)\) 用于堆。

六、代码实现要点

import heapq

def prim_mst_heap(graph, start=0):
    """
    graph: 邻接表，graph[u] = [(v, w), ...]
    start: 起始顶点
    """
    V = len(graph)
    inMST = [False] * V
    minDist = [float('inf')] * V
    minDist[start] = 0
    heap = [(0, start)]  # (dist, vertex)
    mst_edges = []
    total_weight = 0

    while heap:
        dist, u = heapq.heappop(heap)
        if inMST[u]:
            continue
        inMST[u] = True
        total_weight += dist
        if u != start:  # 不记录起点的“边”
            # 实际记录边需要额外保存连接信息，这里省略
            pass
        for v, w in graph[u]:
            if not inMST[v] and w < minDist[v]:
                minDist[v] = w
                heapq.heappush(heap, (w, v))
    return total_weight

七、对比与总结

• 堆优化Prim在稀疏图中效率高于基本Prim的 \(O(V^2)\) 方法。
• 与Kruskal算法对比：
  • Kruskal按边排序，复杂度 \(O(E \log E)\)，适合边数较少的稀疏图。
  • 堆优化Prim适合边数较多的稠密图吗？当 \(E\) 接近 \(V^2\) 时，堆优化Prim的 \(O(V^2 \log V)\) 可能略慢于基本Prim的 \(O(V^2)\)，但实际中通常仍用堆优化，因为它编码简单且对多数图高效。
• 关键优化点：允许重复入堆，用 inMST 标记避免重复加入MST。