最小生成树 高频追问 Q&A
1. Q: MST 和最短路径树区别？
A: MST 最小化总边权；最短路径树最小化源点到各点距离。
2. Q: Kruskal 和 Prim 怎么选？
A: Kruskal 适合边集处理（常配并查集），Prim 常用于稠密图。
3. Q: 图不连通怎么办？
A: 无法形成 MST，通常返回 -1 或构成最小生成森林。
4. Q: MST 是否唯一？
A: 不一定。存在同权边时可能有多个 MST。
5. Q: Kruskal 复杂度是多少？
A: 主要瓶颈是排序，O(E log E)。
6. Q: 现实应用怎么说？
A: 网络布线、道路建设、聚类预处理等最小成本连接问题。