算法设计-04：图算法

图与表示

图 $G=(V,E)$ 由顶点集 $V$ 和边集 $E$ 组成。无向边可以沿两个方向走；有向边 $(u,v)$ 只能从 $u$ 走向 $v$。记 $n=|V|$、$m=|E|$。本篇合并第六讲的图分解与第七讲的路径算法，先研究哪些顶点可以互相到达，再研究到达它们的最短距离。

课件中的线性时间 $O(n+m)$ 采用邻接表：对每个顶点存储其邻居或出边，遍历全图只需扫描全部顶点和全部邻接表。无向边通常在两个端点的表中各存一次；有向边只存入起点的出边表。若改用邻接矩阵，每次找邻居可能需要扫描一整行，同样的遍历实现就可能花 $O(n^2)$ 时间。

深度搜索

深度优先搜索（DFS）沿尚未访问的邻居不断深入，当前顶点的邻居都处理完后再返回。课件先给出从单个顶点出发的 EXPLORE，其中 PREVISIT、POSTVISIT 分别在进入和离开顶点时执行，后文会用它们记录分量编号与访问时刻。

$$\begin{array}{l} \hline \textbf{算法：EXPLORE}(G,v) \\[4pt] \hline visited[v]=\text{true} \\ \text{PREVISIT}(v) \\ \textbf{for}\ u\in\operatorname{Adj}(v)\ \textbf{do} \\ \qquad\textbf{if}\ \neg visited[u]\ \textbf{then}\ \text{EXPLORE}(G,u) \\ \text{POSTVISIT}(v) \\ \hline \end{array}$$

正确性：若所有顶点初始均未访问，EXPLORE$(G,v)$ 恰好访问从 $v$ 可达的顶点。

每次递归都沿图中的边前进，因此新访问的顶点一定从 $v$ 可达。反过来，若有可达顶点没有被访问，取一条从 $v$ 到它的路径，找到路径上第一个未访问的顶点 $u$。其前驱已被访问，扫描前驱的邻接表时应当递归访问 $u$，产生矛盾。

单次 EXPLORE 不一定覆盖全图，因此完整 DFS 还需要外层循环：

$$\begin{array}{l} \hline \textbf{算法：DFS}(G) \\[4pt] \hline \textbf{for}\ v\in V\ \textbf{do}\ visited[v]=\text{false} \\ \textbf{for}\ v\in V\ \textbf{do} \\ \qquad\textbf{if}\ \neg visited[v]\ \textbf{then}\ \text{EXPLORE}(G,v) \\ \hline \end{array}$$

每个顶点只进入 EXPLORE 一次，标记和访问钩子的总代价是 $O(n)$。全部邻接表扫描的总代价是 $O(m)$：有向边扫描一次，无向边扫描两次。因此 DFS 时间为 $O(n+m)$，辅助数组与递归栈共需 $O(n)$ 空间。

连通分量

无向图中，若任意两个顶点之间都有路径，图就连通。连通分量是极大的连通顶点集合，分量之间没有边。从一个顶点运行 EXPLORE 恰好找出它所在的分量；完整 DFS 外层循环每次启动新的 EXPLORE，就开始处理一个新分量。

给每个顶点记录 ccnum[v]，可在 PREVISIT 中令 ccnum[v]=cc，并在 DFS 外层每次启动搜索前把 cc 加 1。最后 cc 是分量数；两个顶点的编号相同，当且仅当它们在同一个分量中。非空无向图连通，当且仅当分量数为 1。

递归第一次发现新顶点时使用的边构成DFS 树边，多次搜索则得到 DFS 森林。无向图其余的非树边连接一个顶点与它的祖先，称为后向边。若一条非树边连接两个互不为祖先的分支，较早被搜索的分支会沿这条边发现另一端，使另一端成为其后代，故这种情况不能发生。扫描无向树边的反方向时，应将它识别为同一条树边。

第六讲最初的 12 点无向例图有两个分量：$A$ 到 $J$ 组成一个分量，$K,L$ 组成另一个分量。按课件所示的访问顺序，$A-C$、$E-J$、$D-H$ 是连接祖先与后代的非树边；完整 DFS 还需从未访问的 $K$ 或 $L$ 启动第二棵树。

练习 3.11：给定无向图 $G$ 及其中一条指定边 $e$，设计线性时间算法，判断是否存在包含 $e$ 的环。

本题考查搜索可达性，以及边位于环上与删边后端点仍连通的等价关系。

设 $e=\{u,v\}$。从 $u$ 开始运行一次 DFS 或 BFS，扫描邻接表时跳过指定的边 $e$，即在 $G-e$ 中搜索。若能到达 $v$，则返回“存在”；否则返回“不存在”。

伪代码将邻接表项写成 $(v,f)$，分别表示邻点和边的标识；同一无向边的两个邻接表项共享标识，因而可以准确跳过指定边 $e$。

// 在忽略指定边 e 后检查其两个端点是否仍然连通。
function CYCLE-THROUGH-EDGE(G = (V, E), e = {s, t}):
    for each v in V:
        visited[v] ← FALSE
    visited[s] ← TRUE
    Q ← 空队列
    ENQUEUE(Q, s)
    while Q is not empty:
        u ← DEQUEUE(Q)
        for each (v, f) in Adj(u):
            if f = e:
                continue
            if visited[v] = FALSE:
                visited[v] ← TRUE
                ENQUEUE(Q, v)
    return visited[t]

正确性由以下等价关系得到：

$$e\text{ 位于某个环上} \iff G-e\text{ 中存在从 }u\text{ 到 }v\text{ 的路径}.$$

若存在包含 $e$ 的环，删掉 $e$ 后剩余部分就是一条 $u$ 到 $v$ 的路径。反过来，搜索树给出一条不含 $e$ 的简单 $u$ 到 $v$ 路径，将它与 $e$ 合起来便得到一个环。

搜索只需 $O(|V|+|E|)$ 时间和 $O(|V|)$ 额外空间，无须实际复制或修改图。这也等价于判断 $e$ 是否不是桥。

访问时刻

令全局计数器 clock 从 1 开始。在 PREVISIT 中记录 pre[v]=clock，在 POSTVISIT 中记录 post[v]=clock，每记录一次就将计数器加 1。每个顶点有一个进入时刻和一个退出时刻，整个搜索共得到 $2n$ 个不同编号。

课件图中的三个分量分别由 $A$、$C$、$F$ 启动搜索：$A$ 的区间是 $[1,10]$，$C$ 是 $[11,22]$，孤立顶点 $F$ 是 $[23,24]$。在第一棵树里，$E$ 的区间 $[4,9]$ 包含 $I$ 的 $[5,8]$，后者又包含 $J$ 的 $[6,7]$；$B$ 的 $[2,3]$ 与这些区间互不相交。

区间引理：任意两个顶点的访问区间，要么互不相交，要么一个严格包含另一个。

若 $v$ 在 $u$ 的递归调用尚未结束时被发现，那么访问 $v$ 的递归必须先结束，随后才能结束 $u$；$v$ 的区间因此被 $u$ 包含。若发现 $v$ 时 $u$ 已结束，两个区间就互不相交。区间相互交错的情况不能发生。

于是可以从时刻判断祖先关系。若 $v$ 是 $u$ 的严格后代，则

$$pre[u]<pre[v]<post[v]<post[u].$$

边的分类

有向图的 DFS 仍然得到搜索森林，但非树边可以有更多类型：树边属于搜索森林；前向边指向非孩子的后代；后向边指向祖先；交叉边连接互不为祖先的顶点。根、父亲、孩子、祖先、后代都相对于本次 DFS 森林而言，访问顺序不同，分类也可能不同。

