第 6 章图

408 数据结构第 6 章图复习讲义，涵盖核心概念、重点考点与典型题型。

一、第 6 章到底在学什么

前面的线性表是“一对一”，树是“一对多”，到了图就是最一般的：

多对多关系。

所以图这一章真正要解决的问题，可以归纳成 5 类：

怎么表示一个复杂关系？ → 邻接矩阵、邻接表、十字链表、邻接多重表。
怎么把所有顶点走一遍？ → BFS、DFS。
怎么用最低成本把所有点连起来？ → 最小生成树 MST：Prim、Kruskal。
怎么找到两点之间最低成本的路线？ → BFS、Dijkstra、Floyd。
如果顶点之间存在先后依赖关系怎么办？ → 拓扑排序、关键路径。

本章的复习优先级，建议你按下面掌握：

重要度	内容	要求
★★★★★	BFS、DFS	必须会手算遍历序列、生成树、复杂度
★★★★★	Prim、Kruskal	必须会逐步构造 MST
★★★★★	Dijkstra、Floyd	必须会手算更新过程
★★★★★	拓扑排序	必须会手推、判断环
★★★★★	关键路径	必须会算 ve、vl、e、l、余量
★★★★☆	邻接矩阵、邻接表	高频选择题
★★★☆☆	图的度、连通、强连通、生成树	高频基础题
★★☆☆☆	十字链表、邻接多重表	理解结构特点即可
★★☆☆☆	DAG 表达式	重点理解公共子表达式共享

资料中的考点追踪也显示：邻接矩阵、DFS/BFS、Prim/Kruskal、Dijkstra、拓扑排序、关键路径在历年统考中都有反复出现。

二、6.1 图的基本概念

1. 图的定义

图由顶点集合和边集合组成：

G = (V, E)

其中：

$V$ ：顶点集合；
$E$ ：边集合。

特别注意：

图不能没有顶点，但可以没有边。

也就是说，空边集可以，但顶点集不能为空。

三、有向图和无向图

1. 无向图

一条边连接 $u, v$ ，没有方向。

例如：

(u, v)

和

(v, u)

表示的是同一条边。

可以理解成：

A 和 B 是朋友。

2. 有向图

边具有方向，又称“弧”。

例如：

⟨ u, v ⟩

表示：

从 $u$ 指向 $v$ 。

其中：

$u$ ：弧尾；
$v$ ：弧头。

例如：

A → B

只能说明 A 能到 B，不能自动说明 B 能到 A。

这是后面“连通”和“强连通”区别的根源。

四、简单图、多重图

408 默认讨论的是简单图。

简单图要求：

不允许自环；
不允许两顶点之间出现重复边。

例如下面是不允许的：

A ── A          自环

A ══ B          两条重复边

五、度、入度、出度——高频基础

这是选择题非常喜欢考的地方。

1. 无向图

一个顶点的“度”：

与这个顶点关联的边数。

因为一条无向边连接两个顶点，所以所有顶点的度数之和：

v \in V \sum T D (v) = 2∣ E ∣

这就是所谓的握手定理。

例如一个无向图有 10 条边，那么：

\sum T D (v) = 20

2. 有向图

有两个概念：

入度：有多少条边指向自己；
出度：自己发出去多少条边。

因此：

T D (v) = I D (v) + O D (v)

而整个有向图中：

\sum I D (v) = \sum O D (v) = ∣ E ∣

因为每条有向边恰好：

给起点贡献 1 个出度；
给终点贡献 1 个入度。

这也是邻接矩阵题的理论基础。

六、路径、回路、简单路径

这部分最容易在概念题里绕。

例如：

A → B → C → D

从 A 到 D 是一条路径。

路径长度

注意：

路径长度一般指经过的边数，不是顶点数。

A-B-C-D 一共有 4 个顶点，但只有 3 条边，因此路径长度为 3。

回路

若起点和终点相同，例如：

A → B → C → A

就是回路，也叫环。

简单路径

路径中顶点不能重复。

简单回路

除首尾顶点相同外，其余顶点不能重复。

七、一个非常重要的判环结论

对于一个含 $n$ 个顶点的无向图：

如果边数大于：

n - 1

那么一定存在环。

为什么？

因为一棵包含 $n$ 个顶点的树最多只能有：

n - 1

条边而没有环。

再加任何一条边，都必然形成环。

但是反过来不能说：

边数不超过 $n - 1$ 就一定无环。

例如两个独立的三角形，本身就可以有环。

八、连通、连通分量、强连通

这是图基础里最容易混的一组。

1. 无向图：连通

若 $u$ 能通过某条路径走到 $v$ ，则称 $u, v$ 连通。

