408答疑

---

---

四、图的应用

图的应用是历年考研考查的重点。

图的应用考查形式

一般而言，这部分内容直接以算法设计题形式考查的可能性很小，更多的是结合图的实例来考查算法的具体操作过程。因此，图的应用要求至少掌握手工模拟图的各个算法的执行过程。此外，还需掌握对给定模型建立相应的图去解决问题的方法。

最小生成树

最小生成树问题是指在图中找到一个包含所有顶点的最小权重的边的集合，使得这些边构成一棵树。这个问题在网络设计、电路板设计等领域有广泛应用。

最小生成树概念

最小生成树（Minimum Spanning Tree, MST）是一个连通图的生成树，包含图中的所有顶点，并且只含尽可能少的边。最小生成树可以用Prim（普里姆）算法或Kruskal（克鲁斯卡尔）算法求出。

最小生成树的性质

1. 唯一性：若图 $G$ 中存在权值相同的边，则 $G$ 的最小生成树可能不唯一，即最小生成树的树形不唯一。当图 $G$ 中的各边权值互不相等时，$G$ 的最小生成树是唯一的；若无向连通图 $G$ 的边数比顶点数少 1，即 $G$ 本身是一棵树时，则 $G$ 的最小生成树就是它本身。
2. 权值之和：虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。
3. 边数：最小生成树的边数为顶点数减 1。

最小生成树中某顶点到其他顶点是否具有最短路径的分析

最小生成树中所有边的权值之和最小，但不能保证任意两个顶点之间的路径是最短路径。例如，最小生成树中 $A$ 到 $C$ 的路径长度为 5，但图中 $A$ 到 $C$ 的最短路径长度为 4。

构造最小生成树的算法

构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质：假设 $G=(V,E)$ 是一个带权连通无向图，$U$ 是顶点集 $V$ 的一个非空子集。若 $(u,v)$ 是一条具有最小权值的边，其中 $u\in U$，$v\in V-U$，则必存在一棵包含边 $(u,v)$ 的最小生成树。

基于该性质的最小生成树算法主要有 Prim 算法和 Kruskal 算法，它们都基于贪心算法的策略。对这两种算法应主要掌握算法的本质含义和基本思想，并能动手模拟算法的实现步骤。

Prim 算法

Prim 算法概述

Prim（普里姆）算法是从顶点的方面考虑构建最小生成树（MST）的一种贪心算法。其执行过程类似于寻找图的最短路径的Dijkstra算法。

Prim 算法的构建思想

• 设图 $G$ 顶点集合为 $U$，首先任意选择图 $G$ 中的一点作为起始点 $a$，将该点加入集合 $V$，再从集合 $U-V$ 中找到另一点 $b$ 使得点 $b$ 到 $V$ 中任意一点的权值最小，此时将 $b$ 点也加入集合 $V$；以此类推，现在的集合 V = { a , b } V=\{a, b\} V={a,b}，再从集合 $U-V$ 中找到另一点 $c$ 使得点 $c$ 到 $V$ 中任意一点的权值最小，此时将 $c$ 点加入集合 $V$，直至所有顶点全部被加入 $V$，此时就构建出了一颗MST。

• 因为有 $N$ 个顶点，所以该MST就有 $N-1$ 条边，每一次向集合 $V$ 中加入一个点，就意味着找到一条MST的边。

Prim 算法的步骤

1. 初始化：向空树 $T=(U,E_T)$ 中添加图 $G=(V,E)$ 的任意一个顶点 $u_0$，使 U = { u 0 } U=\{u_0\} U={u0​}，$E_T=\varnothing$。
2. 循环（重复下列操作直至 $U=V$）：从图 $G$ 中选择满足 $\{(u,v)|u\in U,v\in V-U\}$ 且具有最小权值的边 $(u,v)$，加入树 $T$，置 U = U ∪ { v } U=U \cup \{v\} U=U∪{v}，$E_T=E_T\cup \{(u,v)\}$。

