最小生成树:Kruskal 与 Prim 算法
哪些公司问过
答案要点
- 最小生成树:连通无向图中包含全部顶点、n-1 条边、无环且权和最小的树
- Kruskal:边按权排序,用并查集判断是否成环,复杂度 O(E log E),适合稀疏图
- Prim:从一个顶点扩展,每次加入连接已选集合的最小边,堆实现 O(E log V)
- 稠密图可用 O(V²) 的朴素 Prim
- 正确性基于切分性质:跨越切分的最小边属于某棵最小生成树
易错点
- 把最小生成树和单源最短路混淆,生成树上两点路径不一定是最短路
- Kruskal 不用并查集而用 DFS 判环,复杂度变高
- 对有向图直接套用最小生成树算法
面试官常见追问
- 并查集的时间复杂度是多少?
- 求一条路径,使路径上最大边权最小,怎么用到最小生成树?
- Kruskal 还能怎么优化?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。