如果任意两个顶点都连通：

图是连通图。

2. 连通分量

对于非连通无向图：

A—B—C     D—E     F

这里有三个独立部分。

每一个“最大连通块”就是一个连通分量。

关键词：

极大连通子图。

“极大”的意思不是边最少，而是：

能加进去的属于这个连通块的顶点和边都已经加进来了。

九、有向图：强连通

有向图不能只要求单向可达。

若：

u →……→ v

同时还有：

v →……→ u

那么 $u, v$ 才是强连通。

若任意两个顶点相互可达：

强连通图。

一个非常高频结论

一个含 $n$ 个顶点的强连通有向图，最少需要：

n

条边。

最简单的方法就是构成一个有向环：

1 → 2 → 3 → ... → n
↑                 ↓
└─────────────────┘

这样每个顶点都能绕一圈到达其他顶点。

资料的配套选择题就直接考过：强连通有向图的邻接矩阵至少有多少个非零元素，答案就是 $n$ 。

十、生成树——后面 MST 的基础

对于一个连通无向图：

包含原图全部顶点，并保持连通，同时边数最少的子图，叫生成树。

如果有 $n$ 个顶点，那么任何生成树都有：

n - 1

条边。

生成树具有两个关键性质：

删除任何一条边

树断开。

添加任何一条额外边

产生环。

所以可以记：

树 = 连通 + 无环。

对于 $n$ 个顶点：

∣ E ∣ = n - 1

十一、完全图

无向完全图

任意两个顶点都有边。

最大边数：

∣ E ∣ = \frac{n ( n - 1 )}{2}

有向完全图

任意两个不同顶点之间都有两个方向相反的弧。

最大弧数：

∣ E ∣ = n (n - 1)

十二、6.2 图的存储——非常重要

图不像树一样天然有“左孩子右孩子”。

所以首先必须解决：

计算机里怎么把图存下来？

主要有四种：

邻接矩阵；
邻接表；
十字链表；
邻接多重表。

前两种最重要。

十三、邻接矩阵 ★★★★★

假设有 $n$ 个顶点，建立一个 $n \times n$ 的二维数组。

若 $i, j$ 相邻：

A [i] [j] = 1

否则：

A [i] [j] = 0

例如：

A —— B
|    /
|   /
C

邻接矩阵大致：

1. 无向图邻接矩阵

必然满足：

A [i] [j] = A [j] [i]

所以矩阵关于主对角线对称。

因此理论上只保存：

上三角；
或下三角

就够了。

十四、利用邻接矩阵计算度

这是高频。

无向图

第 $i$ 行非零元素个数：

顶点 $i$ 的度。

有向图

第 $i$ 行非零元素：

出度。

第 $i$ 列非零元素：

入度。

可以记：

行 = 从我出去。

列 = 别人进我。

例如：

A → B
A → C
D → A

A：

行里两个 1 → 出度 2；
列里一个 1 → 入度 1。

十五、带权图的邻接矩阵

不是存 0/1，而是存权值。

例如：

A --5-- B

则：

A [A] [B] = 5

如果两点不相连，一般存：

\infty

而不是简单存 0。

为什么？

因为边权本身有可能就是 0。

所以后面 Dijkstra、Floyd 中经常看到：

∞

表示不可直接到达。

十六、邻接矩阵最重要的优缺点

空间复杂度：

O (∣ V ∣^{2})

因此：

稠密图适合邻接矩阵。

优点：

判断 $u, v$ 是否存在边非常快；
直接访问：

O (1)

求有向图入度、出度方便。

缺点：

如果有 10000 个顶点但只有 10001 条边，大部分矩阵位置都是 0，非常浪费。

十七、邻接矩阵的一个特殊性质

若邻接矩阵为 $A$ ，那么：

A^{k} [i] [j]

表示：

从顶点 $i$ 到顶点 $j$ ，长度恰好为 $k$ 的路径数量。

这是一个经典结论。

注意这里说的是：

长度恰好为 $k$

而不是“不超过 $k$ ”。

十八、邻接表 ★★★★★

邻接表可以理解为：

每个顶点后面挂一条链表，记录它能连到谁。

例如：

A → B
A → C
B → D

邻接表：

A: B → C
B: D
C:
D:

有两部分：

顶点表

data | firstarc

边结点

adjvex | nextarc

十九、邻接表最关键特点

对于有向图：

默认邻接表通常保存的是“出边”。

因此：

求出度

直接数当前链表中有几个边结点。

求入度

很麻烦。

需要扫描所有顶点的邻接链表，看自己一共出现多少次。

复杂度可达到：

O (∣ V ∣ + ∣ E ∣)

这也是题库中经常考的地方。

