1. Prim 算法#

Prim(普里姆)算法在执行过程上与求解单源最短路径的 Dijkstra 算法较为相似。

初始时，从图中任取一个顶点加入树 T，此时 T 仅包含该顶点。接着，选择一个与当前 T 中顶点集合距离最近的顶点，并将该顶点及其相连的最小权值边加入 T。每执行一次此操作，T 中的顶点数和边数各增加 1。重复这一过程，直到图中所有顶点都被并入 T 为止。最终得到的 T 即为最小生成树，且其中必然含有 n-1 条边。图 6.15 展示了 Prim 算法构造最小生成树的过程。

Prim算法步骤如下：

假设 $G = \{V, E\}$ 是连通图，其最小生成树 $T = (U, E_T)$，$E_T$ 是 T 中的边集合。

初始化：向空树 $T=(U,E_{T})$ 中添加图 G 的任意一个顶点 $u_{0}$，使得 $U=\{u_{0}\}$，$E_{T}=\varnothing$。

循环(重复，直至 $U = V$)：从图 $G$ 中选择满足条件 $\{(u, v) | u \in U, v \in V - U\}$ 且具有最小权值的边 $(u, v)$，将其加入树 $T$，并更新 $U = U \cup \{v\}$，$E_T = E_T \cup \{(u, v)\}$。

Prim 算法的简单实现如下：

1
void Prim(G, T) {
2
    T = Ø;                   //初始化空树
3
    U = {w};                 //添加任意一个顶点 w
4
    while ((V-U) != Ø) {     //若树中不含全部顶点
5
        设(u, v)是使 u∈U 与 v∈(V-U)，且权值最小的边；
6
        T = T ∪ ((u, v));   //边归入树
7
        U = U ∪ {v};        //顶点归入树
8
    }
9
}

在 Prim 算法中，每步都从当前已构建的树向外扩展一条最短边，逐步生长出整棵最小生成树。该算法的时间复杂度为 $O(|V|^2)$，与边数 $|E|$ 无关，因此特别适用于求解边稠密图的最小生成树。虽然采用其他方法能改进 Prim 算法的时间复杂度，但会增加实现的复杂度。

2. Kruskal 算法#

与 Prim 算法从一个顶点开始扩展最小生成树的方式不同，Kruskal(克鲁斯卡尔)算法采用按边的权值递增次序选择合适的边来构造最小生成树的方法。

初始时，图 $T = \{V, \{\}\}$ 包含全部 $n$ 个顶点，但不含任何边，每个顶点自成一个连通分量。然后按照边的权值从小到大的顺序，依次考察各条边：如果当前边连接的两个顶点属于 $T$ 中不同的连通分量(可通过并查集判断)，则将该边加入 T；否则，舍弃此边，继续考察下一条权值最小的边。重复这一过程，直到所有顶点都属于同一个连通分量，此时得到的 T 即为最小生成树。图 6.16 展示了 Kruskal 算法构造最小生成树的过程。

Kruskal 算法步骤如下：

假设 $G=(V,E)$ 是连通图，其最小生成树 $T=(U,E_{T})$，$E_{T}$ 是 T 中的边集合。

初始化：$U = V, E_T = \varnothing$。即每个顶点构成一棵独立的树，T此时是一个仅含 $|V|$ 个顶点的森林。

循环(重复，直至 T 成为一棵树)：按照边权值递增的顺序，从 $E-E_{T}$ 中选择一条边。若该边加入 T 后不构成回路，则将其加入 $E_{T}$；否则舍弃，直到 $E_{T}$ 包含 n-1 条边为止。

Kruskal 算法的简单实现如下：

1
void Kruskal(V,T){
2
    T=V;            //初始化树T，仅含顶点
3
    numS=n;         //连通分量数
4
    while(numS>1){  //若连通分量数大于1
5
        //从E中取出权值最小的边(v,u);
6
        if(v和u属于T中不同的连通分量){
7
            T=T∪{(v,u)};
8
            numS--;
9
        }
10
    }
11
}