图中 $A$ 为根，树边包括 $A\to B$、$B\to E$、$E\to F$、$F\to G$、$E\to H$、$A\to C$、$C\to D$。$F\to B$ 与 $D\to A$ 是后向边，$A\to F$ 与 $E\to G$ 是前向边，$H\to G$ 与 $D\to H$ 是交叉边。对应时刻为 $A:(1,16)$、$B:(2,11)$、$E:(3,10)$、$F:(4,7)$、$G:(5,6)$、$H:(8,9)$、$C:(12,15)$、$D:(13,14)$。

记 $p(u)=pre[u]$、$q(u)=post[u]$，对边 $(u,v)$，课件中的区间判别可写为：

类型	时刻关系
树边或前向边	$p(u)<p(v)<q(v)<q(u)$
后向边	$p(v)<p(u)<q(u)<q(v)$
交叉边	$p(v)<q(v)<p(u)<q(u)$

时刻关系不能单独区分树边与前向边，还需看 parent[v] 是否为 $u$。自环 $u\to u$ 也构成回到当前搜索栈顶点的后向边，需单独处理相同端点。

课件提问：上述区间排列是否已经穷尽？

对端点不同的有向边，是的。区间交错已被区间引理排除；剩下的“$u$ 已结束后才发现 $v$”也不可能，因为扫描 $u\to v$ 时若 $v$ 未访问，DFS 就会立即发现它。因此交叉边只能从后搜索的区间指向先结束的区间。

拓扑排序

有向无环图（DAG）不含有向环。课件中的 DAG 可以表示任务依赖：一条边 $u\to v$ 表示必须先完成 $u$，再完成 $v$。

环判定：有向图有环，当且仅当 DFS 出现后向边。

若有后向边 $u\to v$，DFS 树中从祖先 $v$ 到后代 $u$ 的路径与这条边组成有向环。反过来，在一个有向环中取最先被发现的顶点 $v$；DFS 能从它到达环上其他顶点，并在 $v$ 退出前发现一条回到仍在递归栈中的顶点的边，因此会出现后向边。

实现时可把顶点分为未访问、搜索中、已结束三种状态；扫描到指向“搜索中”顶点的边，就发现了环。

拓扑排序把全部顶点排列成一个序列，使每条边都从较早的顶点指向较晚的顶点。DAG 的每条边 $(u,v)$ 都满足 $post[u]>post[v]$：树边和前向边指向更早结束的后代，交叉边指向已经结束的顶点，后向边则被无环条件排除。因此按退出时刻递减排列，即得到拓扑序。

图中边为 $B\to A$、$B\to D$、$A\to C$、$D\to C$、$C\to E$、$C\to F$。合法拓扑序包括 $B,A,D,C,E,F$ 和 $B,D,A,C,F,E$；$A$ 与 $D$、$E$ 与 $F$ 的先后没有被边约束。

课件提问：哪些 DAG 可以线性化？

所有有限 DAG 都可以。反过来，若有有向环，环上每个顶点都必须先于下一个顶点，无法形成线性序列。无环、存在拓扑序、DFS 没有后向边三者等价。

不必真的对退出时刻排序：在 POSTVISIT 时把顶点追加到列表，最后反转列表即可，时间仍是 $O(n+m)$。若检测到后向边，应报告有环，而不能把逆退出序当成有效拓扑序。

非空 DAG 至少有一个源点（入度为 0）和一个汇点（出度为 0）。若每个顶点都有入边，不断沿入边逆向追溯，有限顶点迫使某个顶点重复，从而形成环；汇点的证明对出边同理。拓扑序的第一个顶点必为源点，最后一个必为汇点。

另一种拓扑排序是反复输出源点并删除它，即 Kahn 算法。先计算所有入度，把入度为 0 的顶点入队；弹出顶点 $u$ 时，将其每个邻居的入度减 1，新变为 0 的顶点入队。每条边只处理一次，所以同样是 $O(n+m)$。若最终输出少于 $n$ 个顶点，剩余部分包含有向环。

强连通分量

有向图中，仅有 $u$ 能到达 $v$ 还不够。若 $u$ 能到达 $v$，同时 $v$ 也能到达 $u$，称二者互相可达。这个关系具有自反性、对称性和传递性，因而把顶点划分成互不相交的强连通分量（SCC）。单个顶点也可以构成一个 SCC。

把每个 SCC 收缩成一个顶点，保留不同分量之间的边，得到缩点图。缩点图一定是 DAG：若几个不同分量在缩点图中形成环，它们就可以沿这个环互相到达，应属于同一个分量，产生矛盾。

课件例子共有五个 SCC：$\{A\}$、$\{B,E\}$、$\{C,F\}$、$\{D\}$、$\{G,H,I,J,K,L\}$。下方六个顶点通过 $G\to H\to K\to L\to J\to I\to G$ 互相可达，属于同一分量。缩点后 $\{A\}$ 是源分量，$\{D\}$ 与下方六点组成的分量是汇分量。

从一个汇 SCC 内的顶点运行 EXPLORE，不会走到别的分量，恰好得到这个 SCC。于是算法的关键变成：如何找到汇 SCC，再如何依次处理剩余分量？

退出时刻引理：若不同 SCC $C,C'$ 之间有边 $C\to C'$，则 $C$ 的最大退出时刻大于 $C'$ 的最大退出时刻。

若 DFS 先进入 $C$，它能到达 $C'$，后者会在这次递归结束前全部完成。若先进入 $C'$，则它不能到达 $C$，否则两者应属于同一 SCC；因此 $C'$ 会先结束，之后才发现 $C$。两种情况都得到引理。故全图最大退出时刻所在的分量是源 SCC，尚不能直接作为原图中的汇分量。

令 $G^R$ 为把全部边反向后的图。反向不改变互相可达关系，所以 $G$ 与 $G^R$ 的 SCC 完全相同；原图中的汇 SCC 则成为反向图中的源 SCC。先在 $G^R$ 上做 DFS，就能用最大退出时刻找到原图的汇分量。

Kosaraju 算法采用两遍搜索：

$$\begin{array}{l} \hline \textbf{算法：SCC}(G) \\[4pt] \hline \text{构造反向图 }G^R \\ \text{在 }G^R\text{ 上执行 DFS，按退出先后记录列表 }L \\ \text{将原图所有顶点重置为未访问，令 }cc=0 \\ \textbf{for}\ v\in\operatorname{reverse}(L)\ \textbf{do} \\ \qquad\textbf{if}\ \neg visited[v]\ \textbf{then} \\ \qquad\qquad cc=cc+1 \\ \qquad\qquad\text{在 }G\text{ 上从 }v\text{ 执行 EXPLORE} \\ \qquad\qquad\text{给本次新访问的全部顶点标记分量 }cc \\ \hline \end{array}$$

第二遍搜索每次选取尚未访问顶点中，反向图退出时刻最大的顶点。它属于剩余原图的汇 SCC；已处理分量用 visited 跳过，效果等同于删除它们。归纳可得每次搜索恰好输出一个 SCC。构造反向图、两遍 DFS、反转退出列表均为 $O(n+m)$，因此总时间为 $O(n+m)$。课件例子可以先处理两个汇分量，再处理 $\{C,F\}$、$\{B,E\}$，最后处理 $\{A\}$；两个汇分量的具体先后取决于第一遍访问顺序。

思考：图非常巨大时，SCC 算法如何工作？