二十、邻接表空间复杂度

有向图：

O (∣ V ∣ + ∣ E ∣)

无向图中每条边需要在两个顶点的链表各出现一次，因此：

O (∣ V ∣ + 2∣ E ∣)

渐进量级仍然是：

O (∣ V ∣ + ∣ E ∣)

所以：

稀疏图特别适合邻接表。

资料也明确比较了邻接矩阵与邻接表在稀疏图上的效率差异。

二十一、邻接矩阵 vs 邻接表

这是选择题必须非常熟。

邻接矩阵

适合：

稠密图。

优点：

判断两顶点是否直接相邻特别快。

邻接表

适合：

稀疏图。

优点：

枚举某个顶点所有邻接点特别快。

所以记：

找“有没有这条边” → 矩阵。

找“这个点都连着谁” → 邻接表。

二十二、十字链表——理解即可

这是专门为：

有向图

设计的。

普通邻接表求：

出度方便；
入度麻烦。

所以十字链表让一条弧同时进入两套链：

按弧尾组织；
按弧头组织。

顶点结点有：

data
firstin
firstout

弧结点大致有：

tailvex
headvex
tlink
hlink

所以既能方便寻找：

从我出去的边；

也能方便寻找：

指向我的边。

记忆：

十字链表 → 有向图 → 入边出边都方便。

二十三、邻接多重表

专门针对：

无向图。

普通邻接表中，一条无向边：

A—B

需要存两次：

A: B
B: A

邻接多重表：

一条边只建一个边结点，但让它同时挂到两个顶点的链表中。

因此删除边、修改边更加方便。

记忆：

十字链表 → 有向图。

邻接多重表 → 无向图。

资料对四种结构做了完整比较：邻接矩阵适合稠密图，邻接表适合稀疏图，十字链表只用于有向图，邻接多重表只用于无向图。

二十四、6.3 图的遍历——本章第一大核心

图遍历和树遍历最大的区别：

树里一般不会沿孩子指针绕回来。

图中可能：

A → B → C
↑       ↓
└───────┘

所以必须有：

visited[]

否则会：

A → B → C → A → B → C → ...

无限循环。

因此图遍历最核心的模式就是：

访问顶点
↓
visited = true
↓
寻找尚未访问的邻接顶点

二十五、BFS 广度优先搜索 ★★★★★

BFS 可以直接类比：

树的层序遍历。

核心思想：

先把离起点 1 条边的顶点访问完，再访问距离 2 条边的，再访问距离 3 条边的……

因此 BFS 必须用：

队列。

二十六、BFS 的完整过程

假设：

        A
      / | \
     B  C  D
    / \
   E   F

从 A 出发。

首先：

访问 A
A 入队

队列：

[A]

A 出队，发现 B、C、D：

访问 B,C,D
入队 B,C,D

队列：

[B,C,D]

B 出队：

访问 E,F

队列：

[C,D,E,F]

然后依次处理。

最终遍历：

A B C D E F

这就是“一层一层扩散”。

二十七、BFS 为什么一定要在入队时 visited=true？

经典易错点。

正确方式：

visited[w] = true;
EnQueue(Q, w);

而不要等到出队以后才标记。

因为如果：

A → C
B → C

C 已经从 A 被发现并入队，但如果没有立即标记，处理 B 时会再次发现 C，又入队一次。

所以：

发现顶点 → 立即标记 → 再入队。

二十八、BFS 时间复杂度

邻接表：

O (∣ V ∣ + ∣ E ∣)

邻接矩阵：

O (∣ V ∣^{2})

空间复杂度由队列决定：

O (∣ V ∣)

二十九、BFS 有一个非常重要的用途：无权图最短路径

为什么？

因为 BFS 是：

距离 0
↓
距离 1
↓
距离 2
↓
距离 3

依次发现。

因此一个顶点：

第一次被 BFS 访问时，就是从源点到该顶点经过边数最少的路径。

更新公式非常简单：

d [w] = d [u] + 1

所以：

无权图单源最短路径 → BFS。

题库同样特别强调：当所有边权相同时，BFS 可以求单源最短路径。

三十、BFS 生成树的特殊性质

BFS 按距离分层，因此：

BFS 生成树实际上是一棵“最短路径树”。

也正因为如此，从同一个起点出发：

BFS 生成树高度不会大于 DFS 生成树高度。

资料配套题就直接考过：

BFS 生成树高度 ≤ DFS 生成树高度。

三十一、DFS 深度优先搜索 ★★★★★

DFS 类似：

树的先序遍历。

思想非常直观：

能往下走就一直往下走，没路了才回头。

例如：

A
├─ B
│  ├─ D
│  └─ E
└─ C