在 Kruskal 算法中，每当选择一条连接两棵不同树的边时，这两棵树将通过这条边合并为一棵更大的树，随着算法的进行，整个森林逐渐合并成一棵树。考虑到算法效率，在最坏情况下需要对所有的|E|条边各扫描一次。通常，边会存储在一个堆(见第 7 章)中，每次从中选出最小权值的边所需时间为 $O(\log_2|E|)$。同时，使用并查集来快速确定两个顶点是否属于同一集合的时间复杂度为 $O(\alpha(|V|))$，这里 $\alpha(|V|)$ 增长极其缓慢，可视为常数。因此，Kruskal 算法的总时间复杂度为 $O(|E|\log_2|E|)$，不依赖于|V|，这使得它特别适合于处理边稀疏但顶点较多的图。

1. Dijkstra 算法求单源最短路径问题#

Dijkstra 算法使用一个集合 S 记录已确定最短路径的顶点。初始时，将源点(顶点 0)放入 S；每当将一个新顶点 i 加入 S 后，需更新源点到所有尚未确定最短路径的顶点(集合 V-S 中的顶点)的当前最短路径长度。算法执行过程中维护以下三个辅助数组：

• final[]：标记各顶点是否已找到最短路径(是否属于集合 S)。
• dist[]：记录从源点到各顶点的当前最短路径长度。初始化时，若存在从源点到顶点 i 的直接边，则 dist[i] 为该边的权值，否则置为∞。
• path[]：path[i]存储从源点到顶点 i 的最短路径。算法结束后，可通过 path[]数组回溯，重构出完整的最短路径。

假设源点为顶点 0，集合 S 初始仅含顶点 0。图以邻接矩阵 arcs 表示，其中 arcs[i][j]为有向边<i,j>的权值；若该边不存在，则 arcs[i][j]为∞。

Dijkstra 算法的步骤如下(暂不考虑对 path[] 的操作)：

1. 初始化：集合 $S = \{0\}$，dist[] 的初始值为 $\text{dist}[i] = \arcsin[0][i]$，$i = 1, 2, \cdots, n-1$。
2. 选择最短路径顶点：从不在 S 中的顶点集合(V-S)中选出顶点 j，使得 $\text{dist}[j]$ 最小，此时，顶点 j 即为当前从源点出发的最短路径的终点，将其加入集合 S。
3. 松弛操作：对每个从顶点 j 出发的邻接顶点 k($\operatorname{arcs}[j][k] \neq \infty$)，若 $\operatorname{dist}[j] + \arcsin[j][k] < \operatorname{dist}[k]$，则更新 $\operatorname{dist}[k] = \operatorname{dist}[j] + \arcsin[j][k]$。
4. 重复步骤2～3共n-1次，直至所有顶点都包含在集合S中。

每个新顶点 $^{+}$ 都可能发现到达其他尚未确定最短路径顶点的更短路径，从而需要更设源点为 $v_0$，初始时 $S = \{v_0\}$，dist[1] = 3，dist[2] = 7。将 $v_1$ 加入集合 S 后，发现路径 $v_0 \to v_1 \to v_2$ 的长度为 4(dist[1] + arcs[1][2] = 3 + 1 = 4)，小于原来的 7，因此将 dist[2] 更新为 4。

思考：Dijkstra 算法与 Prim 算法有何异同之处？

例如，对图应用 Dijkstra 算法求从顶点 1 出发到其余各顶点的最短路径的过程。算法执行过程的说明如下。

初始化：集合 $S$ 初始为 $\{v_1\}$，从 $v_1$ 可达 $v_2$ 和 $v_5$，不可达 $v_3$ 和 $v_4$，因此 $\text{dist}()$ 数组的初始值为 $\text{dist}[2]=10$，$\text{dist}[3]=\infty$，$\text{dist}[4]=\infty$，$\text{dist}[5]=5$。