Prim 算法的示例

下图展示了 Prim 算法构造最小生成树的过程，从顶点 $V_1$ 开始，逐步添加顶点和边，直到所有顶点都被包含在内，形成最小生成树。

Prim 算法的性质

Prim算法的时间复杂度为 $O(|V{|}^2)$，不依赖于 $|E|$，因此它适用于求解边稠密的图的最小生成树。虽然采用其他方法能改进Prim算法的时间复杂度，但增加了实现的复杂性。

Kruskal 算法

Kruskal 算法概述

Kruskal算法是从边的方面考虑构建最小生成树（MST）的一种贪心算法。与Prim算法从顶点开始扩展最小生成树不同，Kruskal算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

Kruskal 算法的构建思想

• 初始时为只有 $n$ 个顶点而无边的非连通图 T = { V , { } } T = \{V, \{\}\} T={V,{}}，每个顶点自成一个连通分量。
• 然后按照边的权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在 $T$ 中不同的连通分量上（使用并查集判断这两个顶点是否属于同一棵集合树），则将此边加入 $T$，否则舍弃此边而选择下一条权值最小的边。以此类推，直至 $T$ 中所有顶点都在一个连通分量上。

Kruskal 算法的步骤

1. 初始化：$U=V,E_T=\varnothing$。即每个顶点构成一棵独立的树，$T$ 此时是一个仅含 $|V|$ 个顶点的森林。
2. 循环（重复直至 $T$ 是一棵树）：按 $G$ 的边的权值递增顺序依次从 $E-E_T$ 中选择一条边，若这条边加入 $T$ 后不构成回路，则将其加入 $E_T$，否则舍弃，直到 $E_T$ 中含有 $n-1$ 条边。

Kruskal 算法的示例

Kruskal 算法的性质

根据图的相关性质，若一条边连接了两棵不同树中的顶点，则对这两棵树来说，它必定是连通的，将这条边加入森林中，完成两棵树的合并，直到整个森林合并成一棵树。

在Kruskal算法中，最坏情况需要对$|E|$条边各扫描一次。通常采用堆来存放边的集合，每次选择最小权值的边需要 $O({\log }_2|E|)$ 的时间；每次使用并查集来快速判断两个顶点是否属于一个集合所需的时间为 $O(\alpha (|V|))$，$\alpha (|V|)$ 的增长极其缓慢，可视为常数。算法的总时间复杂度为 $O(|E|{\log }_2|E|)$，不依赖于 $|V|$，因此 Kruskal 算法适合于边稀疏而顶点较多的图。

最短路径

最短路径问题是指在图中找到从一个顶点到另一个顶点的路径，使得路径的总权重最小。这个问题在路由选择、物流配送等领域有重要应用。

概述

图的最短路径问题是指，在有向图中找到一条从源点到达终点的路径，这条路径上的边权和总和达到最小，这意味着，如果存在多条路径可以从源点到达终点，最短路径是指这些路径中权值总和最小的那一条。

最短路径问题的分类

带权有向图 $G$ 的最短路径问题一般可分为两类：

1. 单源最短路径：即求图中某一顶点到其他各顶点的最短路径，可通过经典的 Dijkstra（迪杰斯特拉）算法求解；
2. 每对顶点间的最短路径：可通过 Floyd（弗洛伊德）算法来求解。

求解最短路径的算法通常都依赖于一种性质，即两点之间的最短路径也包含了路径上其他顶点间的最短路径。

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

Dijkstra算法是一种用于求解单源最短路径问题的算法，适用于带权有向图或带权无向图。该算法通过逐步扩展已知最短路径的顶点集合来找到从源点到图中所有其他顶点的最短路径。

Dijkstra算法的基本原理

Dijkstra算法设置一个集合 $S$ 记录已求得的最短路径的顶点，初始时把源点 $v_0$ 放入 $S$，集合 $S$ 每并入一个新顶点 $v_i$，都要修改源点 $v_0$ 到集合 $V-S$ 中顶点当前的最短路径长度值。