内存能容纳邻接表时，仍然按 $O(n+m)$ 分析，但长链上的递归可能耗尽调用栈，可用显式栈记录顶点和下一条待扫描边。两遍搜索还需要反向邻接表。若图不能放入内存，磁盘读取、反向边组织与跨机器通信就成为主要代价，需要面向这些限制设计实现，不能仅凭 RAM 模型的线性时间推断实际速度。

思考：把“路径”换成“边”会怎样？

若按字面把互相可达改成“两个顶点间互有直接边”，关系不再传递：$u\leftrightarrow v$、$v\leftrightarrow w$ 不能推出 $u\leftrightarrow w$，所以不能像 SCC 一样自动划分成等价类。若问题指的是“删除一条边后仍能连通”，则是边连通性问题，需要另外分析桥或边连通分量。

练习 3.28：2SAT 的每个子句是两个文字的析取（逻辑或）；文字是一个布尔变量或它的否定。要求为每个变量赋真或假，使所有子句都至少有一个真文字。考虑下面的实例：

$\Phi=(x_1\lor\overline{x_2})\land(\overline{x_1}\lor\overline{x_3})\land(x_1\lor x_2)\land(\overline{x_3}\lor x_4)\land(\overline{x_1}\lor x_4)$.

该实例的一个满足赋值为 $(x_1,x_2,x_3,x_4)=(1,0,0,1)$，其中 $1$ 表示真，$0$ 表示假。

本题考查逻辑蕴含的建图、强连通分量、缩点 DAG 和拓扑序赋值。

(a) 这个公式是否还有其他满足赋值？若有，找出全部满足赋值。

第一、第三个子句同时成立要求

$$(x_1\lor\overline{x_2})\land(x_1\lor x_2) \equiv x_1,$$

故 $x_1=1$。第二个子句随后要求 $x_3=0$，第五个要求 $x_4=1$；第四个此时自动成立，$x_2$ 可任取。因此全部满足赋值恰为

$$(x_1,x_2,x_3,x_4)\in\{(1,0,0,1),(1,1,0,1)\}.$$

除题目已给出的赋值外，只有 $(1,1,0,1)$。

(b) 给出一个包含四个变量、没有满足赋值的 2SAT 实例。

取

$$\Psi=(x_1\lor x_2)\land(x_1\lor\overline{x_2}) \land(\overline{x_1}\lor x_2)\land(\overline{x_1}\lor\overline{x_2}) \land(x_3\lor x_4).$$

前两个子句的合取等价于 $x_1$，接着两个子句的合取等价于 $\overline{x_1}$，故 $\Psi$ 不可满足。四个变量均在公式中出现。

本题通过强连通分量求解 2SAT。对含 $n$ 个变量、$m$ 个子句的实例 $I$，构造有向蕴含图 $G_I=(V,E)$：

$G_I$ 有 $2n$ 个顶点，每个变量及其否定各对应一个顶点。

$G_I$ 有 $2m$ 条边：每个子句 $(\alpha\lor\beta)$ 对应两条边 $\overline\alpha\to\beta$ 和 $\overline\beta\to\alpha$。

子句 $(\alpha\lor\beta)$ 分别等价于蕴含式 $\overline\alpha\Rightarrow\beta$ 和 $\overline\beta\Rightarrow\alpha$，所以该图记录了公式中的蕴含关系。

© 分别为题目给出的实例和 (b) 中构造的实例建立蕴含图。

两图的顶点集均为

$$V=\{x_1,\overline{x_1},x_2,\overline{x_2}, x_3,\overline{x_3},x_4,\overline{x_4}\}.$$

$G_\Phi$ 的边逐子句列为

$$\begin{aligned} (x_1\lor\overline{x_2})&:\quad \overline{x_1}\to\overline{x_2},\quad x_2\to x_1,\\ (\overline{x_1}\lor\overline{x_3})&:\quad x_1\to\overline{x_3},\quad x_3\to\overline{x_1},\\ (x_1\lor x_2)&:\quad \overline{x_1}\to x_2,\quad\overline{x_2}\to x_1,\\ (\overline{x_3}\lor x_4)&:\quad x_3\to x_4,\quad\overline{x_4}\to\overline{x_3},\\ (\overline{x_1}\lor x_4)&:\quad x_1\to x_4,\quad\overline{x_4}\to\overline{x_1}. \end{aligned}$$

$G_\Psi$ 的边为

$$\begin{aligned} (x_1\lor x_2)&:\quad \overline{x_1}\to x_2,\quad\overline{x_2}\to x_1,\\ (x_1\lor\overline{x_2})&:\quad \overline{x_1}\to\overline{x_2},\quad x_2\to x_1,\\ (\overline{x_1}\lor x_2)&:\quad x_1\to x_2,\quad\overline{x_2}\to\overline{x_1},\\ (\overline{x_1}\lor\overline{x_2})&:\quad x_1\to\overline{x_2},\quad x_2\to\overline{x_1},\\ (x_3\lor x_4)&:\quad \overline{x_3}\to x_4,\quad\overline{x_4}\to x_3. \end{aligned}$$

$G_\Phi$ 的每个 SCC 都是单个顶点；$G_\Psi$ 则有一个 SCC 为 $\{x_1,\overline{x_1},x_2,\overline{x_2}\}$，其余四个顶点各自构成一个 SCC。

(d) 证明：若 $G_I$ 的某个强连通分量同时包含某个变量 $x$ 及其否定 $\overline x$，则 $I$ 不可满足。

满足赋值必须满足图中每条蕴含边，因此真值会沿有向路径传递。若 $x$ 和 $\overline{x}$ 在同一个 SCC 中，则

$$x\leadsto\overline{x},\qquad\overline{x}\leadsto x.$$

若 $x$ 为真，第一条路径强制 $\overline{x}$ 为真；若 $x$ 为假，则 $\overline{x}$ 为真，第二条路径强制 $x$ 为真。两种选择均矛盾，因此无满足赋值。

(e) 证明 (d) 的逆命题：若没有任何强连通分量同时包含一个文字及其否定，则 $I$ 可满足。提示：反复选取剩余图的一个汇强连通分量，将其中的文字设为真、它们的否定设为假，并删除这些顶点；证明这样可以得到满足赋值。

对每条边 $\ell\to r$，图中同时存在逆否边 $\overline r\to\overline\ell$。因此，若两个文字互相可达，它们的否定也互相可达。一个 SCC $C$ 中所有文字的否定恰好构成另一个 SCC，记为 $\overline C$。题设保证 $C\ne\overline C$。

将 SCC 缩点得到 DAG，并取一个拓扑序。令 $t(C)$ 为分量 $C$ 在该序中的编号，编号沿分量间的边严格增加。对每个文字 $\ell$，规定

$$\ell\text{ 为真} \iff t(C(\ell))>t(C(\overline\ell)).$$

其中 $C(\ell)$ 表示包含 $\ell$ 的分量。两个编号不同，所以一个变量与其否定恰好一个为真；同一 SCC 内的文字也获得相同真值。

若某条边 $\ell\to r$ 的起点为真、终点为假，拓扑序与逆否边给出

$$t(C(\overline\ell)) <t(C(\ell)) \le t(C(r)) <t(C(\overline r)) \le t(C(\overline\ell)),$$

矛盾。因此没有蕴含边从真指向假。若某个子句 $(\alpha\lor\beta)$ 不满足，就会有 $\overline\alpha$ 为真、$\beta$ 为假，与边 $\overline\alpha\to\beta$ 不被违反矛盾。故所有子句都满足。

这也实现了提示中的汇分量构造：按拓扑序从后向前处理尚未赋值的分量，将它设为真、将其否定分量设为假，已赋值的分量直接跳过。

(f) 据此给出线性时间的 2SAT 求解算法。