DFS 可能：

所以：

A B D E C

三十二、DFS 为什么天然适合递归？

因为它的思想就是：

访问自己
↓
选择一个未访问邻居
↓
让邻居执行同样操作
↓
走不下去自动函数返回

核心模板：

void DFS(Graph G, int v) {
    visit(v);
    visited[v] = true;

    for (每个 v 的邻接点 w) {
        if (!visited[w])
            DFS(G, w);
    }
}

这一段是本章非常值得记住的算法模板。

三十三、DFS 的本质：递归栈

虽然代码没有显式写：

stack

但递归调用本身就使用：

系统调用栈。

因此 DFS 也可以改写成显式栈版本。

所以记忆：

BFS → 队列。

DFS → 栈/递归。

三十四、DFS 时间复杂度

和 BFS 完全相同。

邻接矩阵：

O (∣ V ∣^{2})

邻接表：

O (∣ V ∣ + ∣ E ∣)

空间复杂度最坏：

O (∣ V ∣)

原因是递归深度可能达到全部顶点。

三十五、DFS/BFS 序列为什么有时不唯一？

非常容易考。

邻接矩阵

如果：

顶点编号固定；
始终按编号顺序扫描；

那么邻接矩阵本身唯一，所以遍历序列通常唯一。

邻接表

例如 A 有：

B,C,D

邻接表可以：

A: B → C → D

也可以：

A: D → B → C

因此 DFS/BFS 的访问顺序可能不同。

资料的模拟题也直接考查过“根据邻接表顺序确定 DFS 序列”。

三十六、用 BFS/DFS 判断连通分量

对于无向图：

从一个未访问顶点运行一次 DFS/BFS：

恰好遍历它所在的整个连通分量。

因此：

调用 DFS/BFS 的次数
=
连通分量数量

例如：

A—B—C    D—E    F

需要启动 3 次。

所以连通分量数：

3

三十七、6.4 图的应用——本章真正的大头

资料明确指出，这一节是历年考查重点，通常并不是让你从零写完整算法，而是给出一个图，让你模拟算法的执行过程。

最重要四组：

MST：Prim / Kruskal

最短路径：Dijkstra / Floyd

依赖关系：拓扑排序

工程进度：关键路径

三十八、最小生成树 MST ★★★★★

首先把目标搞清楚：

给一个：

带权、连通、无向图。

要求：

把所有顶点连通，同时总边权最小。

最终一定有：

∣ V ∣ - 1

条边。

三十九、最小生成树 ≠ 最短路径树

这是极高频坑。

MST 优化的是：

整棵树所有边的总权值。

最短路径优化的是：

某两个顶点之间的路径长度。

完全不是一个目标。

因此：

MST 中 A 到 B 的路径，不一定是原图中 A 到 B 的最短路径。

资料专门强调了这一点。

四十、MST 是否唯一？

如果所有边权：

互不相同，

则 MST 唯一。

如果存在相同权值：

MST 可能不唯一。

但不管有多少棵 MST：

它们的总权值一定一样。

四十一、Prim 算法 ★★★★★

Prim 是：

以“顶点集合”为核心不断向外扩张。

可以想象成：

已经占领了一块区域，每次找一条最便宜的边，把区域外一个新顶点拉进来。

设当前 MST 已包含顶点集合 $U$ 。

每次选择：

一端在 $U$ ，另一端在 $V - U$ 中的最小权边。

然后把新顶点加入 $U$ 。

四十二、Prim 手算方法

假设：

A--2--B
|    / |
3   1  5
|  /   |
C--4--D

从 A 开始。

初始：

U={A}

跨越：

{A} 和 {B,C,D}

的边：

A-B=2
A-C=3

选择：

A-B=2

现在：

U={A,B}

重新检查跨集合边：

A-C=3
B-C=1
B-D=5

选择：

B-C=1

现在：

U={A,B,C}

继续：

C-D=4
B-D=5

选：

C-D=4

得到 MST。

核心不是：

找全图最小边。

而是：

找连接当前树和树外顶点的最小边。

四十三、Prim 为什么适合稠密图？

经典实现复杂度：

O (∣ V ∣^{2})

主要和顶点数有关。

所以边特别多时，它并不会因为边数特别多而明显变差。

因此：

Prim → 稠密图。

四十四、Kruskal 算法 ★★★★★

Kruskal 恰好反过来。

它不关心“当前树从哪里长出来”。

它只考虑：

边。

核心：

所有边按权值从小到大排序；
从最小边开始；
如果加入不会形成环，就加入；
如果会形成环，就跳过；
最终加入 $n - 1$ 条边。

四十五、Kruskal 手算过程