第1轮：选出最小值 $\text{dist}[5]$，将 $v_5$ 加入集合 $S$，此时已确定 $v_1$ 到 $v_5$ 的最短路径。检查从 $v_5$ 出发的邻接边：$v_5$ 可达 $v_2$，$v_1 \to v_5 \to v_2$ 的长度为 8，小于当前 $\text{dist}[2] = 10$，更新 $\text{dist}[2] = 8$；$v_5$ 可达 $v_3$，$v_1 \to v_5 \to v_3$ 的长度为 14，更新 $\text{dist}[3] = 14$；$v_5$ 可达 $v_4$，$v_1 \to v_5 \to v_4$ 的长度为 7，更新 $\text{dist}[4] = 7$。

第2轮：选出最小值 dist[4]，将 $v_4$ 加入集合 $S$。检查从 $v_4$ 出发的邻接边：$v_4$ 不可达 $v_2$，dist[2] 不变；$v_4$ 可达 $v_3$，$v_1 \to v_5 \to v_4 \to v_3$ 的长度为 13，小于当前 dist[3] = 14，更新 dist[3] = 13。

第 3 轮：选出最小值 dist[2]，将 $v_2$ 加入集合 $S$。检查从 $v_2$ 出发的邻接边：$v_2$ 可达 $v_3$，$v_1 \to v_5 \to v_2 \to v_3$ 的长度为 9，小于当前 dist[3] = 13，更新 dist[3] = 9。

第4轮：选出唯一最小值dist[3]，将 $v_{3}$ 加入集合S，此时，所有顶点均已包含在集合S中。

使用邻接矩阵表示图，并采用线性扫描 $\text{dist}[\text{}]$ 查找最小值时，Dijkstra 算法的时间复杂度为 $O(|V|^{2})$。若改用带权邻接表，虽然松弛操作的总代价可降至 $O(|E|)$，但由于查找最小 $\text{dist}[\text{}]$ 值仍需 $O(|V|)$ 时间，总时间复杂度仍为 $O(|V|^{2})$。即使只需求解从源点到某一个特定顶点的最短路径，在最坏情况下仍需处理所有顶点，因此时间复杂度不变，仍为 $O(|V|^{2})$。

特别注意：Dijkstra 算法不适用于存在负权边的图。该算法基于贪心策略，一旦顶点被加入集合 S，便不再更新其最短路径。然而，若图中存在负权边，后续路径可能通过负权边 “绕回” 已确定的顶点，从而发现更短路径，而 Dijkstra 算法无法察觉这一变化，导致结果错误。例如，对于图 6.18 所示的带权有向图，Dijkstra 算法可能无法得到正确的最短路径。

图 6.18 边上带有负权值的有向带权图

2. Floyd 算法求各顶点之间最短路径问题#

给定带权有向图，对任意两个不同顶点 $v_{i} \neq v_{j}$，求解从 $v_{i}$ 到 $v_{j}$ 的最短路径及其长度。

Floyd 算法的基本思想：迭代生成一系列 $n$ 阶方阵 $A^{(-1)}, A^{(0)}, \cdots, A^{(k)}, \cdots, A^{(n-1)}$，其中 $A^{(k)}[i][j]$ 表示从顶点 $v_i$ 到 $v_j$、仅允许使用编号不超过 $k$ 的顶点作为中间顶点时的最短路径长度。初始时 $(k = -1)$，若存在从 $v_i$ 到 $v_j$ 的直接边，则 $A^{(-1)}[i][j]$ 为该边的权值；否则设为 $\infty$。特别地，对所有 $i$，令 $A^{(-1)}[i][i] = 0$。随后，依次考虑顶点 $k$ ($k = 0, 1, \cdots, n-1$)作为中间顶点，若经由 $v_k$ 的路径比当前记录的路径更短，则更新对应的距离。算法的描述如下：

定义 n 阶方阵序列 $A^{(-1)}, A^{(0)}, \cdots, A^{(n-1)}$，其中，