在构造的过程中还设置了三个辅助数组：

• final[]：标记各顶点是否已找到最短路径，即是否归入集合 $S$。
• dist[]：记录从源点 $v_0$ 到其他各顶点当前的最短路径长度，$dist[i]$ 的初始值为：若从 $v_0$ 到 $v_i$ 有弧，则 $dist[i]$ 为弧上的权值；否则置 $dist[i]$ 为 $\infty$。
• path[]：记录从源点到顶点 $i$ 之间的最短路径的前驱结点。在算法结束时，可根据其值追溯得到源点 $v_0$ 到顶点 $v_i$ 的最短路径。

Dijkstra算法的步骤

假设从顶点 $v_0$ 出发，即 $v_0=0$，集合 $S$ 最初只包含顶点 $0$，邻接矩阵 $arcs$ 表示带权有向图，$arcs[i][j]$ 表示有向边 $<i,j>$ 的权值，若不存在有向边 $<i,j>$，则 $arcs[i][j]$ 为 $\infty$。

Dijkstra算法的步骤如下（不考虑对 $path[]$ 的操作）：

1. 初始化：集合 $S$ 初始化为 { 0 } \{0\} {0}，$dist[]$ 的初始值 $dist[0][i]=arcs[0][i],i=1,2,...,n-1$。
2. 从顶点集合 $V-S$ 中选出 $v_j$，满足 d i s t [ j ] = min ⁡ { d i s t [ j ] ∣ v j ∈ V − S } dist[j]=\min\{dist[j] | v_j \in V-S\} dist[j]=min{dist[j]∣vj​∈V−S}，$v_j$ 就是当前求得的一条从 $v_0$ 出发的最短路径的终点，令 S = S ∪ { v j } S=S \cup \{v_j\} S=S∪{vj​}。
3. 修改从 $v_0$ 出发到集合 $V-S$ 上任意一个顶点 $v_k$ 可达的最短路径长度：若 $dist[j]+arcs[j][k]<dist[k]$，则更新 $dist[k]=dist[j]+arcs[j][k]$。
4. 重复步骤 2）~3）操作共 $n-1$ 次，直到所有的顶点都包含在集合 $S$ 中。

实例说明

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

• 初始化：集合 $S$ 初始为 { v 1 } \{v_1\} {v1​}，$v_1$ 可达 $v_2$ 和 $v_5$，$v_1$ 不可达 $v_3$ 和 $v_4$，因此 $dist[]$ 数组各元素的初始值依次设置为 $dist[2]=10$，$dist[3]=\infty$，$dist[4]=\infty$，$dist[5]=5$。

• 第1轮：选出最小值 $dist[5]$，将顶点 $v_5$ 并入集合 $S$，即此时已找到 $v_1$ 到 $v_5$ 的最短路径。当 $v_5$ 加入 $S$ 后，从 $v_1$ 到集合 $V-S$ 中可达顶点的最短路径长度可能会产生变化。因此需要更新 $dist[]$ 数组。$v_5$ 可达 $v_2$，因 $v_1\to v_5\to v_2$ 的距离 8 比 $dist[2]=10$ 小，更新 $dist[2]=8$；$v_5$ 可达 $v_3$，$v_1\to v_5\to v_3$ 的距离 14，更新 $dist[3]=14$；$v_5$ 可达 $v_4$，$v_1\to v_5\to v_4$ 的距离 7，更新 $dist[4]=7$。

• 第 2 轮：选出最小值 $dist[4]$，将顶点 $v_4$ 并入集合 $S$。继续更新 $dist[]$ 数组。$v_4$ 不可达 $v_2$；$dist[2]$ 不变；$v_4$ 可达 $v_3$，$v_1\to v_5\to v_4\to v_3$ 的距离 13 比 $dist[3]$ 小，故更新 $dist[3]=13$。

