面试题库 › C++ / 后端 › 最小生成树:Kruskal 与 Prim 算法

最小生成树:Kruskal 与 Prim 算法

难度 ★★☆在 3 场真实面经中被问到 方向:C++ / 后端考点:图论

哪些公司问过

快手1亚马逊1烽火通信1

常见岗位:软件开发、Go 后端

答案要点

  1. 最小生成树:连通无向图中包含全部顶点、n-1 条边、无环且权和最小的树
  2. Kruskal:边按权排序,用并查集判断是否成环,复杂度 O(E log E),适合稀疏图
  3. Prim:从一个顶点扩展,每次加入连接已选集合的最小边,堆实现 O(E log V)
  4. 稠密图可用 O(V²) 的朴素 Prim
  5. 正确性基于切分性质:跨越切分的最小边属于某棵最小生成树

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题