例如边排序后：

AB 1
BC 2
AC 3
CD 4
BD 5

先选：

AB

再选：

BC

现在：

A-B-C

轮到：

AC

如果加入：

A-B-C-A

形成环。

所以：

跳过 AC

再选：

CD

完成。

四十六、Kruskal 为什么离不开并查集？

关键判断：

一条边的两个端点加入后会不会成环？

本质上就是问：

这两个顶点目前是不是已经在同一个连通分量？

可以用并查集：

Find(u) == Find(v)

说明已经连通：

加边会形成环。

否则：

Union(u,v)

这就是第五章并查集为什么会和第六章 Kruskal 连起来。

题库中也直接考查：Kruskal 常用最小堆高效取得最小边，同时用并查集判断两个端点是否属于同一连通分量。

四十七、Kruskal 复杂度

主要成本是边排序或不断取最小边：

O (∣ E ∣ lo g ∣ E ∣)

所以：

Kruskal → 稀疏图。

四十八、Prim 和 Kruskal 一定要这样区分

Prim	Kruskal
按顶点扩张	按边选择
始终维护一棵树	开始是森林
每次拉入一个新顶点	每次合并两个连通分量
不允许把树内两个点再连起来	不允许形成环
适合稠密图	适合稀疏图
`O(V^2)`	`O(E log E)`

一个记忆方法：

Prim：长树。

Kruskal：并森林。

四十九、最短路径 ★★★★★

有三个算法一定先分清适用范围：

BFS

无权图单源最短路径。

Dijkstra

非负权图单源最短路径。

Floyd

所有顶点对最短路径，可以有负边，但不能有负权环。

资料也给出了这三个算法的集中对比。

五十、Dijkstra ★★★★★

目标：

从一个源点 $s$ 出发，求到所有其他顶点的最短距离。

核心思想：

每次找到“当前离源点最近、且还没有最终确定”的顶点。

然后确定它。

五十一、Dijkstra 的三个核心数组

final

final[i]

表示：

i 的最短路径是否已经最终确定。

dist

dist[i]

表示：

当前已知的从源点到 i 的最短距离。

注意：

是“目前已知”，不是一开始就最终正确。

path

用于记录：

最短路径的前驱。

最后可以倒推完整路径。

五十二、Dijkstra 最重要的操作：松弛

假设：

源点 S → u

当前：

d i s t [u] = 5

并且：

u → v

权值 3。

那么经过 u 到 v：

5 + 3 = 8

如果原来：

d i s t [v] = 10

发现 8 更小，于是：

d i s t [v] = 8

这个过程叫：

Relaxation，松弛。

后面很多图算法都会用到这个思想。

五十三、Dijkstra完整循环

每轮做两件事：

第一步：选

在所有未确定顶点中找：

dist 最小的顶点 $u$ 。

把它标记：

final[u]=true

第二步：松弛

检查所有：

u → v

若：

d i s t [u] + w (u, v) < d i s t [v]

则更新：

d i s t [v] = d i s t [u] + w (u, v)

然后继续下一轮。

题库也直接考过：

Dijkstra 是按照最短路径长度的递增次序依次确定各顶点。

五十四、为什么 Dijkstra 不能有负权边？

这是超级重要。

Dijkstra 有一个核心假设：

我一旦选出了当前 dist 最小的顶点，它的距离以后就不可能再变小。

非负边权时成立。

但有负边就不一定。

例如：

S → A = 2
S → B = 5
B → A = -10

Dijkstra 一开始觉得：

A=2

于是先确定 A。

但实际上：

S → B → A

长度：

5 - 10 = - 5

比 2 小。

所以之前确定 A 是错误的。

因此：

Dijkstra 不能处理负权边。

五十五、Dijkstra 与 Prim 最容易混

二者看起来都在：

每轮选一个最小值
↓
加入集合
↓
更新其他值

但最小值含义完全不同。

Prim

记录：

树外顶点到“当前整个树”的最小连接边。

Dijkstra

记录：

源点到该顶点的当前最短路径长度。

Prim 比较：

边权

Dijkstra 比较：

整条路径长度

这是最重要的区别。

五十六、Floyd 算法 ★★★★★

Floyd 的目标不是单源，而是：

求任意两顶点之间的最短距离。

它的思想其实比 Dijkstra 更统一：

看能不能通过某个中间顶点 $k$ ，让 $i \to j$ 更短。

五十七、Floyd 的核心公式

原来从 $i$ 到 $j$ ：

A [i] [j]

现在尝试走：

i → k → j

距离：

A [i] [k] + A [k] [j]

于是：

A [i] [j] = min (A [i] [j], A [i] [k] + A [k] [j])

