prim算法核心是贪心策略：从任一顶点出发，每次选择连接已选顶点集与未选顶点集的最小权重边，将对应新顶点加入生成树，直至覆盖所有顶点；需维护in_mst布尔列表判断内外顶点，并用优先队列高效选取最小边。
Prim算法的核心逻辑是什么
Prim算法本质是贪心策略：从任意一个顶点出发，每次选择与当前生成树相连的、权值最小的边，把对应新顶点加入树中。关键不是“找所有边排序”，而是维护一个动态的候选边集合——用优先队列（heapq）最自然，但也可以用简单数组扫描，后者更易调试、适合理解原理。
手动实现时最容易卡在「如何判断某条边是否连接了树内和树外顶点」。必须显式维护一个 in_mst 布尔列表（或集合），不能只靠是否访问过——因为图可能不连通，而 Prim 要求输入是连通图，否则会提前终止并漏点。
用 heapq 实现带权重的最小边选取
Python 的 heapq 默认按元组第一个元素排序，所以把边权放在元组首位：(weight, neighbor, current)。注意：不要把顶点名（比如字符串）直接塞进堆里做比较，除非你确保它们可比；整数索引最稳。
常见错误是重复入堆：同一顶点可能被多条边多次推入堆中。这没关系——我们靠 in_mst[neighbor] 在出堆时过滤掉已加入的顶点即可。这是标准的 lazy heap 做法，比每次更新堆中元素更简单可靠。
示例片段：
import heapq heap = [] heapq.heappush(heap, (0, 0)) # (weight, vertex), 从顶点 0 开始 in_mst = [False] * n mst_edges = []
邻接表怎么组织才方便 Prim 遍历
输入图推荐用 graph[u] = [(v, w), (x, w2), ...] 这种邻接表形式，其中每个元素是 (neighbor, weight) 元组。不要用字典套字典（如 {u: {v: w}}），它遍历时要额外取 .items()，且不易按索引访问。
如果原始数据是边列表（如 edges = [(u, v, w), ...]），务必先转成邻接表，否则每次找 u 的邻居都要 O(E) 扫描，让整体复杂度退化到 O(V×E)。
注意无向图要双向添加：
for u, v, w in edges:
graph[u].append((v, w))
graph[v].append((u, w))
为什么初始化时要把起始点权重设为 0
因为 heapq 每次弹出最小权重边，而起点本身没有入边。把它以 (0, start) 推入堆，是为了让循环第一次就能取出它、标记为 in_mst[start] = True，然后扫描它的所有邻边。若初始堆为空，整个算法就动不了。
另一个容易忽略的点：当堆变空但 len(mst_edges) != n - 1 时，说明图不连通。此时应报错或返回部分结果——Prim 算法本身不处理非连通图，这点和 Kruskal 不同。
实际写的时候，建议在主循环开头加一句检查：if not heap: break，再在外层判断是否覆盖全部顶点。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