式中，$A^{(0)}[i][j]$ 表示从 $v_i$ 到 $v_j$、仅允许使用 $v_0$ 作为中间顶点的最短路径长度；一般地，$A^{(k)}[i][j]$ 表示从 $v_i$ 到 $v_j$、中间顶点编号不超过 $k$ 的最短路径长度。Floyd算法是一个迭代过程，每完成一次迭代，便将下一个顶点纳入可选的中间顶点集合；经过 $n$ 次迭代后，$A^{(n-1)}[i][j]$ 即为 $v_i$ 到 $v_j$ 的最短路径长度。最终，矩阵 $A^{(n-1)}$ 中的每个元素即为对应顶点对的最短路径长度。

应用 Floyd 算法求解所有顶点对之间的最短路径长度的过程如表 6.3 所示。算法执行过程的说明如下。

初始化：方阵 $A^{(-1)}[i][j] = \arcsin[i][j]$。

第1轮：以 $v_0$ 为中间顶点，检查全部顶点对 $\{i, j\}$。若 $A^{(-1)}[i][j] > A^{(-1)}[i][0] + A^{(-1)}[0][j]$，则将 $A^{(-1)}[i][j]$ 更新为 $A^{(-1)}[i][0] + A^{(-1)}[0][j]$。$A^{(-1)}[2][1] = \infty$，而 $A^{(-1)}[2][0] + A^{(-1)}[0][1] = 11$，因 $\infty > 11$，故更新 $A^{(-1)}[2][1] = 11$。其余元素保持不变，得到方阵 $A^{(0)}$。

第2轮：以 $v_1$ 为中间顶点，检查全部顶点对 $\{i, j\}$。$A^{(0)}[0][2] = 13$，而 $A^{(0)}[0][1] + A^{(0)}[1][2] = 10$，因 $13 > 10$，故更新 $A^{(0)}[0][2] = 10$，得到方阵 $A^{(1)}$。

第 3 轮：以 $v_2$ 为中间顶点，检查全部顶点对 $\{i, j\}$。$A^{(1)}[1][0] = 10$，而 $A^{(1)}[1][2] + A^{(1)}[2][0] = 9$，更新 $A^{(1)}[1][0] = 9$，最终得到方阵 $A^{(2)}$，其中每个元素 $A^{(2)}[i][i]$ 即为 $v_i$ 到 $v_i$ 的最短路径长度。

表 6.3 Floyd 算法的执行过程

Floyd 算法的时间复杂度为 $O(|V|^{3})$。其代码结构紧凑，仅需一个三重循环，无须复杂数据结构，且常数因子较小，因此在中等规模图上实际运行效率较高。

Floyd 算法允许图中存在负权边，但不允许存在负权环。Floyd 算法同样适用于带权无向图——只需将每条无向边视为两条方向相反、权值相同的有向边。

此外，也可通过调用单源最短路径算法求解所有顶点对的最短路径：在边权非负的条件下，依次以每个顶点为源点运行 Dijkstra 算法。Dijkstra 算法的时间复杂度为 $O(|V|^2)$，因此共需执行 $|V|$ 次，总时间复杂度为 $O(|V|^3)$，与 Floyd 算法的相同。

BFS 算法、Dijkstra 算法和 Floyd 算法求最短路径的总结如表 6.4 所示。

表 6.4 BFS 算法、Dijkstra 算法和 Floyd 算法求最短路径的总结

1. 事件 $v_{k}$ 的最早发生时间 $v_{e}(k)$#

指从源点 $v_{1}$ 到顶点 $v_{k}$ 的最长路径长度。该值决定了所有从 $v_{k}$ 开始的活动能够开工的最早时间。可用以下递推公式计算：

$v_{e}$(源点)=0

其中，$v_k$ 是 $v_j$ 的任意后继，Weight $(v_j, v_k)$ 表示有向边 $<v_j, v_k>$ 上的权值。

NOTE

计算 $v_{e}()$ 时，可在拓扑排序过程中同步进行：

