13.4.5 最小生成树与最短路径问题

课程对这一节的要求是“了解算法名称和策略”，不要求像算法课那样完整推导每一步。但最小生成树和最短路径非常容易混淆，必须先把目标区分开。

两类问题的本质差别

问题	目标	适用图	结果
最小生成树 MST	用最小总代价连接所有顶点	连通无向带权图	一棵包含全部顶点的树
最短路径	从一个点到另一个点代价最小	带权图	一条或多条路径

最小生成树关注“全网建设成本最小”；最短路径关注“两点之间走哪条路最省”。

生成树的性质

若图有 $n$ 个顶点，生成树必须：

1. 包含全部 $n$ 个顶点。
2. 有 $n-1$ 条边。
3. 连通。
4. 无回路。

如果边数达到 $n$ 且仍连通，必然有回路；如果少于 $n-1$ 条边，不可能连接所有顶点。

Prim 与 Kruskal

算法	思路	更像什么
Prim	从一个顶点集合开始，每次选连接集合内外的最小边	“从一个城市向外扩网”
Kruskal	把所有边按权值从小到大考虑，不成环就加入	“先买最便宜的路，但不能形成圈”

两者都是贪心策略：每一步选择当前看起来最优的边，并维持生成树条件。

Dijkstra 与 Floyd

算法	解决问题	策略
Dijkstra	单源最短路径	每次确定当前距离最小的未确定顶点
Floyd	任意两点最短路径	枚举中转点，不断改进两点间距离

课程中最短路径例题通过比较若干路径代价，最终选出花费最小路径。真正考试中目前更常见的是问这些算法属于什么策略，例如贪心。

技术取舍

算法	优点	局限
Prim	适合稠密图，按顶点集合扩展	需要维护集合外最小连接边
Kruskal	适合稀疏图，按边排序直观	要检查是否成环
Dijkstra	单源最短路径高效	不适合负权边的常规版本
Floyd	一次求所有顶点对	时间复杂度较高，适合顶点数较小

本节例题

单选

关于最小生成树与最短路径，下列说法正确的是：

A最小生成树保证任意两点路径最短B最短路径必须包含所有顶点C生成树可以有回路DPrim 和 Kruskal 都可用于求最小生成树

自查清单

1. 能否区分“连接所有顶点成本最小”和“两点之间路径最短”？
2. 能否说出 Prim、Kruskal、Dijkstra、Floyd 分别解决什么问题？
3. 能否解释 Kruskal 为什么必须检查回路？