先为每个子句加入两条蕴含边，再用 Kosaraju 或 Tarjan 算法一次性求出所有 SCC。若某个 $x_i$ 与 $\overline{x_i}$ 在同一分量，报告不可满足；否则构造缩点 DAG、求拓扑序，并按 (e) 的规则赋值。

伪代码中，SCC 返回每个文字的分量编号 comp，拓扑排序按从源到汇的顺序排列分量。缩点时可保留重边，拓扑排序按实际边数统计入度，无须额外排序去重。

// 建立蕴含图、检查矛盾并生成满足赋值；¬ 表示文字取反。
function SOLVE-2SAT(n, clauses):
    G ← 顶点集为 {x_i, ¬x_i : 1 ≤ i ≤ n} 的空有向图
    for each clause (α ∨ β) in clauses:
        ADD-EDGE(G, ¬α, β)
        ADD-EDGE(G, ¬β, α)

    comp ← SCC(G)
    for i ← 1 to n:
        if comp[x_i] = comp[¬x_i]:
            return UNSAT

    H ← 每个分量对应一个顶点的空有向图
    for each edge (u, v) in E(G):
        if comp[u] ≠ comp[v]:
            ADD-EDGE(H, comp[u], comp[v])

    order ← TOPOLOGICAL-SORT(H)
    for j ← 1 to length(order):
        t[order[j]] ← j
    for i ← 1 to n:
        value[x_i] ← (t[comp[x_i]] > t[comp[¬x_i]])
    return (SAT, value)

图有 $2n$ 个顶点和 $2m$ 条边，建图、求 SCC、检查矛盾、拓扑排序和生成赋值均在线性时间内完成。因此

$$T(n,m)=O(n+m),\qquad S(n,m)=O(n+m).$$

无需每删除一个汇分量就重新计算 SCC。

分解练习

练习 3.16：所有课程必修，先修关系用 DAG 表示，一学期可选任意多门课。如何在线性时间内计算最少学期数？

对图拓扑排序。令 sem[v] 表示最早可修 $v$ 的学期，初始均为 1；按拓扑序扫描每条边 $u\to v$，把 sem[v] 更新为 sem[v] 和 sem[u]+1 中较大的值。所有前驱都处理完后，$v$ 的值就是最早学期；答案为所有 sem[v] 的最大值。时间 $O(n+m)$。

正确性来自先修约束：$v$ 至少要比每个前驱晚一学期；反过来，在最大前驱学期之后选修 $v$ 已满足全部约束。图中的最长有向路径若含 $k$ 个顶点，就至少需要 $k$ 学期，这个安排恰好达到下界。上面的课件 DAG 需四学期：$B$；$A,D$；$C$；$E,F$。若先修图有环，则没有有限学期安排能完成所有课程。

练习 3.22：判断有向图中是否存在一个顶点，能到达所有其他顶点。

在 DFS 外层循环中记住最后一次启动 EXPLORE 的顶点 $r$，然后重新清空访问标记，从 $r$ 再搜索一次；若覆盖全图，答案为存在，否则不存在。两遍搜索总时间 $O(n+m)$。

若图没有顶点，直接返回不存在；单个顶点则自然满足条件。

若这样的顶点 $s$ 存在，考虑第一次访问它的 DFS 树：若它是某棵树的后代，那么树根能到达 $s$，进而到达所有顶点；若它自己是根，同样如此。此后不会再有新的 DFS 根，所以最后一棵树的根必能到达全图。第二遍负责验证候选者，避免没有解的图被误判。

从缩点图看，这也等价于存在唯一的源 SCC。DAG 中每个顶点都可追溯到某个源点；源点唯一时，它就能到达全部分量，该源 SCC 中任一顶点都是答案。课件的 SCC 例子中，$A$ 满足条件。

广度搜索

在无权图中，路径长度是边数；$s$ 到 $v$ 的距离 $\delta(s,v)$ 是所有这类路径中的最小边数，不可达时记为 $\infty$。广度优先搜索（BFS）使用先进先出的队列，按距离层次依次处理顶点。

$$\begin{array}{l} \hline \textbf{算法：BFS}(G,s) \\[4pt] \hline \textbf{for}\ v\in V\ \textbf{do}\ dist[v]=\infty,\ prev[v]=\text{nil} \\ dist[s]=0,\ Q=[s] \\ \textbf{while}\ Q\ne[\ ]\ \textbf{do} \\ \qquad u=\text{EJECT}(Q) \\ \qquad\textbf{for}\ v\in\operatorname{Adj}(u)\ \textbf{do} \\ \qquad\qquad\textbf{if}\ dist[v]=\infty\ \textbf{then} \\ \qquad\qquad\qquad dist[v]=dist[u]+1,\ prev[v]=u \\ \qquad\qquad\qquad\text{INJECT}(Q,v) \\ \hline \end{array}$$

在入队时立即设置距离，保证同一个顶点不会被重复入队。prev 记录首次发现它的前驱；从目标不断追溯 prev 到 $s$，再反转序列，就得到一条最短路径。

课件例子从 $S$ 出发，先发现距离为 1 的 $A,C,D,E$，再由 $A$ 发现距离为 2 的 $B$：

已处理顶点	处理后的队列
尚未开始	$[S]$
$S$	$[A,C,D,E]$
$A$	$[C,D,E,B]$
$C$	$[D,E,B]$
$D$	$[E,B]$
$E$	$[B]$
$B$	$[\ ]$

分层不变量：开始处理距离 $d$ 这一层时，距离不超过 $d$ 的顶点均已正确赋值，其他顶点尚为 $\infty$，队列恰好包含距离为 $d$ 的顶点。

处理这一层时，尚未发现的邻居距离至多为 $d+1$；若它有更短路径，就应已被更早的一层发现，因此首次赋予的 $d+1$ 正确。新顶点排在队尾，只有当前层全部处理完后才开始处理下一层。层内处理中，队列可以同时含距离 $d$ 和 $d+1$ 的顶点，课件的不变量指的是两层之间的边界时刻。

每个顶点最多入队、出队一次，每条邻接边扫描一次，因此 BFS 的时间与 DFS 相同，都是 $O(n+m)$；距离、前驱与队列共需 $O(n)$ 辅助空间。BFS 适用于有向图和无向图，但按边数最短，不能直接解决一般加权距离问题。

练习 3.7：若图 $G=(V,E)$ 的顶点可划分为两个互不相交的集合 $V_1,V_2$，满足 $V=V_1\cup V_2$，且同一集合内的顶点之间没有边，则称该图为二部图。

本题考查 BFS 遍历所有连通分量、二染色与奇环的等价关系。

(a) 给出线性时间算法，判断一个无向图是否为二部图。

将所有顶点的颜色初始化为“未染色”。对每个尚未染色的顶点 $s$，令 $c(s)=0$，从 $s$ 开始 BFS。扫描边 $\{u,v\}$ 时，若 $v$ 未染色，则令 $c(v)=1-c(u)$ 并入队；若已经染色且 $c(v)=c(u)$，立即返回“不是二部图”。所有连通分量检查完毕后，返回

$$V_0=\{v:c(v)=0\},\qquad V_1=\{v:c(v)=1\}.$$

伪代码使用 $-1$ 表示未染色，队列操作均为 $O(1)$ 时间：

// 检查所有连通分量；成功时返回二部划分，失败时返回 FALSE。
function BIPARTITE(G = (V, E)):
    for each v in V:
        c[v] ← -1
    for each s in V:
        if c[s] ≠ -1:
            continue
        c[s] ← 0
        Q ← 空队列
        ENQUEUE(Q, s)
        while Q is not empty:
            u ← DEQUEUE(Q)
            for each v in Adj(u):
                if c[v] = -1:
                    c[v] ← 1 - c[u]
                    ENQUEUE(Q, v)
                else if c[v] = c[u]:
                    return FALSE
    V0 ← {v ∈ V : c[v] = 0}
    V1 ← {v ∈ V : c[v] = 1}
    return (TRUE, V0, V1)

