第 10 讲 · 图、遍历与网络算法

图 $G=(V,E)$ 用顶点集合表示对象，用边集合表示对象之间的关系。无向边表示对称关系，有向边表示方向；权值可以代表距离、时间或成本。

基本概念

• 路径是首尾相接的边序列，简单路径不重复顶点；
• 回路首尾顶点相同；
• 无向图中两点有路径就称连通；极大连通子图是连通分量；
• 有向图中任意两点互相可达称强连通；
• 无向图顶点的度是关联边数；有向图分入度和出度；
• 含 $n$ 个顶点的连通无向图至少有 $n-1$ 条边。

邻接矩阵与邻接表

邻接矩阵用 $|V|\times|V|$ 数组保存边。判断两点是否直接相连为 $O(1)$，但空间固定为 $O(|V|^2)$，适合稠密图。

邻接表为每个顶点保存出边链表，空间 $O(|V|+|E|)$，适合稀疏图。无向边会在两个顶点的表中各出现一次；有向图的表长直接反映出度。

课程还介绍有向图十字链表和无向图邻接多重表，用来让同一条边同时便于从两个端点访问。

DFS：一路深入再回退

从顶点出发，标记已访问，再递归访问每个未访问邻接点。已访问标记防止在环中无限重复。

若图不连通，只从一个起点无法遍历全部顶点，还要从每个未访问顶点重新启动，得到 DFS 森林。

BFS：逐层扩展

起点标记并入队；反复出队一个顶点，把其所有未访问邻接点标记并入队。标记应在入队时完成，否则同一顶点可能被重复加入。

无权图中，BFS 第一次到达顶点时所用边数最少，因此可求单源最短路。

采用邻接表时，DFS 和 BFS 都是 $O(|V|+|E|)$；采用邻接矩阵时，需要为每个顶点扫描一整行，是 $O(|V|^2)$。

最小生成树

连通无向图的生成树包含全部顶点和恰好 $|V|-1$ 条边。带权图中总边权最小的生成树称最小生成树。

Prim

维护已选顶点集合 $U$。每次挑选一条连接 $U$ 与 $V-U$ 的最轻边，把新顶点加入 $U$。不变量是当前边集始终是一棵连接 $U$ 的树。

Kruskal

把边按权从小到大考虑，若加入当前边不会形成环，就选取它。并查集可以高效判断两个端点是否已经在同一连通分量。

Prim 更围绕顶点展开，邻接矩阵实现适合稠密图；Kruskal 围绕边展开，常适合稀疏图。

Dijkstra 单源最短路径

维护起点到各顶点的当前最短估计 dist。每轮从未确定顶点中选 dist 最小者 $u$，把它标记为已确定，再用边 $(u,v)$ 松弛：

$$dist[v]=\min(dist[v],dist[u]+w(u,v)).$$

不变量是：所有已确定顶点的 dist 已是最终最短距离。这个证明依赖边权非负；有负权边时，后来经过负边的路径可能推翻已经确定的结果。

Floyd-Warshall 则通过逐步允许更多中间顶点，计算任意两点最短路，时间 $O(|V|^3)$。

AOV 网与拓扑排序

AOV 网用顶点表示活动，用有向边表示先后约束。拓扑排序反复选择入度为零的顶点输出，并删除其出边。

若输出数少于顶点数，说明剩余部分存在有向环，工程依赖无法完成。拓扑序通常不唯一：两个活动没有先后约束时，交换次序仍合法。

AOE 网与关键路径

AOE 网用边表示活动，顶点表示事件，边权是活动持续时间。完成整个工程所需的最短时间等于源点到汇点的最长路径长度。

沿拓扑序计算事件最早发生时间 ve；逆拓扑序计算最迟发生时间 vl。活动的最早开始与最迟开始相等时没有机动时间，是关键活动；关键活动组成关键路径。

缩短非关键活动不一定缩短总工期；缩短关键活动才可能有效，而且缩短后关键路径可能改变。

不要混淆三个“最小”

• 最小生成树：让连接全部顶点的总边权最小；
• 单源最短路树：让源点到各点的路径分别最短；
• BFS 树：只在无权图中保证源点到各点边数最少。

它们的目标函数不同，得到的树不必相同。