这一个式子就是 Floyd 的全部灵魂。

五十八、Floyd 为什么有三层循环？

因为：

第一层

枚举中间顶点：

第二、三层

枚举起点终点：

i,j

因此整体：

for (k)
    for (i)
        for (j)
            dist[i][j] =
                min(dist[i][j],
                    dist[i][k] + dist[k][j]);

时间复杂度：

O (∣ V ∣^{3})

五十九、Floyd 如何理解“第 k 轮”？

这是很多人真正没理解的地方。

假设顶点：

0 1 2 3

第 0 轮：

允许经过顶点 0。

第 1 轮：

允许经过顶点 0、1。

第 2 轮：

允许经过顶点 0、1、2。

……

所以 Floyd 不是随机更新。

它其实是动态规划：

不断扩大“允许作为中间点的顶点集合”。

六十、Floyd 为什么能处理负权边？

因为 Floyd 不会像 Dijkstra 那样：

一旦确定某个顶点就永远不改。

它会持续：

尝试更多中间顶点
↓
重新更新距离

所以负权边没有问题。

但是：

不能存在负权环。

因为如果有：

A → B → C → A

整个环权值为负，那么绕一圈更短，再绕一圈还更短：

d, d - 5, d - 10, d - 15, \dots

不存在有限的“最短”路径。

六十一、三个最短路径算法一眼判断

看到题目先问：

无权图？

BFS。

单源 + 权值非负？

Dijkstra。

任意两点？

Floyd。

有负权边？

Dijkstra 排除。

有负权环？

正常意义上不存在有限最短路径。

六十二、DAG 表示表达式

DAG：

有向无环图。

这一小节不是最高频，理解思想即可。

假设表达式有重复子表达式：

(a+b)*(a+b)

如果用普通表达式树：

     *
   /   \
  +     +
 / \   / \
a   b a   b

a+b 存了两份。

DAG 可以：

    +
   / \
  a   b
   \ /
    *

概念上就是：

让多个父结点共享同一个公共子表达式。

资料中的统考追踪包括 2019 年构建表达式 DAG。

六十三、拓扑排序 ★★★★★

首先明确：

拓扑排序只针对有向无环图 DAG。

它解决的问题是：

有一堆存在先后依赖关系的任务，怎样排出一个合法执行顺序？

例如：

高数基础 → 微积分
微积分 → 微分方程

那么排序必须满足：

高数基础
↓
微积分
↓
微分方程

六十四、AOV 网

AOV：

Activity On Vertex。

也就是：

顶点代表活动。

有向边：

A → B

表示：

A 必须先完成，B 才能进行。

六十五、拓扑排序最经典算法

核心就一句：

反复删除入度为 0 的顶点。

过程：

找所有入度为 0 的顶点；
任取一个输出；
删除这个顶点；
删除其所有出边；
相邻顶点入度减 1；
若某顶点入度变成 0，加入栈/队列；
重复。

六十六、为什么一定选入度为 0？

因为：

入度为 0 = 没有任何前驱依赖。

所以它可以立即执行。

而：

A → B

B 入度不为 0，说明 A 还没完成。

自然不能先输出 B。

六十七、拓扑排序如何判断环？

如果最终：

已经输出顶点数 < 总顶点数

而又没有入度为 0 的顶点：

存在环。

例如：

A → B
↑   ↓
└── C

三个顶点入度都不为 0。

谁都不能第一个执行。

因此不可能有合法拓扑序。

所以：

有拓扑序列 ⇔ DAG。

六十八、拓扑序列通常不唯一

例如：

A → C
B → C

开始时：

A、B

入度都为 0。

所以可以：

A B C

也可以：

B A C

因此：

DAG 不一定只有一个拓扑序列。

题库也反复考这一点：某个顶点在另一个顶点之前，并不意味着二者之间一定有直接边；但如果存在从后者到前者的路径，则这个顺序一定不合法。

六十九、拓扑排序时间复杂度

邻接表：

O (∣ V ∣ + ∣ E ∣)

邻接矩阵：

O (∣ V ∣^{2})

七十、DFS 也能做拓扑排序

这个稍微理解一下。

DFS 中：

先深入子孙
↓
子孙先结束
↓
祖先后结束

所以按照：

DFS 完成时间的逆序

排列顶点，可以得到拓扑序。

等价理解：

一个顶点一定要等它所有后继处理完以后，再压入结果栈。

最后弹栈就是拓扑序。

七十一、关键路径 ★★★★★

这是本章计算量最大、最容易混的一部分。

先区分：

AOV

顶点 = 活动
边 = 先后关系

用于：

拓扑排序。

AOE

顶点 = 事件
边 = 活动
边权 = 活动耗时