• 第 3 轮：选出最小值 $dist[2]$，将顶点 $v_2$ 并入集合 $S$。继续更新 $dist[]$ 数组。$v_2$ 可达 $v_3$，$v_1\to v_5\to v_2\to v_3$ 的距离 9 比 $dist[3]$ 小，更新 $dist[3]=9$。

• 第 4 轮：选出唯一最小值 $dist[3]$，将顶点 $v_3$ 并入集合 $S$，此时全部顶点都已包含在 $S$ 中。

下表为从$v_1$到各终点的 dist 值和最短路径的求解过程

顶点	第1轮	第2轮	第3轮	第4轮
2	10 $v_1\to v_2$	8 $v_1\to v_5\to v_2$	8 $v_1\to v_5\to v_2$
3	∞	14 $v_1\to v_5\to v_3$	13 $v_1\to v_5\to v_4\to v_3$	9 $v_1\to v_5\to v_2\to v_3$
4	∞	7 $v_1\to v_5\to v_4$
5	5 $v_1\to v_5$
集合S	{1, 5}	{1, 5, 4}	{1, 5, 4, 2}	{1, 5, 4, 2, 3}

每轮得到的最短路径

• 第1轮：1→5，路径距离为 5
• 第2轮：1→5→4，路径距离为 7
• 第3轮：1→5→2，路径距离为 8
• 第4轮：1→5→2→3，路径距离为 9

显然，Dijkstra 算法也是基于贪心策略的。

Dijkstra算法的性质

• Dijkstra算法的流程、操作与Prim算法的都很相似，都基于贪心策略。区别在于，目的不同：Dijkstra算法的目的是构建单源点的最短路径树；Prim算法的目的是构建最小生成树。
• 算法思路略有不同：Prim算法从一个点开始，每次选择权值最小的边，将其连接到已构建的生成树上，直至所有顶点都已加入；而Dijkstra算法每次找出到源点距离最近且未归入集合的点，并把它归入集合，同时以这个点为基础更新从源点到其他所有顶点的距离。
• 适用的图不同：Prim算法只能用于带权无向图。Dijkstra算法可用于带权有向图或带权无向图。

Dijkstra算法的时间复杂度

• 使用邻接矩阵表示时，时间复杂度为 $O(|V{|}^2)$。
• 使用带权的邻接表表示时，虽然修改 $dist[]$ 的时间可以减少，但因为在 $dist[]$ 中选择最小分量的时间不变，所以时间复杂度仍为 $O(|V{|}^2)$。

注意事项

• 边上带有负权值时，Dijkstra算法并不适用。若允许边上带有负权值，则在与集合 $S$（已求得最短路径的顶点集，归入 $S$ 内的顶点的最短路径不再变更）内某顶点（记为 $a$）以负边相连的顶点（记为 $b$）确定其最短路径时，其最短路径长度加上这条负边的权值结果可能小于 $a$ 原先确定的最短路径长度，而此时 $a$ 在 Dijkstra算法下是无法更新的。例如，对于下图所示的带权有向图，利用 Dijkstra算法不一定能得到正确的结果。

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

问题描述

求所有顶点之间的最短路径问题描述如下：已知一个各边权值均大于0的带权有向图，对任意两个顶点$v_i$和$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$个顶点的运算步骤。初始时，对于任意两个顶点$v_i$和$v_j$，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以$\infty$作为它们之间的最短路径长度。以后逐步尝试在原路径中加入顶点$k$（$k=0,1,\cdots ,n-1$）作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径。

算法描述

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

$$A^{(-1)}[i][j]=\text{arcs}[i][j]$$