若算法返回成功，每条边的端点颜色不同，所以 $(V_0,V_1)$ 是合法二部划分。反过来，若图本来有二部划分，沿任意一条边都必须切换所在集合；从根开始交替染色会始终与该划分一致，至多交换两种颜色，不会产生冲突。

使用邻接表时，每个顶点入队一次，每条无向边扫描两次，因此时间为 $O(|V|+|E|)$，额外空间为 $O(|V|)$。外层循环保证不连通图中的每个分量都被检查。

(b) 无向图为二部图，当且仅当它可以只用两种颜色对顶点合法染色。证明另一等价表述：无向图为二部图，当且仅当它不含奇数长度的环。

若图为二部图，沿环每走一条边都切换一次集合。回到起点必须切换偶数次，因此所有环的长度都是偶数。

反过来，设图没有奇环。在每个连通分量中选根构造 BFS 树，令

$$c(v)=d(v)\bmod2,$$

其中 $d(v)$ 是根到 $v$ 的树深。若某条边 $\{u,v\}$ 的端点同色，设 $w$ 为二者在树中的最近公共祖先，则树上 $u$ 到 $v$ 的唯一路径长

$$d(u)+d(v)-2d(w),$$

它是偶数。这条树路径加上边 $\{u,v\}$ 构成奇环，与假设矛盾。因此每条边连接不同颜色，图为二部图。

© 一个恰好只有一个奇环的无向图，至多需要多少种颜色才能合法染色？

恰好需要 $3$ 种颜色。取唯一奇环上的一个顶点 $v$，删除它后，图中不再有奇环。由 (b)，$G-v$ 可用两种颜色染色；恢复 $v$ 并给它第三种颜色，就得到原图的合法染色。原图包含奇环，不能只用两种颜色，因此

$$\chi(G)=3.$$

加权距离

加权图为每条边指定长度 $\ell(u,v)$，路径长度是沿途边权之和。课件用城市道路说明：从 San Francisco 到 Los Angeles，直接道路长度为 $409$，经 Bakersfield 的两条道路为 $290+112=402$。BFS 会优先选择一条边的路线，但加权最短路应选择总长度 $402$ 的路线。

课件提问：边长为正整数时，能否把 BFS 改用于加权图？

可以把长度为 $\ell_e$ 的边替换成 $\ell_e$ 条单位边，在中间加入 $\ell_e-1$ 个虚拟顶点，然后运行 BFS。但运行时间变成 $O(n+\sum_e\ell_e)$。边权很大时图会膨胀；这个界依赖边权的数值，而非表示边权所需的位数，因此不能作为一般高效方案。

课件接着用闹钟解释如何跳过这些虚拟顶点：为源点在时刻 0 设闹钟；取下一次响铃的顶点 $u$，其到达时刻 $T$ 就是已确定的距离。对每条出边 $u\to v$，尝试把 $v$ 的闹钟设在 $T+\ell(u,v)$，已有更晚的闹钟则提前。这等价于每次取当前暂定距离最小的顶点。

松弛操作

所有后续算法都使用同一种松弛操作：

$$dist[v]\leftarrow\min\{dist[v],dist[u]+\ell(u,v)\}.$$

若候选值更小，同时令 prev[v]=u。初始化 dist[s]=0、其他距离为 $\infty$，并仅在 dist[u] 有限时沿 $u\to v$ 更新。

距离的有限候选值总对应一条从 $s$ 出发的实际路线，因此不会小于真正的最短距离。若 $u$ 已有正确距离，且 $u\to v$ 是一条最短路的最后一条边，那么松弛这条边就能得到 $v$ 的正确距离。后续松弛只能保持或降低候选值，不会把它降到最短距离以下。

设一条最短路依次经过 $s,u_1,\ldots,u_k,t$。只要更新序列按这个先后次序包含路径上的全部边，即使中间穿插其他更新，最后也会得到 $t$ 的正确距离。不同最短路算法的区别，在于如何安排这些更新。

Dijkstra

Dijkstra 算法每次取暂定距离最小的未确定顶点，把它的距离确定下来，再松弛其出边。课件假设边权为正；同样的算法与证明也适用于零权边，只需全部边权非负。

$$\begin{array}{l} \hline \textbf{算法：DIJKSTRA}(G,\ell,s) \\[4pt] \hline \textbf{输入：}\ \ell(e)\ge0\text{，使用邻接表} \\ \textbf{for}\ v\in V\ \textbf{do}\ dist[v]=\infty,\ prev[v]=\text{nil} \\ dist[s]=0 \\ H=\text{MAKEQUEUE}(V,dist) \\ \textbf{while}\ H\ne\varnothing\ \textbf{do} \\ \qquad u=\text{DELETEMIN}(H) \\ \qquad\textbf{if}\ dist[u]=\infty\ \textbf{then}\ \text{break} \\ \qquad\textbf{for}\ (u,v)\in E\text{ 的出边}\ \textbf{do} \\ \qquad\qquad\textbf{if}\ v\in H\ \text{且}\ dist[v]>dist[u]+\ell(u,v)\ \textbf{then} \\ \qquad\qquad\qquad dist[v]=dist[u]+\ell(u,v),\ prev[v]=u \\ \qquad\qquad\qquad\text{DECREASEKEY}(H,v) \\ \hline \end{array}$$

从堆中取出的顶点即距离已确定的顶点。非负边保证后面不会得到更短的路线，因此无需重新放回堆；若最小键已经是 $\infty$，剩余顶点全部不可达。

课件例子以 $A$ 为源点，边包括 $A\to B:4$、$A\to C:2$、$C\to B:1$、$B\to C:3$、$B\to D:2$、$C\to D:4$、$B\to E:3$、$C\to E:5$、$E\to D:1$。暂定距离的变化如下：

已处理顶点	$A$	$B$	$C$	$D$	$E$
初始化	0	$\infty$	$\infty$	$\infty$	$\infty$
$A$	0	4	2	$\infty$	$\infty$
$C$	0	3	2	6	7
$B$	0	3	2	5	6
$D$	0	3	2	5	6
$E$	0	3	2	5	6

最终距离为 $A:0,B:3,C:2,D:5,E:6$。最短路树使用 $A\to C$、$C\to B$、$B\to D$、$B\to E$；例如到 $D$ 的路径长度是 $2+1+2=5$。

正确性证明对已确定集合 $S$ 的大小归纳。源点正确。设之前确定的距离都正确，下一次取出 $u$；在一条真正的最短 $s\to u$ 路径上，取第一条离开 $S$ 的边 $x\to y$。$x$ 已确定，其出边已松弛，所以 $y$ 的暂定距离不超过该路径到 $y$ 的前缀长度。因为剩余边非负，前缀长度不超过整条路径长度 $\delta(s,u)$；又因为 $u$ 是未确定顶点中暂定距离最小者，$dist[u]\le dist[y]$。故 $dist[u]\le\delta(s,u)$。另一方面，松弛的安全性保证 $dist[u]\ge\delta(s,u)$，两者相等。

练习 4.11：给定边长均为正的有向图，设计算法返回图中最短环的长度；若图无环，应报告无环。时间复杂度至多为 $O(|V|^3)$。

本题考查正权最短路径、以一条边闭合路径得到环，以及多次 Dijkstra 的复杂度分析。

