从种树到修路：Prim算法让总成本最低

这是什么？用来解决什么问题？

想象你们学校要新建几栋教学楼，需要铺一条水管连通所有新楼，施工队说每两栋楼之间的铺设费用不同。怎样铺才能让总费用最少？这就是 最小生成树 问题：用一个图（点表示建筑，边表示可能的管道，权重表示费用）找出一棵包含所有点的树（没有环），并且所有边的权重和最小。

Prim算法 就是求解最小生成树的经典方法之一，它的思路特别像“种树”：从一棵小树苗开始，每次选择离这棵树最近的一棵未连接的树苗，连上去，最后所有树苗都长成一棵大树。这样一来，总铺设长度（或总费用）就是最短的。

生活中的比喻：修路连通村庄

假设有5个村庄，它们之间可以修路，每条路的造价不同。你希望用最少的钱修路让所有村庄都能互相到达（不需要每条路都直通，只要通过已修的路能连通就行）。Prim算法是这样工作的：

随便选一个村庄，比如1号村，把它标记为“已通车”。
查看所有与1号村直接相连的村庄，记下每条路的造价。
从中选出造价最低的那条路，修过去，把那个村庄也加入“已通车”集合。
现在“已通车”集合里有2个村庄。找出所有连接“已通车村庄”和“未通车村庄”的路，选造价最低的，再修过去。
重复，直到所有村庄都通车。

注意：每次只选一条路，并且这条路必须连接“已通车”和“未通车”两边，这样才不会形成环。最后所有村庄通过n-1条路连通，总造价最小。

算法核心步骤（配上手算小例子）

假设有5个点（0,1,2,3,4），它们之间的边（无向）和权重如下：

0-1: 10, 0-2: 15
1-2: 5, 1-3: 12
2-3: 8, 2-4: 7
3-4: 3

我们模拟Prim算法过程（选0为起点）：

初始化：已访问集合 = {0}。记录每个未访问点到当前树的最小距离：
dist[1]=10 (0→1), dist[2]=15 (0→2), dist[3]=∞, dist[4]=∞。
最小距离是10，对应点1，把它加入树（边0-1）。
更新：现在已访问 = {0,1}。检查点1的邻居：
- 点2：距离5（比原来的15小，更新dist[2]=5）
- 点3：距离12（原来∞，更新dist[3]=12）
  dist变为：dist[2]=5, dist[3]=12, dist[4]=∞。最小距离5，对应点2，加入树（边1-2）。
更新：已访问 = {0,1,2}。点2的邻居：
- 点3：距离8（比原来的12小，更新为8）
- 点4：距离7（原来∞，更新为7）
  dist: dist[3]=8, dist[4]=7。最小距离7，对应点4，加入树（边2-4）。
更新：已访问 = {0,1,2,4}。点4的邻居：
- 点3：距离3（比原来的8小，更新为3）
  dist[3]=3，加入树（边4-3）。
所有5个点都访问了，结束。选中的边：0-1(10), 1-2(5), 2-4(7), 4-3(3)。总权重=10+5+7+3=25。

新手容易犯的错误

忘记处理堆中已过时的边
优先队列（堆）里可能同时存着同一个点不同距离的记录（因为更新了距离但旧记录没被删除）。必须用 visited 数组判断：如果从堆中弹出时发现该点已经访问过，就直接跳过，否则会错误地重复加入。
正确做法：在 while 循环中 if visited[u]: continue。
初始化起点时距离处理不对
如果图不连通，算法可能永远无法访问所有点。应该检查循环结束后 visited 是否全为True，否则说明图不连通，不存在最小生成树。
邻接表只保存单向
Prim算法需要无向图（每条边在邻接表中存两次）。如果只存了一次，会导致找不到某些边，生成错误结果。
忽略权重为0的边
权重可以是0，堆中优先队列会正常工作，但要注意权重0的边也可能形成环？不会，因为Prim只连接未访问点。

完整可运行的Python代码

下面给出一个带输入输出示例的完整程序，代码中每行变量定义都写了中文注释，方便理解。

import heapq

def prim_mst(n, adj):
    """
    使用Prim算法求最小生成树
    :param n: int, 节点个数（节点编号0~n-1）
    :param adj: list of list, 邻接表，adj[u] = [(v, weight), ...]
    :return: (总权重, 边列表)
    """
    visited = [False] * n          # 记录每个节点是否已加入生成树
    # 堆元素：(权重, 当前节点, 父节点)
    min_heap = [(0, 0, -1)]        # 从节点0开始，权重0，父节点-1表示无
    mst_weight = 0                 # 最小生成树总权重
    mst_edges = []                 # 存储选中的边 (parent, child, weight)

    while min_heap:
        weight, u, parent = heapq.heappop(min_heap)  # 弹出权重最小的边
        if visited[u]:
            continue               # 如果该点已经加入树，跳过（防止旧记录干扰）
        visited[u] = True          # 标记为已加入
        mst_weight += weight       # 累加权重
        if parent != -1:
            mst_edges.append((parent, u, weight))  # 记录边
        # 遍历当前节点u的所有邻居
        for v, w in adj[u]:
            if not visited[v]:     # 只考虑未访问的邻居
                heapq.heappush(min_heap, (w, v, u))  # 将边加入堆

    # 检查是否所有点都访问了（图连通性检查）
    if not all(visited):
        raise ValueError("图不连通，无法生成最小生成树")
    return mst_weight, mst_edges

# ---------- 测试示例 ----------
if __name__ == "__main__":
    # 5个节点，手工构造的图（无向）
    graph_adj = [
        [(1, 10), (2, 15)],        # 节点0的邻居
        [(0, 10), (2, 5), (3, 12)],# 节点1
        [(0, 15), (1, 5), (3, 8), (4, 7)], # 节点2
        [(1, 12), (2, 8), (4, 3)], # 节点3
        [(2, 7), (3, 3)]           # 节点4
    ]
    try:
        total_weight, edges = prim_mst(5, graph_adj)
        print("最小生成树总权重:", total_weight)
        print("选中的边（起点→终点，权重）:")
        for s, t, w in edges:
            print(f"  {s} -- {t} : {w}")
    except ValueError as e:
        print(e)

运行结果：

最小生成树总权重: 25
选中的边（起点→终点，权重）:
  0 -- 1 : 10
  1 -- 2 : 5
  2 -- 4 : 7
  4 -- 3 : 3

代码详解：为什么要用堆？

堆（优先队列） 让我们每次都能快速拿到距离最小的边，而不必每次扫描所有未访问点。堆的插入和弹出都是 O(log n)，整体复杂度 O((n + m) log n)（m是边数），比朴素遍历的 O(n²) 快很多。
visited 数组 确保每个节点只加入一次，不会形成环。
注意邻接表必须包含双向边，因为是无向图。如果只存单向，算法会漏掉边。

Python最小生成树 Prim 算法