考研笔记

拓扑排序与关键路径

关键路径是第 6 章唯一一个「四个参量、五个步骤」的固定流程题，也是本章综合题的主力。

它的难点不在思想，在四个量的定义方向相反： 取 Max 从前往后算， 取 Min 从后往前算； 看弧的起点， 看弧的终点减权值。方向搞反，整题全错。

机制

AOV 网与拓扑排序

AOV 网：用顶点表示活动、用有向边表示活动之间先后关系的有向无环图（DAG）。

拓扑排序：

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

逆拓扑排序（教材单列，关键路径要用）：

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

时间复杂度：采用邻接表 ；采用邻接矩阵 。

拓扑排序的三条注意

教材列的三条，第 2 条是高频考点：

1）入度为零的顶点，即没有前驱活动的或前驱活动都已经完成的顶点，工程可以从这个顶点所代表的活动开始或继续。

2）拓扑排序的结果可能不唯一。

不少人误认为「AOV 网的各顶点为线性序列」是拓扑序列唯一的充要条件，而它其实只是充分非必要条件。 拓扑序列是否唯一的判断条件是：在每次输出顶点时，检测入度为 0 的顶点是否唯一，若每次都唯一，则说明拓扑序列唯一。

3） AOV 网中各顶点的地位平等，每个顶点编号是人为的，因此可以按拓扑排序的结果重新编号，生成 AOV 网的新的邻接存储矩阵，这种邻接矩阵可以是三角矩阵；但对于一般的图来说，若其邻接矩阵是三角矩阵，则存在拓扑序列；反之则不一定成立。

边界辨析：

第 3 条的两个方向要分开记：

  • 邻接矩阵是三角矩阵 存在拓扑序列（成立）；
  • 存在拓扑序列 邻接矩阵是三角矩阵（不一定，因为顶点编号是人为的，没重新编号时矩阵可以不是三角）。

这是 2011、2024 两年「拓扑排序序列的存在性和唯一性分析」的直接考点。

有向无环图描述表达式

DAG 可以用来描述含公共子式的表达式：把重复出现的子表达式合并成同一个顶点，从而共享。做法是从叶结点（操作数）开始自底向上归并相同的子树。

考法固定：给一个表达式，问「用 DAG 描述至少需要多少个顶点」。答案 = 去重后的不同子表达式个数（含操作数）。

AOE 网

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

AOE 网和 AOV 网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的： AOE 网中的边有权值；而 AOV 网中的边无权值，仅表示顶点之间的前后关系。

AOE 网具有以下两个性质：

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

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

关键路径

在 AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。

因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

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

边界辨析：

「最短完成时间 = 最长路径长度」这个看似矛盾的表述，是关键路径全部的直觉。 因为所有路径上的活动必须全部完成，所以工程的耗时由最慢的那条路决定—— 这与 计组全书的第 ⑥ 条隐线「要整齐就得按最慢的来」 是同一个道理。

四个参量

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

源点

其中 取遍 的所有直接前驱， 表示 上的权值。

教材注意框：计算 值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算： ① 初始时，令 ； ② 输出一个入度为 0 的顶点 时，计算它所有直接后继顶点 的最早发生时间，若 ，则 。以此类推，直至输出全部顶点。

2. 事件 的最迟发生时间 ：指在不推迟整个工程完成的前提下，即保证它的后继事件 在其最迟发生时间 能够发生时，该事件最迟必须发生的时间。

汇点汇点

其中 取遍 的所有直接后继。

教材注意框：计算 值时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算。 增设一个栈以记录拓扑序列，拓扑排序结束后从栈顶至栈底便为逆拓扑有序序列。 ① 初始时，令 ； ② 栈顶顶点 出栈，计算其所有直接前驱顶点 的最迟发生时间，若 ，则 。

3. 活动 的最早开始时间 ：指该活动弧的起点所表示的事件的最早发生时间。若边 表示活动 ，则有 。

4. 活动 的最迟开始时间 ：指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边 表示活动 ，则有 。

5. 差额 ：指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动 可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称 即 的活动 是关键活动。