A ( k ) [ i ] [ j ] = min ⁡ { A ( k − 1 ) [ i ] [ j ] , A ( k − 1 ) [ i ] [ k ] + A ( k − 1 ) [ k ] [ j ] } , k = 0 , 1 , ⋯ , n − 1 A^{(k)}[i][j] = \min\{A^{(k-1)}[i][j], A^{(k-1)}[i][k] + A^{(k-1)}[k][j]\}, \quad k = 0, 1, \cdots, n-1 A(k)[i][j]=min{A(k−1)[i][j],A(k−1)[i][k]+A(k−1)[k][j]},k=0,1,⋯,n−1

式中，$A^{(0)}[i][j]$是从顶点$v_i$到$v_j$，中间顶点是$v_0$的最短路径的长度，$A^{(k)}[i][j]$是从顶点$v_i$到$v_j$，中间顶点的序号不大于$k$的最短路径的长度。Floyd算法是一个迭代的过程，每迭代一次，在从$v_i$到$v_j$的最短路径上就多考虑了一个顶点：经过$n$次迭代后，所得到的$A^{(n-1)}[i][j]$就是$v_i$到$v_j$的最短路径长度，即方阵$A^{(n-1)}$中就保存了任意一对顶点之间的最短路径长度。

实例说明

下图所示为带权有向图 G 及其邻接矩阵，应用 Floyd 算法执行过程的说明如下：

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

• 第 1 轮：将 $v_0$ 作为中间顶点，对于所有顶点对 { i , j } \{i, j\} {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]>A^{-1}[2][0]+A^{-1}[0][1]=11$，更新 $A^{-1}[2][1]=11$，更新后的方阵标记为 $A^0$。

• 第 2 轮：将 $v_1$ 作为中间顶点，继续检测全部顶点对 { i , j } \{i, j\} {i,j}。

  • 有 $A^0[0][2]>A^0[0][1]+A^0[1][2]=10$，更新 $A^0[0][2]=10$，更新后的方阵标记为 $A^1$。

• 第 3 轮：将 $v_2$ 作为中间顶点，继续检测全部顶点对 { i , j } \{i, j\} {i,j}。

  • 有 $A^1[1][0]>A^1[1][2]+A^1[2][0]=9$，更新 $A^1[1][0]=9$，更新后的方阵标记为 $A^2$。此时 $A^2$ 中保存的就是任意顶点对的最短路径长度。

Floyd算法的执行过程
A	A(-1)			A(0)			A(1)			A(2)
	V0	V1	V2	V0	V1	V2	V0	V1	V2	V0	V1	V2
V0	0	6	13	0	6	13	0	6	10	0	6	10
V1	10	0	4	10	0	4	10	0	4	9	0	4
V2	5	∞	0	5	11	0	5	11	0	5	11	0

说明：

1. 表格展示了 Floyd 算法迭代过程中各阶段的邻接矩阵：
   • $A$ 为初始邻接矩阵
   • $A^{(k)}$ 表示经过顶点 $V_k$ 计算后的结果
2. 数值变化示例：
   • $A^{(1)}$ 中 $V_0\to V_2$ 的路径从 13 缩短为 10（通过 $V_1$）
   • $A^{(2)}$ 中 $V_1\to V_0$ 的路径从 10 缩短为 9（通过 $V_2$）
3. $\infty$ 表示两顶点间无直接路径。

算法复杂度

Floyd算法的时间复杂度为$O(|V{|}^3)$。不过由于其代码很紧凑，且并不包含其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。

Floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。

应用

也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次Dijkstra算法，其时间复杂度为$O(|V{|}^2)\cdot |V|=O(|V{|}^3)$。

BFS 算法、Diikstra 算法和 Floyd 算法求最短路径的总结

算法	用途	无权图	带权图	带负权值的图	带负权回路的图	时间复杂度
BFS算法	求单源最短路径	适用	不适用	不适用	不适用	$O($|$V$|${}^2)$或$O($|$V$|+|$E$|$)$
Dijkstra算法	求单源最短路径	适用	适用	不适用	不适用	$O($|$V$|${}^2)$
Floyd算法	求各顶点之间的最短路径	适用	适用	适用	不适用	$O($|$V$|${}^3)$

