0Pricing
Coding Interview Prep · 课时

Kruskal 最小生成树

添加最便宜的边，同时避免循环

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

什么是 MST

最小生成树使用总权重最小的边连接每个顶点，且不形成环。您可以把它想象成用最低成本为一座城镇铺设线路。🌲

Kruskal 算法的核心思想

Kruskal 算法完全采用贪心策略：不断加入不会形成环的最小权重边，直到整个图连通。

第一步：对边进行排序

首先对每条边执行 sort，按权重从小到大排列。贪心地优先选择低价边，才能使最终总权重最小。

edges.sort()  # (weight, u, v)

DSU 为什么如此适合

只有当一条边的两个端点已经连通时，加入它才会形成环。DSU可以用近似常数时间完成这项连通性检查。🤝

遍历排好序的边

请按照从最便宜到最昂贵的顺序遍历各条边。对于每条边，检查它的两个端点在 DSU 中是否已经拥有相同的根节点。

for w, u, v in edges:
    ru, rv = find(u), find(v)

接受或拒绝

如果两个根节点不同，说明这条边连接了两个独立部分，因此请接受它并将两者合并。如果根节点相同，则跳过它以避免形成环。

if ru != rv:
    union(u, v)
    total += w

知道何时停止

包含 n 个顶点的生成树恰好有n 减 1条边。接受这么多条边后，您就可以提前停止。

检测图是否不连通

如果遍历完所有边后，接受的边少于 n 减 1 条，则图是不连通的，也就不存在生成树。

时间开销

排序占据主要开销，因此 Kruskal 算法的时间复杂度为O(E log E)。DSU 操作非常高效，几乎不会增加总开销。

贪心策略为何正确

切分性质保证了穿过任意分割的最轻边都可以安全加入，这正是按最低权重优先选择永远不会出错的原因。

何时使用 Kruskal 算法

Kruskal 算法非常适合处理以边列表给出的稀疏图，而这正是大多数竞赛题直接提供的格式。⚡

快速检查

请判断什么条件会让 Kruskal 算法拒绝一条边。

回顾

您构建了Kruskal 的 MST：对边执行 sort，通过 DSU 添加连接两个连通分量的最便宜边，并在达到 n 减 1 条边时停止。🎉

常见问题解答

「Kruskal 最小生成树」课时是免费的吗？

是的 — 「Kruskal 最小生成树」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「Kruskal 最小生成树」这节课中我会学到什么？

添加最便宜的边，同时避免循环 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

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

「Kruskal 最小生成树」课时需要多长时间？

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

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

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

此课程中的所有课时

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