flowchart TD
    S1["① 从源点出发，令 vₑ(源点)=0<br/>按<b>拓扑有序</b>求其余顶点的 vₑ()<br/><b>取 Max，从前往后</b>"]
    S2["② 从汇点出发，令 v_l(汇点)=vₑ(汇点)<br/>按<b>逆拓扑有序</b>求其余顶点的 v_l()<br/><b>取 Min，从后往前</b>"]
    S3["③ 由各顶点的 vₑ() 求所有弧的<br/>最早开始时间 e()<br/><b>e(i) = vₑ(弧的起点)</b>"]
    S4["④ 由各顶点的 v_l() 求所有弧的<br/>最迟开始时间 l()<br/><b>l(i) = v_l(弧的终点) − 权值</b>"]
    S5["⑤ 求所有活动的差额 d() = l() − e()<br/><b>找出所有 d()=0 的活动</b><br/>构成关键路径"]
    S1 --> S2 --> S3 --> S4 --> S5

    classDef fwd fill:#e3f2fd,stroke:#1565c0,stroke-width:2px
    classDef bwd fill:#ffe0b2,stroke:#e65100,stroke-width:2px
    classDef fin fill:#c8e6c9,stroke:#1b5e20,stroke-width:2px
    class S1,S3 fwd
    class S2,S4 bwd
    class S5 fin

蓝色的两步向前算，橙色的两步向后算。 这是这道题唯一需要记的结构。

手算模板

拓扑排序：

  1. 列出所有顶点的入度。
  2. 每轮：选一个入度为 0 的顶点输出，把它的出边全删，相关顶点入度减 1。
  3. 若某轮有多个入度为 0 的顶点 → 拓扑序列不唯一（按题目规定的次序选，通常是编号最小）。

关键路径（照五步走，画一张四列表）：

活动 起点终点
  1. 先算 ：源点为 0，按拓扑序从前往后，每个顶点取「所有前驱的 + 边权」的最大值。
  2. 再算 ：汇点 ，按逆拓扑序从后往前，每个顶点取「所有后继的 − 边权」的最小值。
  3. 逐条边填上表的四列。
  4. 的边就是关键活动，把它们串起来就是关键路径。
  5. 验算：关键路径长度 汇点汇点，且关键路径上每个顶点都满足 。

边界

说法判断说明
「拓扑序列唯一 各顶点构成线性序列」❌只是充分非必要条件；判据是每次入度为 0 的顶点是否唯一
「有拓扑序列则邻接矩阵是三角矩阵」❌反之才成立；这个方向不一定
「AOV 网的边有权值」❌AOV 边无权，仅表示前后关系；AOE 边有权
「AOE 网可以有多个源点」❌仅有一个入度为 0 的顶点和一个出度为 0 的顶点
「关键路径是最短路径」❌是最长路径；但它等于工程的最短完成时间
「关键路径唯一」❌可能有多条， 的活动可能构成多条路径
「加快任一关键活动都能缩短工期」❌若有多条关键路径，必须同时缩短所有关键路径上的公共活动才有效
「 取 Min」❌取 Max（最长路径）； 才取 Min
「 是弧终点的最早发生时间」❌是起点的
「起点」❌是 终点 权值
「 的顶点是关键顶点」⚠️ 定义在**活动（边）**上；顶点的判据是
「 用拓扑序算」❌用逆拓扑序，且要用栈记录

口径差异：

算竞里拓扑排序就是 Kahn 或 DFS 后序，从不关心序列是否唯一； 「关键路径」这个词在算竞里根本不出现——那就是 DAG 上的最长路 DP，一遍 DP 就完了， 不会分成 //// 五个量。

408 要的正是这五个量的表。 直接用最长路 DP 算出答案，能得到关键路径， 但答不出「活动 的时间余量是多少」——而那恰恰是分值所在。 另外「拓扑序列是否唯一」这个问法在算竞里几乎不存在，408 考了两年（2011、2024）。

对照速查

AOV 网AOE 网
顶点表示活动事件
边表示活动之间的前后关系活动
边有无权无权有权（开销）
都是有向无环图有向无环图
典型问题拓扑排序关键路径
量方向取公式
从前往后（拓扑序）Max， 是前驱
从后往前（逆拓扑序）Min， 是后继
——弧的起点
——弧的终点
——； 即关键活动
复杂度值
拓扑排序（邻接表）
拓扑排序（邻接矩阵）
关键路径与拓扑排序同阶

考点

  • 拓扑排序序列的存在性和唯一性分析（2011、2024 命题追踪）——唯一性判据。
  • 邻接矩阵为三角矩阵与拓扑序列的单向蕴涵关系。
  • AOV 与 AOE 的三点差别（顶点含义、边含义、边有无权）。
  • 关键路径的性质（2020 命题追踪）：最长路径 = 最短完成时间。
  • 求关键路径的实例（2019、2022 命题追踪）——五步流程 + 四列表。
  • 四个参量的方向： 取 Max 向前， 取 Min 向后。
  • 关键路径可能不唯一，缩短工期要看公共活动。

链接

反向链接