有向无环图描述表达式

有向无环图 (DAG)

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图。

构建表达式的有向无环图

有向无环图是描述含有公共子式的表达式的有效工具。例如表达式 $((a+b)\ast (b\ast (c+d))+(c+d)\ast e)\ast ((c+d)\ast e))$ 可以用二叉树来表示，如下图所示。

仔细观察该表达式，可发现有一些相同的子表达式 $(c+d)$ 和 $(c+d)\ast e$，而在二叉树中，它们也重复出现。若利用有向无环图，则可实现对相同子式的共享，从而节省存储空间，下图所示为该表达式的有向无环图表示。

注意事项

在表达式的有向无环图表示中，不可能出现重复的操作数顶点。

拓扑排序

拓扑排序是指对一个有向无环图（DAG）的顶点进行排序，使得对于每一对有向边 $(u,v)$，顶点 $u$ 在顶点 $v$ 之前。拓扑排序在任务调度、课程安排等领域有广泛应用。

相关概念

拓扑排序是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 $A$ 到顶点 $B$ 的路径，那么在序列中顶点 $A$ 必须出现在顶点 $B$ 的前面。

或者可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点 $A$ 到顶点 $B$ 的路径，则在排序中 $B$ 出现在 $A$ 的后面。每个 AOV 网都有一个或多个拓扑排序序列。

用途

拓扑排序主要用于：

• 判断图是否有回路。
• 用来规定顶点活动的开展顺序。

AOV 网

AOV 网：若用有向无环图表示一个工程，其顶点表示活动，用有向边 $<V_i,V_j>$ 表示活动 $V_i$ 必须先于活动 $V_j$ 进行的这样一种关系，则将这种有向图称为顶点表示活动的网络，简称 AOV 网。在 AOV 网中，活动 $V_i$ 是活动 $V_j$ 的直接前驱，$V_j$ 是 $V_i$ 的直接后继，这种前驱和后继关系具有传递性，且任何活动 $V_i$ 不能以它自己作为自己的前驱或后继。

拓扑排序的步骤

对一个 AOV 网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：

1. 从 AOV 网中选择一个没有前驱（入度为 0）的顶点并输出。
2. 从网中删除该顶点和所有以它为起点的有向边。
3. 重复步骤 1 和 2 直到当前的 AOV 网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

拓扑排序的实例

下图所示为拓扑排序过程的示例。每轮选择一个入度为 0 的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为 {1, 2, 4, 3, 5}。

结点号	1	2	3	4	5
初始入度	0	1	2	2	2
第1轮		0	2	1	2
第2轮			1	0	2
第3轮			0		1
第4轮					0

不同存储方式下的拓扑排序的效率

• 因为输出每个顶点的同时还要删除以它为起点的边，所以采用邻接表存储时拓扑排序的时间复杂度为 $O(|V|+|E|)$，采用邻接矩阵存储时拓扑排序的时间复杂度为 $O(|V{|}^2)$。

DFS 实现拓扑排序的思想

• 利用深度优先遍历也可以实现拓扑排序。
• 对于有向无环图 $G$ 中的任意结点 $u,v$，它们之间的关系必然是下列三种之一：
  1. 若 $u$ 是 $v$ 的祖先，则在调用 DFS 访问 $u$ 之前，必然已对 $v$ 进行了 DFS 访问，即 $v$ 的 DFS 结束时间先于 $u$ 的 DFS 结束时间。从而可考虑在 DFS 函数中设置一个时间标记，在 DFS 调用结束时，对各顶点计时。因此，祖先的结束时间必然大于子孙的结束时间。
  2. 若 $u$ 是 $v$ 的子孙，则 $v$ 为 $u$ 的祖先，按上述思路，$v$ 的结束时间大于 $u$ 的结束时间。
  3. 若 $u$ 和 $v$ 没有路径关系，则 $u$ 和 $v$ 在拓扑序列的关系任意。