用于：

关键路径。

这个区别必须彻底记住。

七十二、什么叫关键路径？

工程中可能有多条从：

源点 → 汇点

的路径。

假设三条分别需要：

8 天
10 天
15 天

整个工程最快多久能完成？

显然：

15 天

因为所有活动都必须完成。

因此：

最长路径 = 关键路径。

注意：

MST

找最小。

最短路径

找最小。

关键路径

反而找：

最长。

因为最长的那条工程链决定总工期。

七十三、关键路径最核心的四组量

很多同学就是在这里混乱。

必须把：

事件
活动

分开。

1. 事件最早发生时间 ve

记住：

这个事件最早什么时候能发生？

对于顶点 $k$ ：

v e (k) = max {v e (j) + w (j, k)}

为什么是 Max？

因为如果事件 k 有三个前驱活动：

A ─5─→ k
B ─8─→ k
C ─3─→ k

事件 k 必须等：

所有前驱活动完成。

所以要等最慢那个。

因此：

ve 正向算，取 Max。

七十四、事件最迟发生时间 vl

含义：

在不延误整个工程的前提下，这个事件最晚什么时候必须发生？

公式：

v l (k) = min {v l (j) - w (k, j)}

为什么取 Min？

因为一个事件可能有多个后继。

必须保证：

每个后继都不会被拖延。

所以必须满足最严格的那个截止要求。

因此：

vl 逆向算，取 Min。

七十五、活动的最早开始时间 e

若活动对应边：

k → j

那么：

活动最早什么时候能开始？

当然就是：

起点事件 k 最早发生的时候。

所以：

e (i) = v e (k)

七十六、活动的最迟开始时间 l

活动从：

k → j

持续时间为 $w$ 。

为了保证终点事件 j 不晚于：

v l (j)

发生，那么最晚必须：

w

时间之前开始。

因此：

l (i) = v l (j) - w (k, j)

七十七、时间余量 d

活动能够拖延多久而不影响工程：

d (i) = l (i) - e (i)

如果：

d (i) = 0

说明：

一分钟都不能耽误。

那么这个活动就是：

关键活动。

所以判断关键活动的核心：

e (i) = l (i)

七十八、一套非常重要的关键路径口诀

你只需要牢牢记住：

ve：正向，Max，加。

vl：反向，Min，减。

e：看起点 ve。

l：终点 vl 减边权。

l-e=0：关键活动。

这基本解决 90% 的关键路径计算题。

七十九、用一个小例子完整走一遍

假设：

v1 --3--> v2 --4--> v4
 \                    ↑
  \--2--> v3 --6------/

两条路径：

v1 → v2 → v4

长度：

3 + 4 = 7

另一条：

v1 → v3 → v4

长度：

2 + 6 = 8

因此：

关键路径是 v1-v3-v4。

工程工期：

8

第一步：算 ve

源点：

v e (v_{1}) = 0

于是：

v e (v_{2}) = 3

v e (v_{3}) = 2

对于 v4：

v e (v_{4}) = max {3 + 4, 2 + 6}

v e (v_{4}) = 8

第二步：算 vl

汇点：

v l (v_{4}) = 8

然后：

v l (v_{2}) = 8 - 4 = 4

v l (v_{3}) = 8 - 6 = 2

源点：

v l (v_{1}) = min {4 - 3, 2 - 2}

v l (v_{1}) = 0

第三步：检查活动

活动：

v1→v2

最早：

e = v e (v_{1}) = 0

最迟：

l = v l (v_{2}) - 3 = 1

所以余量：

d = 1

不是关键活动。

活动：

v1→v3

e = 0

l = 2 - 2 = 0

因此：

d = 0

关键活动。

活动：

v3→v4

e = 2

l = 8 - 6 = 2

因此：

d = 0

关键活动。

最终：

v1 → v3 → v4

为关键路径。

资料配套题也是采用完全相同的方法：先拓扑顺序计算 ve，再逆拓扑计算 vl，最后使用活动余量判断关键活动。

八十、关键路径最危险的陷阱

陷阱 1：缩短一个关键活动，工期一定缩短？

不一定。

因为可能存在：

多条关键路径。

例如：

路径1 = 10
路径2 = 10

你把路径 1 缩短到：

但路径 2 仍然：

所以总工期还是 10。

陷阱 2：关键路径永远不会变？

错误。

假设：

路径 A = 10
路径 B = 9

A 是关键路径。

把 A 缩短到：

这时：

B = 9

反而成为新的关键路径。

因此：

关键路径可能转移。

资料特别强调：当存在多条关键路径时，只有缩短所有关键路径共有的关键活动，才一定有机会缩短工程工期。

