最小生成树 高频追问 Q&A

最小生成树 高频追问 Q&A

1. Q: MST 和最短路径树区别？

A: MST 最小化总边权；最短路径树最小化源点到各点距离。（深入阅读：最小生成树基础知识速览）

2. Q: Kruskal 和 Prim 怎么选？

A: Kruskal 适合边集处理（常配并查集），Prim 常用于稠密图。（深入阅读：Kruskal 的并查集实现、Prim 的堆优化实现）

3. Q: 图不连通怎么办？

A: 无法形成 MST，通常返回 -1 或构成最小生成森林。（深入阅读：最小生成树基础知识速览）

4. Q: MST 是否唯一？

A: 不一定。存在同权边时可能有多个 MST。（深入阅读：最小生成树基础知识速览）

5. Q: Kruskal 复杂度是多少？

A: 主要瓶颈是排序，O(E log E)。（深入阅读：Kruskal 的并查集实现）

6. Q: 现实应用怎么说？

A: 网络布线、道路建设、聚类预处理等最小成本连接问题。（深入阅读：最小生成树基础知识速览）