于是，按结束时间从大到小排列，就可以得到一个拓扑排序序列。

逆拓扑排序

定义

逆拓扑排序是另一种针对有向无环图（AOV网）的一种排序方法，其步骤如下：

1. 选择顶点：从 AOV 网中选择一个没有后继（出度为 0）的顶点并输出。
2. 删除顶点：从网中删除该顶点和所有以它为终点的有向边。
3. 重复操作：重复步骤 1 和 2 直到当前的 AOV 网为空。

应用

逆拓扑排序常用于确定任务的执行顺序，特别是在项目管理和编译原理中，用于确保任务按照依赖关系正确执行。

注意事项

用拓扑排序算法处理 AOV 网时，应注意以下问题：

1. 入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。
2. 若一个顶点有多个直接后继，则拓扑排序的结果通常不唯一；但若各个顶点已经排在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，则拓扑排序的结果是唯一的。
3. 由于 AOV 网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成 AOV 网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

关键路径

关键路径是指在项目管理中，从项目开始到项目结束的最长路径。关键路径上的活动决定了项目的最短完成时间，对项目管理和进度控制有重要意义。
在AOE网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

• 关键路径的影响
  完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。

AOE网与AOV网

• AOV网：AOV网中的边无权值，仅表示顶点之间的前后关系。
• AOE网：在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网。

AOE 网和 AOV 网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的，AOE 网中的边有权值，而 AOV网中的边无权值。

AOE网的性质

AOE网具有以下两个性质：

1. 只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
2. 只有在进入某顶点的各向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

在 AOE 网中仅有一个入度为 0 的顶点，称为开始顶点（源点），它表示整个工程的开始；也仅有一个出度为 0 的顶点，称为结束顶点（汇点），它表示整个工程的结束。

关键路径分析参数

事件的最早发生时间 $v_e(k)$

定义

事件 $v_k$ 的最早发生时间是指从源点 $v_1$ 到顶点 $v_k$ 的最长路径长度。它决定了所有从 $v_k$ 开始的活动能够开工的最早时间。

计算公式

• $v_e(\text{源点})=0$
• v e ( k ) = max ⁡ { v e ( j ) + Weight ( v j , v k ) } , v k 为  v j 的任意后继 v_e(k) = \max\{v_e(j) + \text{Weight}(v_j, v_k)\}, v_k \text{ 为 } v_j \text{ 的任意后继} ve​(k)=max{ve​(j)+Weight(vj​,vk​)},vk​ 为 vj​ 的任意后继，$\text{Weight}(v_j,v_k)$ 表示 $<v_j,v_k>$ 上的权值。

注意事项

计算 $v_e()$ 值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算：