1. 初始时，令 $v_e[1...n] = 0$。
2. 每当输出一个入度为 0 的顶点 $v_j$，就计算其所有直接后继顶点 $v_k$ 的最早发生时间，若 $v_e[j] + \text{Weight}(v_j, v_k) > v_e[k]$，则更新 $v_e[k] = v_e[j] + \text{Weight}(v_j, v_k)$。重复此过程，直至输出全部顶点。

2. 事件 $v_{k}$ 的最迟发生时间 $v_{l}(k)$#

指在不推迟整个工程完成时间的前提下，事件 $v_{k}$ 必须发生的最晚时间，以保证其所有后继事件 $v_{j}$ 均不晚于各自的最迟发生时间 $v_{i}(j)$ 发生。可用以下递推公式计算：

其中，$v_{k}$ 是 $v_{j}$ 的任意前驱。

NOTE

计算 $v(k)$ 时，需按逆拓扑顺序进行。可在拓扑排序时用栈记录顶点顺序，排序结束后从栈顶到栈底即为逆拓扑序列。

1. 初始时，令 $v_l[1...n] = v_e[n]$。
2. 依次弹出栈顶顶点 $v_j$，计算其所有直接前驱顶点 $v_k$ 的最迟发生时间，若 $v_l[j] - \text{Weight}(v_k, v_j) < v_l[k]$，则更新 $v_l[k] = v_l[j] - \text{Weight}(v_k, v_j)$。重复此过程，直至栈空。

3. 活动 $a_{i}$ 的最早开始时间 $e(i)$#

指该活动所对应弧的起点事件的最早发生时间。若边 $\langle v_{k}, v_{j} \rangle$ 表示活动 $a_{i}$，则有

4. 活动 $a_{i}$ 的最迟开始时间 $l(i)$#

指在不延误工程总工期的前提下，活动 $a_i$ 最迟必须开始的时间，等于其终点事件的最迟发生时间与该活动所需时间之差。若边 $\leq v_k, v_j$ 表示活动 $a_i$，则有

5. 一个活动 $a_{i}$ 的最迟开始时间 $l(i)$ 与其最早开始时间 $e(i)$ 的差额：#

或称活动 $a_{i}$ 的时间余量。该值表示在不延长整个工程总工期的前提下，活动 $a_{i}$ 可以拖延的时间。若一个活动的时间余量为零，则该活动必须如期完成，否则将导致整个工程延期。因此，满足 $l(i)-e(i)=0$ [即 $l(i)=e(i)$] 的活动称为关键活动。

求关键路径的算法步骤如下：

1. 从源点出发，令 $v_{e}$(源点)=0，按拓扑有序求其余顶点的最早发生时间 $v_{e}$。
2. 从汇点出发，令 $v_{l}$(汇点) $=v_{e}$(汇点)，按逆拓扑有序求其余顶点的最迟发生时间 $v_{l}()$。
3. 根据各顶点的 $v_{e}()$ 值，求所有弧的最早开始时间 e()。
4. 根据各顶点的 $v_{1}()$ 值，求所有弧的最迟开始时间 $l()$。
5. 求 AOE 网中所有活动的时间余量 d()，找出所有 d()=0 的活动构成关键路径。

求解关键路径的具体过程，简单说明如下：

1. 求 $v_e()$：初始时 $v_e(1) = 0$。在拓扑排序输出顶点的过程中，依次求得 $v_e(2) = 3$，$v_e(3) = 2$，$v_e(4) = \max\{v_e(2) + 2, v_e(3) + 4\} = \max\{5, 6\} = 6$，$v_e(5) = 6$，$v_e(6) = \max\{v_e(5) + 1, v_e(4) + 2$，$v_e(3) + 3\} = \max\{7, 8, 5\} = 8$。

若本题为选择题，仅凭上述 $v_{e}()$ 的计算过程，通常已可推断出关键路径。