记 $n=|V|$、$m=|E|$。对每个顶点 $s$ 运行一次 Dijkstra，得到距离 $d_s[u]=\delta(s,u)$；对每条进入 $s$ 的边 $(u,s)$，用该边将一条最短 $s\to u$ 路径闭合成环。答案为

$$L=\min_{(u,s)\in E}\bigl(d_s[u]+\ell(u,s)\bigr).$$

若没有有限候选值，则图无环。以下使用无序数组选取最小距离顶点，使一次 Dijkstra 的时间为 $O(n^2+m)$。邻接表项 $(v,f)$ 表示邻点 $v$ 和边标识 $f$；参数 skip 允许跳过一条指定边，供 4.12 复用。

// 正权图上的数组版 Dijkstra；skip = NONE 表示不跳过任何边。
function DIJKSTRA-ARRAY(G = (V, E), ell, s, skip):
    for each v in V:
        dist[v] ← +∞
        fixed[v] ← FALSE
    dist[s] ← 0
    for step ← 1 to |V|:
        u ← 未固定顶点中 dist 最小者
        if dist[u] = +∞:
            break
        fixed[u] ← TRUE
        for each (v, f) in Adj(u):
            if f = skip:
                continue
            if fixed[v] = FALSE and dist[v] > dist[u] + ell[f]:
                dist[v] ← dist[u] + ell[f]
    return dist

// 枚举环的闭合边；incoming[s] 保存所有进入 s 的边。
function SHORTEST-DIRECTED-CYCLE(G = (V, E), ell):
    for each s in V:
        incoming[s] ← 空列表
    for each edge f = (u, v) in E:
        APPEND(incoming[v], (u, f))
    answer ← +∞
    for each s in V:
        dist ← DIJKSTRA-ARRAY(G, ell, s, NONE)
        for each (u, f) in incoming[s]:
            answer ← min(answer, dist[u] + ell[f])
    if answer = +∞:
        return ACYCLIC
    return answer

设最短环长为 $\mathrm{OPT}$。正权保证有限最短路径可取为简单路径。对每条满足 $d_s[u]<\infty$ 的边 $(u,s)$，最短 $s\to u$ 路径与该边构成一个环，因此

$$d_s[u]+\ell(u,s)\ge\mathrm{OPT}, \qquad L\ge\mathrm{OPT}.$$

反过来，取任意最短环 $C$ 及其一条边 $(u,s)$。删除该边得到一条 $s\to u$ 路径，故

$$d_s[u]\le\ell(C)-\ell(u,s), \qquad L\le d_s[u]+\ell(u,s)\le\ell(C)=\mathrm{OPT}.$$

因此 $L=\mathrm{OPT}$。同样地，存在有限候选值当且仅当存在环，所以无环判定也正确。

按教材的简单图模型，$m=O(n^2)$。建立反向邻接表需要 $O(n+m)$ 时间；运行 $n$ 次数组版 Dijkstra，最后各条入边共检查一次，故

$$T(n,m)=O\bigl(n(n^2+m)+m+n\bigr)=O(n^3).$$

辅助空间为 $O(n+m)$，无须保存全部源点的距离。

练习 4.12：对下列问题设计 $O(|V|^2)$ 时间的算法。

输入：无向图 $G=(V,E)$，正边长 $\ell_e>0$，以及一条指定边 $e\in E$。

输出：包含边 $e$ 的最短环的长度。

本题考查删边后的最短路径与包含指定边的最短环之间的对应关系；它是练习 3.11 的加权版本。

设 $e=\{s,t\}$。在搜索中跳过边 $e$ 的两个邻接表项，计算

$$d=\delta_{G-e}(s,t).$$

若 $d=\infty$，则不存在包含 $e$ 的环；否则返回 $d+\ell_e$。使用 4.11 中的数组版 Dijkstra：

// 跳过指定的无向边，再用该边闭合最短路径。
function SHORTEST-CYCLE-THROUGH-EDGE(G, ell, e = {s, t}):
    dist ← DIJKSTRA-ARRAY(G, ell, s, e)
    if dist[t] = +∞:
        return NO-CYCLE
    return dist[t] + ell[e]

记 $\mathcal C_e$ 为包含 $e$ 的简单环集合，$\mathcal P_{s,t}(G-e)$ 为删边后简单 $s\to t$ 路径的集合。删去或补回 $e$ 给出对应关系

$$C\in\mathcal C_e \longleftrightarrow C-e\in\mathcal P_{s,t}(G-e).$$

因此，当两集合非空时，

$$\min_{C\in\mathcal C_e}\ell(C) = \ell_e+\min_{P\in\mathcal P_{s,t}(G-e)}\ell(P) = \ell_e+\delta_{G-e}(s,t).$$

两集合也同时为空，故算法的 NO-CYCLE 分支正确。数组版 Dijkstra 的时间为

$$O(n^2+m)=O(n^2),$$

辅助空间为 $O(n)$；搜索只跳过指定边，不复制图。

优先队列

课件的闹钟操作由优先队列实现：INSERT 插入元素；DECREASEKEY 降低键值；DELETEMIN 取出并删除最小键元素；MAKEQUEUE 从给定键值构建队列。实现 DECREASEKEY 时，通常还需要保存顶点在堆中的位置。

Dijkstra 至多执行 $n$ 次 DELETEMIN、$m$ 次 DECREASEKEY，以及一次构建队列。邻接表扫描另花 $O(m)$。不同实现的代价为：

实现	删除最小值	插入或降键	总时间
无序数组	$O(n)$	$O(1)$	$O(n^2+m)$
二叉堆	$O(\log n)$	$O(\log n)$	$O((n+m)\log n)$
$d$ 叉堆	$O(d\log_d n)$	$O(\log_d n)$	$O((dn+m)\log_d n)$
Fibonacci 堆	均摊 $O(\log n)$	均摊 $O(1)$	$O(n\log n+m)$

普通简单图有 $m=O(n^2)$，数组实现的界可写成 $O(n^2)$。二叉堆可在 $O(n)$ 时间建堆，按逐个插入估计的 $O(n\log n)$ 上界也足够推导课件的总复杂度。

课件提问：数组和二叉堆哪个更好？

稠密图 $m=\Theta(n^2)$ 时，数组的 $O(n^2)$ 比二叉堆上界少一个对数因子。稀疏图中二叉堆更有优势；比较两式可见，边数显著低于 $n^2/\log n$ 时堆的上界更小。$d$ 叉堆则可在删除与降键之间调节，课件建议取 $d$ 约为 $m/n$，实际需保证 $d\ge2$。

练习 4.16：将含 $n$ 个结点的完全二叉树按层序存入下标为 $1,2,\ldots,n$ 的数组。

本题考查完全树的数组编号、自底向上建堆的总代价分析，以及 d 叉堆的上浮、下沉和逆映射维护。

(a) 证明：位置 $j$ 的结点，其父结点在 $\lfloor j/2\rfloor$，孩子在 $2j$ 和 $2j+1$；孩子下标须不超过 $n$。

按层序从左到右编号，根为 $1$。把结点编号写成二进制

$$j=(1b_1b_2\cdots b_h)_2.$$

从根向左走在编号末尾追加 $0$，向右走追加 $1$，故两个孩子分别为

$$(j0)_2=2j,\qquad (j1)_2=2j+1.$$

对 $j>1$，删除最后一位就回到父结点，得到 $\lfloor j/2\rfloor$。大于 $n$ 的孩子编号表示该孩子不存在；根没有父结点。

(b) 完全 $d$ 叉树用同样方式存入数组时，父结点和孩子的下标分别是什么？

