7.2 路径、连通、树与最短路：不同权重需要不同算法
从变量村到安全要塞有多条路线，距离、时间和费用给出的“最短路”并不相同。
导航中的“最短”可能指距离、时间、费用或换乘次数。选算法之前，要先确定路径成本怎样累加、边权能否为负、图是否有向，以及需要一个源点还是所有点对。
Walk、Trail、Path 和 Cycle
术语约定在教材间略有差异，本课采用：
- Walk（游走）：相邻顶点由边连接，可重复顶点和边；
- Trail（迹）：不重复边；
- Path（简单路径）：不重复顶点；
- Cycle（环）：起点终点相同，内部顶点不重复。
算法中常把一般顶点序列也口语称作 path。证明时应说明是否允许重复。
路径长度在无权图中常指边数；带权图中路径权重是沿途边权之和。
连通分量
无向图中，若任意两点间都有路径，图连通。可达关系是等价关系，其等价类就是连通分量。
有向图区分：
- 强连通：任意
u,v都能互相到达； - 弱连通：忽略方向后连通。
单向可达不等于强连通。服务 A 调用 B，B 不必能调用 A。
树的等价刻画
有限无向图是树，以下性质等价：
- 连通且无环；
- 任意两顶点间恰有一条简单路径；
- 连通且有
|V|-1条边； - 无环且有
|V|-1条边； - 删除任意边都会不连通；
- 加入任意一条新边都会产生唯一环。
这些等价性质让证明可以选择最方便的入口。
树指定根后产生父子、深度和子树结构；无根树本身没有天然“上方”。文件目录通常按根树理解，但硬链接、符号链接和挂载会破坏简单树模型。
生成树与最小生成树
连通无向图的生成树包含全部顶点，并从原图选择 |V|-1 条边保持连通。
带权图的最小生成树（MST）使总边权最小。它优化的是“连接所有顶点的总成本”，不是任意两点间的最短路径。
Kruskal
- 按边权从小到大排序；
- 依次加入不会形成环的边；
- 用并查集维护连通分量。
Prim
- 从一个顶点开始维护当前树；
- 每次加入跨越当前树与外部的最小权边；
- 用优先队列维护候选边。
二者正确性可由割性质说明：跨越某个割的最轻边在适当条件下是安全选择。边权相同可能产生多棵不同但总权重相同的 MST。
MST 通常针对无向图。网络布线若要求方向、可靠性冗余或容量，普通 MST 模型可能过弱。
无权最短路：BFS
每条边成本相同，BFS 按距离层访问：
第 0 层：源点
第 1 层：一条边可达
第 2 层：两条边可达
...第一次发现顶点时，任何更短路径都应在更早层发现，因此得到最少边数路径。
边权为 0 或 1 时，可使用双端队列的 0-1 BFS；普通 FIFO BFS 不再足够。
非负权最短路：Dijkstra
Dijkstra 维护暂定距离：
dist[s]=0
其他 dist=∞每次从优先队列取暂定距离最小的顶点，并松弛出边：
if dist[v]+w(v,u)<dist[u]:
dist[u]=dist[v]+w(v,u)
parent[u]=v算法正确性依赖边权非负：当最小暂定顶点被确定时，绕经尚未确定顶点的路径不可能再把它变短。
有负边时，这个贪心结论失效。即使某些实现偶尔给出正确结果，也没有一般保证。
邻接表配二叉堆的常见复杂度：
O((V+E) log V)具体取决于优先队列实现和是否支持 decrease-key。常见工程实现重复入队，取出陈旧条目时跳过。
负边与负环：Bellman–Ford
Bellman–Ford 对全部边重复松弛，能处理负权边，并检测从源点可达的负环。
若存在可达负环，沿环反复走可使路径权重无限降低，“最短路径”没有有限解。
典型复杂度：
O(VE)比 Dijkstra 慢，但模型能力不同。选择算法不能只按跑分，还要按边权假设。
DAG 最短路
有向无环图可按拓扑序处理顶点，每条边只需松弛一次：
O(V+E)DAG 即使有负边也不会有负环，因此算法仍可工作。任务成本、流水线关键路径常适合这一模型。
所有点对与多目标成本
若需要所有点对最短路，可考虑 Floyd–Warshall O(V³) 或多次单源算法，选择取决于稠密度、负边和图规模。
现实导航常有多个目标：时间、费用、风险。把它们强行加成一个权重需要业务给出可解释的换算；否则应寻找 Pareto 前沿，而不是宣称存在唯一“最短”。
边权若随时间变化，静态最短路也可能失效。FIFO 时间依赖、等待和实时更新需要专门模型。
完成检查
- 证明树有
|V|-1条边； - 对同一带权图手工执行 Kruskal 和 Prim；
- 构造负边使 Dijkstra 失败的例子；
- 用 Bellman–Ford 判断一个负环是否从源点可达；
- 为 DAG 计算最短路和最长关键路径；
- 说明 MST 与从总部到每个站点的最短路树为何不同。