八十一、全章复杂度必须记住

资料最后给出的汇总非常重要。

邻接矩阵

DFS：

O (∣ V ∣^{2})

BFS：

O (∣ V ∣^{2})

Prim：

O (∣ V ∣^{2})

Dijkstra：

O (∣ V ∣^{2})

Floyd：

O (∣ V ∣^{3})

拓扑排序：

O (∣ V ∣^{2})

关键路径：

O (∣ V ∣^{2})

邻接表

DFS：

O (∣ V ∣ + ∣ E ∣)

BFS：

O (∣ V ∣ + ∣ E ∣)

拓扑排序：

O (∣ V ∣ + ∣ E ∣)

关键路径：

O (∣ V ∣ + ∣ E ∣)

Kruskal：

O (∣ E ∣ lo g ∣ E ∣)

八十二、最后把整章算法放到一张“选择器”里

遇到题目，第一反应不要背代码，先问“它到底要解决什么问题”。

问题	算法
遍历全部顶点，分层搜索	BFS
遍历全部顶点，一路深入	DFS
无权图单源最短路径	BFS
带权连通无向图，总连接成本最低	Prim / Kruskal
非负权图单源最短路径	Dijkstra
任意两顶点间最短路径	Floyd
活动先后依赖排序	拓扑排序
检查 DAG 是否有环	拓扑排序
工程最短完成时间	关键路径
求活动最大可拖延时间	关键路径

八十三、几个最容易混淆的本质区别

BFS vs DFS

BFS：一层层扩散 → 队列
DFS：一条路走到底 → 栈/递归

Prim vs Dijkstra

Prim：
当前树到树外顶点
哪条连接边最小？

Dijkstra：
源点到未确定顶点
哪条完整路径最短？

Prim vs Kruskal

Prim：围绕顶点集合扩张
Kruskal：从最小边开始合并森林

MST vs 最短路径

MST：
所有选中边总和最小

最短路径：
特定顶点之间距离最小

拓扑排序 vs 关键路径

拓扑排序：
只管先后关系
AOV：顶点是活动

关键路径：
还要考虑活动持续时间
AOE：边是活动

八十四、408 考场做图题的推荐流程

这一章真正应该练的不是死背代码，而是“手工跑算法”。

看到图以后，建议固定执行：

第一步：先看图的类型。

有向 / 无向
带权 / 无权
连通 / 非连通
DAG / 有环

第二步：确认目标。

遍历？
最小总成本？
单源最短路径？
所有点对最短路径？
先后关系？
工程工期？

第三步：立刻锁定算法。

例如：

带权无向 + 连接所有点 + 权值总和最小
→ MST
→ Prim/Kruskal

而不是看到“最小”两个字就想到 Dijkstra。

第四步：画辅助状态。

Prim：

U 集合
候选跨边

Kruskal：

边权排序
连通分量

Dijkstra：

S
dist[]
path[]

Floyd：

距离矩阵

拓扑排序：

indegree[]

关键路径：

ve[]
vl[]
e[]
l[]

这样基本不会乱。

最后给你一个第 6 章的核心知识树

图
│
├─ 基本概念
│  ├─ 有向 / 无向
│  ├─ 度 / 入度 / 出度
│  ├─ 路径 / 回路
│  ├─ 连通 / 强连通
│  └─ 生成树
│
├─ 存储
│  ├─ 邻接矩阵 → 稠密图
│  ├─ 邻接表 → 稀疏图
│  ├─ 十字链表 → 有向图
│  └─ 邻接多重表 → 无向图
│
├─ 遍历
│  ├─ BFS → 队列 → 分层 → 无权最短路径
│  └─ DFS → 栈/递归 → 深入回溯
│
└─ 应用
   ├─ MST
   │  ├─ Prim → 长一棵树
   │  └─ Kruskal → 合并森林
   │
   ├─ 最短路径
   │  ├─ BFS → 无权单源
   │  ├─ Dijkstra → 非负权单源
   │  └─ Floyd → 所有点对
   │
   ├─ DAG
   │  └─ 拓扑排序 → 删除入度 0 顶点
   │
   └─ AOE
      └─ 关键路径
         ├─ ve：正向 Max
         ├─ vl：反向 Min
         ├─ e：起点 ve
         ├─ l：终点 vl - 边权
         └─ l-e=0 → 关键活动

如果只从应试收益来看，接下来最值得单独强化的是 4 类“手算题”——Prim/Kruskal、Dijkstra/Floyd、拓扑排序、关键路径。这四类一旦能不看答案完整跑出每一轮状态，第 6 章的大部分中高难度选择题就基本打通了。

第 6 章 图

On this page