设 $d\ge2$。转为从 $0$ 开始的编号后，位置 $j-1$ 的孩子编号为 $d(j-1)+1,\ldots,d(j-1)+d$；再转回从 $1$ 开始的编号，得到

$$\operatorname{children}(j) = \{d(j-1)+2,\ldots,d(j-1)+d+1\}\cap\{1,\ldots,n\}.$$

因此，对 $j>1$，

$$\operatorname{parent}(j) = \left\lfloor\frac{j-2}{d}\right\rfloor+1.$$

取 $d=2$，恰好还原为 (a) 的公式。

教材图 4.16 给出了参考塔扬相关著作编写的二叉堆伪代码。堆以数组 $h$ 存储，并支持常数时间访问 $|h|$（当前元素数）与 $h^{-1}$（元素在数组中的位置）；后者可通过辅助数组维护。

© 证明：对 $n$ 个元素执行 makeheap 只需 $O(n)$ 时间。最坏情况的输入是什么？提示先考虑 $\sum_{i=1}^{n}\log(n/i)$ 给出的代价界。

建堆先按输入顺序填入数组，再从最后一个结点向根逐个下沉。记 pos 为逆映射 $h^{-1}$；SIFT-DOWN 的通用形式在 (d) 给出，取 $d=2$ 即二叉堆版本。

// 自底向上建堆；每个元素有独立标识，key(x) 表示其优先级。
function MAKEHEAP(S, d = 2):
    h ← 按输入顺序存放 S 的数组
    for i ← 1 to |h|:
        pos[h[i]] ← i
    for i ← |h| downto 1:
        SIFT-DOWN(h, pos, h[i], i, d)
    return (h, pos)

处理位置 $i$ 时，其孩子的下标均大于 $i$，所以孩子子树已经满足堆性质；下沉后，以 $i$ 为根的子树也成为堆。逆序归纳可得最终结果正确。

在二叉堆中，位置 $i$ 的子树高度满足

$$H_i\le\left\lfloor\log_2\frac ni\right\rfloor,$$

因为距离 $h$ 层的后代编号至少为 $2^hi$，必须满足 $2^hi\le n$。每次下沉的时间为 $O(1+H_i)$，因此

$$\begin{aligned} T(n) &=O\!\left(n+\sum_{i=1}^{n} \left\lfloor\log_2\frac ni\right\rfloor\right)\\ &=O\!\left(n+\sum_{h=1}^{\lfloor\log_2n\rfloor} \left\lfloor\frac n{2^h}\right\rfloor\right) =O(n). \end{aligned}$$

初始读入和建表需要 $\Omega(n)$ 时间，故建堆实际为 $\Theta(n)$。

一种最坏量级输入是按层序严格递减的键序列 $n,n-1,\ldots,1$。特别地，当 $n=2^{h+1}-1$ 时，每个内部结点原有的键都大于其全部后代，因而在处理时一直下沉到叶子，达到上述总下沉次数的上界。一般 $n$ 的最坏总时间仍为 $\Theta(n)$。

(d) 要把这些二叉堆伪代码改成 $d$ 叉堆，需要修改哪些部分？

教材最后一小问重复标为 (a)，此处按 (d) 处理。使用 (b) 的父子编号，并让 MIN-CHILD 扫描至多 $d$ 个孩子。每次移动元素都必须同步更新 pos，才能保持 $h^{-1}$ 的常数时间访问。

图 4.16 的 bubbleup 将父下标误写为 $\lceil i/2\rceil$；从 $1$ 开始编号时应为 $\lfloor i/2\rfloor$，通用版本统一使用 $\lfloor(i-2)/d\rfloor+1$。下面也显式维护删除操作的数组长度。

// 返回最小键孩子的下标；叶子返回 0。
function MIN-CHILD(h, i, d):
    left ← d × (i - 1) + 2
    if left > |h|:
        return 0
    right ← min(|h|, left + d - 1)
    c ← left
    for j ← left + 1 to right:
        if key(h[j]) < key(h[c]):
            c ← j
    return c

// 将 x 放入位置 i，并沿父结点上浮，维护逆映射。
procedure BUBBLE-UP(h, pos, x, i, d):
    while i > 1:
        p ← floor((i - 2) / d) + 1
        if key(h[p]) ≤ key(x):
            break
        h[i] ← h[p]
        pos[h[i]] ← i
        i ← p
    h[i] ← x
    pos[x] ← i

// 孩子子树已是堆；沿最小键孩子下沉，再放置 x。
procedure SIFT-DOWN(h, pos, x, i, d):
    c ← MIN-CHILD(h, i, d)
    while c ≠ 0 and key(h[c]) < key(x):
        h[i] ← h[c]
        pos[h[i]] ← i
        i ← c
        c ← MIN-CHILD(h, i, d)
    h[i] ← x
    pos[x] ← i

// 弹出末元素使数组长度先减一，再将它放到根部下沉。
function DELETE-MIN(h, pos, d):
    if |h| = 0:
        return NIL
    result ← h[1]
    x ← REMOVE-LAST(h)
    pos[result] ← NIL
    if |h| > 0:
        SIFT-DOWN(h, pos, x, 1, d)
    return result

写入 $h[|h|+1]$ 表示追加元素。INSERT 与 DECREASEKEY 的调用规则不变，只需传入 $d$：

$$\operatorname{INSERT}(h,x): \quad\operatorname{BUBBLE\text{-}UP}(h,\mathrm{pos},x,|h|+1,d),$$

$$\operatorname{DECREASEKEY}(h,x): \quad\operatorname{BUBBLE\text{-}UP}(h,\mathrm{pos},x,\mathrm{pos}[x],d),$$

其中 DECREASEKEY 在降低 key$(x)$ 后调用。MAKEHEAP 同样按逆序调用通用下沉过程。每层上浮只比较一个父结点，下沉则检查至多 $d$ 个孩子，因此时间分别为 $O(\log_d n)$ 和 $O(d\log_d n)$；固定 $d$ 时建堆仍为 $O(n)$。

负权最短路

负权边使 Dijkstra 的确定步骤失效。例如 $s\to a$ 权重 2、$s\to b$ 权重 5、$b\to a$ 权重 $-4$：算法会先确定 $a$ 的距离为 2，但真正的最短路线 $s\to b\to a$ 长度为 1。较远的未确定顶点可能通过负边改进已确定顶点。

课件提问：允许负权边后需要改变什么？

松弛操作仍然安全，但不能再把“当前最小的暂定距离”视为最终值。需要安排多轮更新，使每条最短路径的边最终按正确的先后顺序完成松弛。

在没有相关负环的情况下，可以选取一条简单最短路：若路线重复某个顶点，就包含一个环；删去权重非负的环不会增大长度。简单路径最多有 $n-1$ 条边。因此不必预先知道最短路，只要反复扫描全部边 $n-1$ 轮，便能覆盖每条最短路所需的更新次序。这就是 Bellman-Ford 算法。

$$\begin{array}{l} \hline \textbf{算法：BELLMAN-FORD}(G,\ell,s) \\[4pt] \hline \textbf{for}\ v\in V\ \textbf{do}\ dist[v]=\infty,\ prev[v]=\text{nil} \\ dist[s]=0 \\ \textbf{repeat}\ n-1\ \textbf{times}: \\ \qquad\textbf{for}\ (u,v)\in E\ \textbf{do} \\ \qquad\qquad\textbf{if}\ dist[u]<\infty\ \text{且}\ dist[v]>dist[u]+\ell(u,v)\ \textbf{then} \\ \qquad\qquad\qquad dist[v]=dist[u]+\ell(u,v),\ prev[v]=u \\ \hline \end{array}$$

