0Pricing
Competitive Programming Academy · 课时

使用堆实现 Prim 的 MST

从一个顶点开始扩展树

使用堆实现 Prim 的 MST 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

通往 MST 的另一条路径

Prim 算法同样可以找到最小生成树，但它是从一个连通块向外扩展，而不是先对所有边进行排序。🌱

从一个顶点开始扩展

请选择任意一个起始顶点，并将其标记为已访问。树从一个节点开始，每次通过一条边逐步扩展。

visited = [False] * n

边界的概念

每一步中，您都要查看从树连接到外部的所有边。Prim 算法始终选择这些边界边中最便宜的一条。

用堆选出最小值

最小堆可以快速找到最便宜的边界边。每一轮将候选边压入堆中，并弹出权重最小的边。

import heapq
heap = [(0, start)]

弹出最便宜的边

请从堆中弹出最小的元素。它会提供权重以及下一个应以最低成本连接到扩展中树的顶点。

w, u = heapq.heappop(heap)

跳过过时的元素

一个顶点可能会多次出现在堆中。如果弹出的顶点已经访问过，请直接忽略它并再次弹出元素。

if visited[u]:
    continue

添加并扩展

将弹出的顶点标记为已访问，并把它的权重加入总权重。然后将它的每条出边压入堆中，供后续步骤使用。

visited[u] = True
total += w
for wt, v in adj[u]:
    heapq.heappush(heap, (wt, v))

重复直到完成

不断弹出元素并扩展，直到每个顶点都已访问。此时累积的总权重就是最小生成树的权重。

运行时间

每条边最多压入一次、弹出一次，因此基于堆的 Prim 算法运行时间为O(E log V)，与 Kruskal 算法相当。

Prim 算法与 Kruskal 算法

对于使用邻接表表示的稠密图，请使用Prim 算法；如果已经拥有普通的边列表，则使用 Kruskal 算法。两者得到的 MST 权重相同。

它看起来像 Dijkstra 算法

堆循环与Dijkstra 算法很相似，但这里比较的是原始边权重，而不是路径距离。识别出这种模式可以节省编码时间。⚡

快速检查

请回忆 Prim 算法每一轮如何选择下一条边。

回顾

您使用Prim 算法构建了 MST：从任意位置开始，使用最小堆添加最便宜的边界边，并跳过过时的访问记录。做得很好！🎉

常见问题解答

「使用堆实现 Prim 的 MST」课时是免费的吗？

是的 — 「使用堆实现 Prim 的 MST」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「使用堆实现 Prim 的 MST」这节课中我会学到什么？

从一个顶点开始扩展树 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。

「使用堆实现 Prim 的 MST」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 带路径压缩的 DSU
  2. 按秩合并与连通分量
  3. Kruskal 最小生成树
  4. 使用堆实现 Prim 的 MST
← 返回 Competitive Programming Academy