2. 求 $v_1()$：初始时 $v_1(6) = 8$。在逆拓扑排序(通过栈回溯)过程中，依次求得 $v_1(5) = 7$，$v_1(4) = 6$，$v_1(3) = \min\{v_1(4) - 4, v_1(6) - 3\} = \min\{2, 5\} = 2$，$v_1(2) = \min\{v_1(5) - 3, v_1(4) - 2\} = \min\{4, 4\} = 4$，$v_1(1)$ 必然为 0，无须额外计算。
3. 弧的最早开始时间 $e()$ 等于该弧的起点顶点的 $v_{e}()$ 值。
4. 弧的最迟开始时间 $l(i)$ 等于该弧的终点顶点的 $v_{i}$ 值减去该弧的权值。
5. 由 $l(i)-e(i)=0$ 可确定关键活动，最终得到的关键路径为 $(v_{1}, v_{3}, v_{4}, v_{6})$。

对于关键路径，需要注意以下几点：

1. 关键路径上的所有活动均为关键活动，它们共同决定了整个工程的工期。因此，加快关键活动的执行速度有可能缩短总工期。但不能任意缩短关键活动的持续时间，一旦过度缩短，原关键路径的长度可能小于其他路径，从而引发关键路径的转移。此时，即使继续压缩该活动，工程总工期已由新的最长路径决定，不再受其影响。
2. 网中的关键路径可能不止一条。当存在多条关键路径时，仅提高其中某一条路径上的关键活动速度，并不能缩短整个工程的工期。只有加快那些同时出现在所有关键路径上的关键活动(公共关键活动)，才能达到缩短工期的目的。

各种图算法在采用邻接矩阵或邻接表存储时的时间复杂度如表6.5所示。

表6.5 采用不同存储结构时各种图算法的时间复杂度

1. 关于图的基本操作#

本章中介绍的多数图算法均可适配邻接矩阵或邻接表存储结构，主要原因是在图的基本操作函数中保持了相同的参数和返回值，封装了内部实现细节。例如，函数 NextNeighbor(G, x, y) 用于返回顶点 x 在邻接顶点 y 之后的下一个邻接顶点。

1
int NextNeighbor(MGraph& G,int x,int y){
2
    if(x!=-1&&y!=-1){
3
        for(int col=y+1;col<G.vexnum;col++)
4
            if(G.Edge[x][col]>0 && G.Edge[x][col]<maxWeight)
5
                return col;    //maxWeight 代表∞
6
}
7
return -1;
8
}

1
int NextNeighbor(ALGraph& G,int x,int y){
2
    if(x!=-1){      //顶点x存在
3
        ArcNode *p=G.vertices[x].first;//对应边链表第一个边结点
4
        while(p!=NULL && p->data!=y) //寻找邻接顶点y
5
            p=p->next;
6
        if(p!=NULL && p->next!=NULL)
7
            return p->next->data; //返回下一个邻接顶点
8
    }
9
    return -1;
10
}

2. 关于图的遍历、连通性、生成树、关键路径的几个要点#

1. 在执行图的遍历时，由于图中可能存在回路，且任意顶点都可能与其他顶点相连，访问完某个顶点后可能沿某些边回到已访问过的顶点。因此，需设置辅助数组 visited[]标记顶点是否已被访问，以避免重复访问。
2. 深度优先搜索(DFS)采用回溯策略遍历图，通常通过递归实现。在递归访问某一邻接顶点前，必须先判断该顶点是否已被访问。此外，所有递归算法均可借助栈转换为非递归形式，DFS也不例外，具体实现参见6.3.4节综合应用题03。
3. 广度优先搜索(BFS)是一种分层遍历过程，每向前推进一层可能访问一批顶点，不存在回退操作，因此它不是递归过程。
4. 一个给定图的邻接矩阵表示是唯一的；但邻接表示则依赖于边的输入顺序，若输入次序不同，生成的邻接表也可能不同。
5. 最小生成树针对带权连通无向图，是从图中选出n-1条边构成的连通无环子图，使得所有边的权值总和最小。
6. 加速某一关键活动不一定能缩短整个工程的工期，因为 AOE 网中可能存在多条关键路径。只有那些出现在所有关键路径上的关键活动被加速时，才能有效缩短总工期。