可用归纳证明：第 $k$ 轮结束后，所有存在不超过 $k$ 条边的最短路的顶点都已得到正确距离。沿一条这样的路径，前驱在上一轮已经正确，本轮扫描最后一条边就会更新终点。穿插其他松弛也不会产生过小的距离，所以结论不受扫描顺序影响。$n-1$ 轮后全部有限最短距离正确，时间 $O(nm)$。若某轮没有更新，可提前停止。

课件从 $S$ 出发，给出以下迭代表格：

顶点	0	1	2	3	4	5	6	7
$S$	0	0	0	0	0	0	0	0
$A$	$\infty$	10	10	5	5	5	5	5
$B$	$\infty$	$\infty$	$\infty$	10	6	5	5	5
$C$	$\infty$	$\infty$	$\infty$	$\infty$	11	7	6	6
$D$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	14	10	9
$E$	$\infty$	$\infty$	12	8	7	7	7	7
$F$	$\infty$	$\infty$	9	9	9	9	9	9
$G$	$\infty$	8	8	8	8	8	8	8

这个表格可以按“第 $k$ 列是最多经过 $k$ 条边的最短距离”理解：每轮读取上一轮的副本，计算新一轮距离。上面的伪代码采用原地更新，同一轮可能传播多条边，因此某些图或扫描顺序会更早收敛；$n-1$ 轮的保证仍然成立。

例如 $S\to G\to F\to A$ 长度为 $8+1-4=5$，所以 $A$ 在第 3 轮从 10 改为 5。最终到 $D$ 的最短路是 $S\to G\to F\to A\to E\to B\to C\to D$，长度为 $8+1-4+2-2+1+3=9$，共 7 条边；这解释了表格为什么直到第 7 轮才得到 $D=9$。

负环检测

负环是总权重小于 0 的环。若从 $s$ 能到达负环，又能从负环到达 $v$，绕环次数越多，到 $v$ 的路线越短，最短距离不再是一个有限值，可记为 $-\infty$。图中某处存在负环，并不意味着所有源点、所有目标的最短路都失去意义。

课件提问：如何检测负环？

Bellman-Ford 做完 $n-1$ 轮后再扫描一轮。如果仍能降低某个距离，就存在从 $s$ 可达的负环。若要检测全图任意位置的负环，可增加一个到所有顶点都有零权边的超级源点，等价地把所有初始距离都设为 0，再检测额外一轮更新。

没有可达负环时，一条有限最短路最多需要 $n-1$ 条边，额外一轮不能再改进。反过来，若可达负环上的全部边都已满足 $dist[v]\le dist[u]+\ell(u,v)$，把这些不等式沿环相加，就得到环权重不小于 0，与负环矛盾；因此仍有边能继续降低距离。

若还要找出距离为 $-\infty$ 的目标，可以从额外一轮中被降低的顶点出发，沿原图搜索；能够从这些顶点到达的顶点都受负环影响。

DAG 路径

非负权图不会含负环，DAG 则不含任何环，所以边权可以任意正负。对 DAG，拓扑序已经保证每条路径的顶点依次出现；只需按拓扑序处理顶点，并松弛它的出边，便能在线性时间求出最短路。

$$\begin{array}{l} \hline \textbf{算法：DAG-SHORTEST-PATHS}(G,\ell,s) \\[4pt] \hline L=\text{TOPOLOGICAL-SORT}(G) \\ \textbf{for}\ v\in V\ \textbf{do}\ dist[v]=\infty,\ prev[v]=\text{nil} \\ dist[s]=0 \\ \textbf{for}\ u\in L\ \textbf{do} \\ \qquad\textbf{if}\ dist[u]<\infty\ \textbf{then} \\ \qquad\qquad\textbf{for}\ (u,v)\in E\text{ 的出边}\ \textbf{do} \\ \qquad\qquad\qquad\text{松弛 }(u,v) \\ \hline \end{array}$$

处理 $u$ 时，它的全部前驱都已处理，所有进入 $u$ 的候选路线都已比较完，因此距离已正确。每条边只松弛一次，加上拓扑排序，总时间为 $O(n+m)$。课件伪代码的内层写成“对所有 $e\in E$ 更新”，照字面实现会花 $O(nm)$；要达到课件声称的线性时间，应改为只扫描当前顶点 $u$ 的出边。

DAG 中也能求最长路径：把全部边权取负，再求最短路，最后将距离取负即可。直接实现时把未到达值初始化为 $-\infty$，将松弛中的最小值改成最大值，也得到相同结果。由于没有环，路径不会因无限绕环而变长。

思考：一般有向图中，所有边权为正，能否高效求最长简单路径？

不能从 DAG 的线性算法直接推广。要求路径不重复顶点后，问题是 NP 困难的：把每条边权都设为 1，若能判定最长简单路径是否有 $n-1$ 条边，就能判定图是否存在 Hamilton 路径。若允许重复顶点，正环又会使最长路线无上界；因此“简单路径”这个限制很关键。

路径练习

练习：给每条边权加同一个大常数，使负权变成正权，再用 Dijkstra，能否求出原图最短路？

不能。路径 $P$ 的新长度是原长度加上常数乘以路径边数；边数不同的路径会被增加不同的代价，排序可能改变。

反例：$s\to t$ 权重 2，$s\to a$ 权重 $-2$，$a\to t$ 权重 3。原图中经 $a$ 的路线长度 1，比直接路线 2 更短。每条边加 3 后，两条路线长度分别为 7 和 5，Dijkstra 会选直接路线，得到错误答案。问题不是 Dijkstra 在修改后的图上算错，而是修改边权破坏了原问题的最优路线。

练习 4.14：强连通有向图的边权均为正，给定顶点 $v_0$。如何求所有顶点对之间必须经过 $v_0$ 的最短路线？

在 $G$ 中从 $v_0$ 做一次 Dijkstra，得到 $d_{out}[t]=\delta(v_0,t)$；在反向图 $G^R$ 中再从 $v_0$ 做一次，得到 $d_{in}[s]=\delta(s,v_0)$。任意 $s,t$ 的答案为 $d_{in}[s]+d_{out}[t]$。

任何经过 $v_0$ 的路线都可在一次到达 $v_0$ 的位置拆成两段，每段长度至少是对应最短距离，所以这个和给出下界；拼接两段最短路线又能达到它。强连通保证两段距离都有限。

二叉堆实现的两次搜索共花 $O((n+m)\log n)$。若必须显式输出全部 $n^2$ 个距离，还需 $O(n^2)$ 时间；若只存两组距离，之后每次查询只需 $O(1)$。保存两次搜索的前驱也可恢复路线；若要逐条展开完整路线，还应计入总输出长度。

本题按允许重复顶点的路线理解。强制经过 $v_0$ 时，两段最短路线可能共享其他顶点；若题目额外要求整体是简单路径，上述拼接公式就不一定适用。

算法对比

问题	适用条件	时间
可达性、无向连通分量	任意图，按边的方向搜索	$O(n+m)$
拓扑排序	DAG	$O(n+m)$
强连通分量	有向图，两遍 DFS	$O(n+m)$
BFS 最短路	所有边等长或无权	$O(n+m)$
Dijkstra 最短路	所有边权非负，二叉堆	$O((n+m)\log n)$
Bellman-Ford	可有负权；同时检查可达负环	$O(nm)$
DAG 最短路或最长路	DAG，边权可正可负	$O(n+m)$

图的结构与边权条件共同决定算法选择。拓扑序把 DAG 中的依赖一次安排好；非负边让 Dijkstra 的最小候选值可以确定；一般负权图则需要多轮松弛，并检查负环是否影响目标。