1. 初始时，令 $v_e[\mathrm{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)$。以此类推，直至输出全部顶点。

事件的最迟发生时间 $v_l(k)$

定义

事件 $v_k$ 的最迟发生时间是指在不推迟整个工程完成的前提下，即保证它的后继事件 $v_j$ 在其最迟发生时间 $v_l(j)$ 能够发生时，该事件最迟必须发生的时间。

计算公式

• $v_l(\text{汇点})=v_e(\text{汇点})$
• v l ( k ) = min ⁡ { v l ( j ) − Weight ( v k , v j ) } , v k 为  v j 的任意前驱 v_l(k) = \min\{v_l(j) - \text{Weight}(v_k, v_j)\}, v_k \text{ 为 } v_j \text{ 的任意前驱} vl​(k)=min{vl​(j)−Weight(vk​,vj​)},vk​ 为 vj​ 的任意前驱

注意事项

计算 $v_l(k)$ 值时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算。增设一个栈以记录拓扑序列，拓扑排序结束后从栈底至栈顶便为逆拓扑有序序列。过程如下：

1. 初始时，令 $v_l[\mathrm{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)$。以此类推，直至输出全部栈中顶点。

活动 $a_i$ 的最早开始时间 $e(i)$

• 定义：它是指该活动弧的起点所表示的事件的最早发生时间。若边 $<v_k,v_j>$ 表示活动 $a_i$，则有 $e(i)=v_e(k)$。

活动 $a_i$ 的最迟开始时间 $l(i)$

• 定义：它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边 $<v_k,v_j>$ 表示活动 $a_i$，则有 $l(i)=v_l(j)-\text{Weight}(v_k,v_j)$。

活动 $a_i$ 的时间余量 $d(i)$

• 定义：一个活动 $a_i$ 的最迟开始时间 $l(i)$ 和其最早开始时间 $e(i)$ 的差额 $d(i)=l(i)-e(i)$。
• 意义：它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动 $a_i$ 可以拖延的时间。
• 关键活动：若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称 $l(i)-e(i)=0$ 即 $l(i)=e(i)$ 的活动 $a_i$ 是关键活动。

关键路径的实例

求关键路径的算法步骤

1. 从源点出发，令 $v_e(\text{源点})=0$，按拓扑有序求其余顶点的最早发生时间 $v_e()$。
2. 从汇点出发，令 $v_l(\text{汇点})=v_e(\text{汇点})$，按逆拓扑有序求其余顶点的最迟发生时间 $v_l()$。
3. 根据各顶点的 $v_e()$ 值求所有弧的最早开始时间 $e()$。
4. 根据各顶点的 $v_l()$ 值求所有弧的最迟开始时间 $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(4) = \max\{v_e(2) + 2, v_e(3) + 4\} = \max\{5, 6\} = 6 ve​(4)=max{ve​(2)+2,ve​(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(6) = \max\{v_e(5) + 1, v_e(4) + 2, v_e(3) + 3\} = \max\{7, 8, 5\} = 8 ve​(6)=max{ve​(5)+1,ve​(4)+2,ve​(3)+3}=max{7,8,5}=8。
2. 求 $v_l()$：初始 $v_l(6)=8$，在逆拓扑排序出栈过程中，求得 $v_l(5)=7$，$v_l(4)=6$， v l ( 3 ) = min ⁡ { v l ( 4 ) − 4 , v l ( 6 ) − 3 } = min ⁡ { 2 , 5 } = 2 v_l(3) = \min\{v_l(4) - 4, v_l(6) - 3\} = \min\{2, 5\} = 2 vl​(3)=min{vl​(4)−4,vl​(6)−3}=min{2,5}=2， v l ( 2 ) = min ⁡ { v l ( 5 ) − 3 , v l ( 4 ) − 2 } = min ⁡ { 4 , 4 } = 4 v_l(2) = \min\{v_l(5) - 3, v_l(4) - 2\} = \min\{4, 4\} = 4 vl​(2)=min{vl​(5)−3,vl​(4)−2}=min{4,4}=4，$v_l(1)$ 必然为 0 而无须再求。
3. 弧的最早开始时间 $e(i)$ 等于该弧的起点的顶点的 $v_e()$，结果如下表。
4. 弧的最迟开始时间 $l(i)$ 等于该弧的终点的顶点的 $v_l()$ 减去该弧持续的时间，结果如下表。
5. 根据 $l(i)-e(i)=0$ 的关键活动，得到的关键路径为 $(v_1,v_3,v_4,v_6)$。

缩短工期的相关分析

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

1. 关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可以通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定程度，该关键活动就可能会变成非关键活动。
2. 网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

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

算法	邻接矩阵	邻接表
Dijkstra	$O(n^2)$	-
Floyd	$O(n^3)$	-
Prim	$O(n^2)$	-
Kruskal	-	$O(e\log e)$
DFS	$O(n^2)$	$O(n+e)$
BFS	$O(n^2)$	$O(n+e)$
拓扑排序	$O(n^2)$	$O(n+e)$
关键路径	$O(n^2)$	$O(n+e)$

六、参考资料

鲍鱼科技课件

b站免费王道课后题讲解:

网课全程班:

26王道考研书