第6章图（自学增强版）¶

章节定位：图论主干章

这一章把“结构表示 + 遍历 + 应用算法”真正整合到同一个模型里。
建议按概念、存储、遍历、最短路、最小生成树、拓扑排序、关键路径的顺序推进，并结合代码专题一起看。

1. 本章定位¶

这一章是整本书里最容易让学生突然感觉“抽象度上来了”的一章。如果说前面的线性表、栈、队列、树，主要还是在讨论“一个结构内部怎么组织”；那么图开始讨论的是：

多个顶点之间可以如何任意建立关系
这些关系是否有方向、是否带权、是否连通
遍历、最短路、最小生成树、拓扑排序这些经典问题如何统一落到同一个模型里

所以第6章真正难的地方，不只是算法多，而是：

术语多
表示法多
同一个问题在不同存储结构下写法不同
遍历和应用算法之间联系很紧

这一章一旦吃透，后面的查找、排序虽然仍然重要，但在“结构抽象能力”上不会再有这么大的跨越。

2. 学习目标¶

学完本章后，你应当能够做到：

说清图、顶点、边、弧、度、入度、出度、路径、回路、连通、强连通、生成树这些基本概念
分清无向图、有向图、完全图、稀疏图、稠密图、带权图之间的区别
理解邻接矩阵、邻接表、十字链表、邻接多重表各自适合什么场景
看懂并写出 DFS 和 BFS 的真实 C 代码
把图遍历迁移到连通分量、拓扑排序、最小生成树、最短路径等问题
知道图算法里哪些题更偏“思想理解”，哪些题更适合直接代码化

3. 前置知识¶

正式进入本章前，最好先确保这几块比较稳：

第2章的顺序存储、链式存储
第3章的栈和队列
第5章的递归思维、遍历模板、连通 / 非连通判断直觉

因为图这一章里：

邻接矩阵本质上还是顺序存储
邻接表本质上还是数组 + 链表
BFS 本质上离不开队列
DFS 本质上离不开递归或栈

4. 本章结构总览¶

第6章建议按下面这条主线理解：

先搞清图到底是什么，它和树、线性结构的区别是什么
再看图怎么存，尤其是邻接矩阵和邻接表
再把 DFS、BFS 彻底打透，因为后面很多应用都是从遍历长出来的
最后再进入图的应用：最小生成树、最短路径、拓扑排序、关键路径

如果把这一章压成一句话，那就是：

先学怎么表示关系，再学怎么沿着关系走，最后学怎么在关系网络上做最优决策。

5. 6.1 图的基本概念¶

5.1 为什么图比前面的结构更自由¶

线性表强调“一个挨一个”，树强调“从一个点往下分叉”，图更进一步：

任意两个顶点之间都可能有关系
这个关系可能有方向，也可能没方向
这个关系还可能带权值

所以图是整本书里最通用、表达能力最强的一类结构。

5.2 本节先要抓住的核心术语¶

这一节最基础、但也最容易混的术语包括：

顶点、边、弧
无向图、有向图
简单图、多重图
顶点的度、入度、出度
路径、路径长度、回路
连通图、强连通图、连通分量、强连通分量
生成树、生成森林
完全图、稀疏图、稠密图、带权图

这里有一个学习建议：

不要一上来背定义
先理解“这些术语到底是在描述图的哪一面”

例如：

度 / 入度 / 出度在描述“一个顶点和周围边的关系”
路径 / 回路在描述“沿边能不能走、怎么走”
连通 / 强连通在描述“任意两点之间是否能到达”

5.3 本节学习重点¶

学习第 6 章时，建议先优先掌握下面这些内容：

图的定义与和前面结构的对比
无向图与有向图
度、入度、出度
路径、回路、简单路径、简单回路
连通图、强连通图、生成树
原书高频选择题和易错点整理

5.4 图的定义：先抓“顶点集 + 边集”¶

图通常记作：

G = (V, E)

这里：

V 表示顶点集合
E 表示边集合或弧集合

这一点看起来简单，但很重要，因为它提醒我们：

图不是“只有边”
图也不是“只有点”
图的本质是“点和点之间关系的整体”

和前面结构对比一下会更容易理解：

线性表重点是“元素的先后顺序”
树重点是“父子层次关系”
图重点是“任意顶点之间都可能建立关系”

所以图是这本书里表达能力最强的一类结构。

5.5 无向图和有向图：先分清“边有没有方向”¶

这是整章最基础的分界线。

无向图¶

如果边没有方向，那么顶点 v 和 w 之间的边可以记成：

(v, w)

它表示：

v 能到 w
w 也能到 v
两者关系是对称的

有向图¶

如果边有方向，那么通常记成：

<v, w>

它表示：

边是从 v 指向 w
v 是弧尾
w 是弧头

这时就不能默认反过来也成立。

一句话抓核心：

无向图看“有没有边”
有向图看“边朝哪边指”

5.6 简单图、多重图、完全图¶

这些概念在选择题里很高频。

简单图¶

如果一个图满足：

不存在重复边
不存在顶点到自身的边

那么它就是简单图。

这也是本章默认重点讨论的对象。

多重图¶

如果：

同一对顶点之间允许出现多条边
还允许顶点和自身相连

那么就是多重图。

学生常见误区是：

以为所有图默认都能出现重边和自环

不是的。
教材里大多数基础结论、基础存储结构和基础算法，默认讨论的都是简单图。

完全图¶

完全图强调的是：

任意两个不同顶点之间都存在边

无向图里，若有 n 个顶点，则完全图边数为：

n(n - 1) / 2

有向完全图里，弧数为：

n(n - 1)

这一组公式非常容易考。

5.7 顶点的度、入度、出度¶

这一组概念是“顶点和边的关系”的核心。

无向图中的度¶

在无向图中，顶点的度就是：

和该顶点相关联的边的条数

最关键的一个结论是：

无向图所有顶点的度之和 = 2e

这里 e 表示边数。

为什么一定乘 2？

因为每一条无向边都同时连接两个顶点，所以会被数两次。

有向图中的入度和出度¶

在有向图中：

入度：以该顶点为终点的弧数
出度：以该顶点为起点的弧数

顶点总度满足：

总度 = 入度 + 出度

而整张有向图还有一个非常重要的结论：

所有顶点入度之和 = 所有顶点出度之和 = 弧数

这一点一定要和无向图的 2e 区分开。

5.8 路径、路径长度、回路、简单路径、简单回路¶

这一组概念看起来像定义题，但其实后面最短路、拓扑排序、关键路径都离不开它。

路径¶

从一个顶点出发，顺着边走到另一个顶点，经过的顶点序列就是路径。

路径长度¶

路径长度指的是：

路径上边的条数

注意：

不是顶点数
是边数

回路¶

如果一条路径的起点和终点相同，那么它就是回路，也叫环。

简单路径¶

如果路径中顶点不重复出现，那么就是简单路径。

简单回路¶

除起点和终点相同外，其余顶点都不重复，那么就是简单回路。

这里很容易混：

回路不一定是简单回路
简单路径不能随便顶点重复
简单回路允许“首尾相同”，但中间不能乱重复

5.9 连通、强连通、连通分量、强连通分量¶

这一组概念是第6章最容易“概念上似懂非懂”的地方。

无向图中的连通¶

如果从顶点 v 到顶点 w 有路径，那么称 v 和 w 连通。

如果无向图中任意两个顶点都连通，那么它就是连通图。

连通分量¶

无向图中的极大连通子图，叫连通分量。

这里“极大”不是“边最多”，而是：

在保持连通的前提下，已经不能再往里加顶点了

有向图中的强连通¶

在有向图中，如果：

v 能到 w
w 也能到 v

那么才叫强连通。

所以：

无向图讨论“连通”
有向图讨论“强连通”

强连通分量¶

有向图中的极大强连通子图，叫强连通分量。

一句话帮助记忆：

连通强调“能过去”
强连通强调“来回都能过去”

5.10 生成树、生成森林、带权图、稀疏图¶

这些概念会直接通向后面的应用算法。

生成树¶

对一个连通无向图来说，如果一个子图：

包含原图全部顶点
保持连通
边数最少

那么它就是生成树。

生成树最核心的一个结论：

n 个顶点的生成树一定有 n - 1 条边

生成森林¶

如果原图本身非连通，那么每个连通分量各自取一棵生成树，合起来就是生成森林。

带权图¶

如果边上带有权值，那么这张图就是带权图，也叫网。

权值可以表示：

距离
时间
费用
代价

所以后面的最短路径、最小生成树，本质上都在“带权关系网络”上做最优问题。

稀疏图和稠密图¶

这是相对概念：

边很少，叫稀疏图
边很多，叫稠密图

为什么这个概念重要？

因为它会影响：

存储结构怎么选
算法复杂度怎么看

一般来说：

稠密图更适合邻接矩阵
稀疏图更适合邻接表

5.11 6.1 高频选择题怎么抓¶

图的概念题很多时候不是考你“会不会背一句定义”，而是考你能不能抓住判断依据。

类型 1：边数和顶点数关系题¶

这类题经常围绕：

连通图至少多少边
完全图有多少边
无向图度数和是多少
有向图入度和 / 出度和是多少

这类题要优先记的不是题，而是公式。

类型 2：连通与非连通判断题¶

这类题常问：

边数少到什么程度一定非连通
边数多到什么程度一定有环
强连通图最少要多少条边

这类题不能硬背结论，最好自己会画极端图形去想。

类型 3：概念辨析题¶

最容易混的有：

路径 vs 简单路径
回路 vs 简单回路
连通 vs 强连通
生成树 vs 极大连通子图
简单图 vs 多重图

这类题最稳的方法是：

看它是不是要求“重复”
看它讨论的是无向图还是有向图
看它强调的是“极大”还是“极小”

5.12 6.1 高频易错点¶

错点 1：把图也当成可以是空结构¶

线性表可以为空表，树可以为空树，但教材这里通常默认图的顶点集非空。
也就是：

图不能一个顶点都没有
但可以有顶点而没有边

错点 2：把“路径长度”看成顶点数¶

路径长度数的是边，不是点。
这在最短路题里非常重要。

错点 3：把“连通”拿去描述有向图¶

更准确地说：

无向图谈连通
有向图谈强连通

虽然有时口头上也会说“有向图连通”，但做题时一定按严格术语来。

错点 4：把生成树理解成“边最多的树”¶

生成树不是“边最多”，而是：

包含全部顶点
还保持连通
并且边数已经压到最少

错点 5：把“极大连通子图”和“极小连通子图”混掉¶

这组概念必须分清：

极大连通子图：连通分量
极小连通子图：生成树

一个强调“不能再加顶点” 一个强调“不能再减边”

6. 6.2 图的存储及基本操作¶

这一节是第6章代码落地的真正入口。

后面我们会重点做两种表示：

邻接矩阵
邻接表

为什么优先这两种：

它们是最核心、最常考的两种存储结构
DFS / BFS 用这两种结构最容易讲透
后面的拓扑排序、最短路径、最小生成树也都能顺着这两种结构接下去

这一节后面会重点补：

存储结构定义
原书伪代码与真实代码对照
基本操作
时间 / 空间复杂度比较
适用场景比较

6.1 为什么图的存储比前面更重要¶

在线性表里，顺序表和链表虽然不同，但“逻辑关系”很直观；图不一样。

图里有一个非常关键的特点：

逻辑关系是“谁和谁相连”
代码实现是“这种相连关系到底放在哪种结构里”

所以图这一章经常会出现一种情况：

同一个 DFS，换个存储结构，代码写法就明显不一样

这就是为什么第6章不能跳过存储结构直接讲遍历。

6.2 图的存储结构先抓哪两种¶

虽然教材里会讲：

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

但从“先学会、再做题、再写代码”的顺序来说，最应该先抓住的是：

邻接矩阵
邻接表

原因是：

这两种最基础、最常考
DFS / BFS 最容易用这两种结构讲透
其他结构本质上都可以理解为在这两种基础上的进一步优化

6.3 邻接矩阵：把“是否有边”直接摆成一个二维表¶

邻接矩阵的核心想法非常直接：

图有多少个顶点，就开一个 n × n 的二维数组
第 i 行第 j 列表示顶点 vi 到 vj 是否有边

如果是无权图，通常可以记成：

有边 = 1
无边 = 0

如果是带权图，则通常记成：

有边 = 权值
无边 = INF 或某个约定值

一句话抓本质：

邻接矩阵就是把“点和点之间有没有边”做成一张关系表。

邻接矩阵最适合什么场景¶

它特别适合：

稠密图
经常要判断两个顶点之间是否直接有边
题目里更强调“关系查询”而不是“边很少”

因为它的最大优点是：

判断 vi 和 vj 是否邻接：O(1)

邻接矩阵最大的代价是什么¶

空间固定要开到：

O(n^2)

所以如果边很少，很多位置都是空的，就会显得浪费。

6.4 邻接矩阵：原书思路版伪代码¶

教材里这一部分最核心的动作通常是：

初始化图
定位顶点
加边

可以先抽成下面这种思路：

InitMGraph(G, 顶点序列):
    G.vexnum = 顶点个数
    G.arcnum = 0
    for i = 0..n-1:
        G.vexs[i] = 顶点名
    for i = 0..n-1:
        for j = 0..n-1:
            if i == j:
                G.edges[i][j] = 0
            else:
                G.edges[i][j] = INF

AddEdge(G, vi, vj, w):
    找到 vi 和 vj 的下标 i, j
    G.edges[i][j] = w
    若为无向图:
        G.edges[j][i] = w

这段伪代码真正要学生看懂的不是语法，而是：

为什么先把整张表都填成“无边”
为什么无向图要补对称位置
为什么顶点名和数组下标之间必须建立映射

6.5 邻接矩阵：对应真实代码¶

第6章代码首稿里，这部分已经落成真实 C 代码，对应位置是：

第6章普通代码版（约第91行） InitAMGraph
第6章普通代码版（约第122行） LocateVertexAM
第6章普通代码版（约第142行） AddEdgeAM
第6章普通代码版（约第166行） PrintAMGraph

最核心的真实代码片段如下：

void InitAMGraph(AMGraph *graph, const char *vertex_names, bool directed) {
    int i;
    int j;
    int length;

    if (graph == NULL || vertex_names == NULL) {
        return;
    }

    length = (int)strlen(vertex_names);
    if (length <= 0 || length > MAX_VERTEX_NUM) {
        return;
    }

    graph->vexnum = length;
    graph->arcnum = 0;
    graph->directed = directed;

    for (i = 0; i < graph->vexnum; i++) {
        graph->vexs[i] = vertex_names[i];
    }

    for (i = 0; i < graph->vexnum; i++) {
        for (j = 0; j < graph->vexnum; j++) {
            if (i == j) {
                graph->edges[i][j] = 0;
            } else {
                graph->edges[i][j] = INF;
            }
        }
    }
}

这段代码和伪代码几乎是一一对应的，所以它很适合学生第一次把“图的抽象定义”落实到真正的程序结构里。

6.6 邻接表：把“一个顶点连出去的边”挂成链¶

如果说邻接矩阵是在问：

任意两点之间有没有边？

那么邻接表更像是在问：

从这个顶点出发，能直接走到哪些顶点？

邻接表的核心思想是：

先有一个顶点表
每个顶点后面挂一条边链表
这条链表里存这个顶点能直接到达的所有邻接点

一句话抓本质：

邻接表就是按“顶点出发”来组织边。

邻接表最适合什么场景¶

它特别适合：

稀疏图
经常要遍历某个顶点的所有邻接点
DFS / BFS 这类顺着边往外扩的算法

因为邻接表不会像邻接矩阵那样，把大量“根本没边的位置”也强行开出来。

6.7 邻接表：原书思路版伪代码¶

邻接表最核心的动作同样是：

初始化顶点表
创建边结点
挂边

可以先抽成下面这种思路：

InitALGraph(G, 顶点序列):
    G.vexnum = 顶点个数
    G.arcnum = 0
    for i = 0..n-1:
        G.vertices[i].data = 顶点名
        G.vertices[i].firstarc = NULL

AddArcNode(G, i, j, w):
    创建新边结点 p
    p.adjvex = j
    p.weight = w
    p.nextarc = G.vertices[i].firstarc
    G.vertices[i].firstarc = p

AddEdge(G, vi, vj, w):
    找到 vi 和 vj 下标 i, j
    挂上 i -> j
    若为无向图:
        再挂上 j -> i

这里最重要的不是背头插法，而是理解：

邻接表在存“边链”
同一个顶点的所有邻接点都集中挂在一起
无向图本来一条边，在邻接表里通常要表现成两条方向相反的记录

6.8 邻接表：对应真实代码¶

第6章代码首稿里，这部分已经落成真实 C 代码，对应位置是：

第6章普通代码版（约第179行） CreateArcNode
第6章普通代码版（约第212行） InitALGraph
第6章普通代码版（约第236行） LocateVertexAL
第6章普通代码版（约第254行） AddArcNode
第6章普通代码版（约第271行） AddEdgeAL
第6章普通代码版（约第296行） PrintALGraph

其中最值得先看懂的是：

bool AddArcNode(ALGraph *graph, int from, int to, int weight) {
    ArcNode *node;

    if (graph == NULL || from < 0 || from >= graph->vexnum || to < 0 || to >= graph->vexnum) {
        return false;
    }

    node = CreateArcNode(to, weight);
    if (node == NULL) {
        return false;
    }

    node->nextarc = graph->vertices[from].firstarc;
    graph->vertices[from].firstarc = node;
    return true;
}

这段代码要重点看懂两件事：

新边结点为什么先指向旧表头
为什么再让表头改成新结点

这就是链式结构里最经典的“头插法”。

6.9 邻接矩阵 vs 邻接表：怎么做选择¶

这是第6章最经典的比较题之一。

邻接矩阵的优势¶

判断两顶点是否有边非常快
结构直观
适合稠密图

邻接矩阵的劣势¶

空间消耗固定是 O(n^2)
边少时浪费明显

邻接表的优势¶

更适合稀疏图
遍历某顶点所有邻接点更自然
更贴合 DFS / BFS

邻接表的劣势¶

判断两顶点是否直接有边不如矩阵快
结构上比矩阵更绕一点

一句话选法：

稠密图偏矩阵
稀疏图偏邻接表
强调邻接查询偏矩阵
强调遍历扩展偏邻接表

6.10 这一节和后面遍历是什么关系¶

这节必须学明白的根本原因是：

后面的 DFS / BFS 不是凭空写出来的，它一定依赖图的存储结构。

比如：

矩阵版遍历是“扫这一整行”
邻接表版遍历是“顺着边链往下走”

也就是说，遍历本质上是在回答：

已知当前顶点，下一批能走到的顶点我该怎么找？

而这个问题的答案，正是存储结构决定的。

6.11 6.2 高频易错点¶

错点 1：把无向图在邻接表里只挂一条边¶

无向图虽然逻辑上是一条边，但在邻接表里通常需要：

i -> j
j -> i

都挂出来。

错点 2：把邻接矩阵对角线也写成 `INF`¶

当前代码里对角线写成 0，表示顶点到自身的距离 / 权值初始化为 0。
这是后面很多图算法里更自然的写法。

错点 3：只会背“稀疏图用邻接表”，不会解释为什么¶

真正原因是：

稀疏图边少
邻接矩阵会浪费大量空位置
邻接表只为真实存在的边开空间

错点 4：把“存储结构不同”误以为“逻辑图不同”¶

邻接矩阵和邻接表只是同一张图的两种不同表示法。
变的是存储方式，不是图的逻辑关系本身。

7. 6.3 图的遍历¶

这一节是整章代码与算法的核心。

第6章的很多应用题，本质上都建立在两种遍历上：

深度优先搜索 DFS
广度优先搜索 BFS

这两种遍历不是只要“会背定义”就行，而是必须做到：

会手推遍历顺序
会解释为什么是这个顺序
会写真实代码
会把它迁移到连通分量、拓扑排序、最短路等问题

这一节后面会优先做成：

伪代码与真实代码对照
邻接矩阵版 DFS/BFS
邻接表版 DFS/BFS
遍历过程手推示范
高频易错点整理

7.1 为什么图遍历比树遍历更麻烦¶

树遍历虽然也有先序、中序、后序、层序，但树有一个天然优势：

每个结点的孩子关系比较固定
一般不会担心“绕回来重复访问”

图不一样。图里经常会出现：

一个顶点能连到多个顶点
多条路径可能走到同一个顶点
图里可能有环

所以图遍历最关键的不是“怎么走”，而是：

走到一个顶点后，必须立刻标记它已经访问过，否则就可能在环里反复打转。

这也是图遍历和树遍历最大的思维差别之一。

7.2 图遍历先抓哪两个¶

整章最重要的就两个：

深度优先搜索 DFS
广度优先搜索 BFS

你可以先把它们想成两种不同的“探索策略”：

DFS：一条路先走到底，走不动了再回头
BFS：先把离当前顶点最近的一圈都看完，再看下一圈

一句话区分：

DFS 更像“钻进去”
BFS 更像“一层一层铺开”

7.3 DFS：先走深，再回头¶

DFS 的直觉非常像“迷宫探路”：

从起点出发
先找一条能走的路一直往深处走
走到尽头后再回退
再尝试别的分支

这种思路天然适合：

递归
栈

因为“走深 -> 回退”本身就和递归调用栈很像。

7.4 DFS：原书思路版伪代码¶

教材里 DFS 的骨架本质上就这几句：

DFS(G, v):
    访问顶点 v
    visited[v] = true
    for v 的每个邻接点 w:
        if visited[w] == false:
            DFS(G, w)

这段伪代码真正要理解的重点只有两个：

为什么“访问后马上标记”
为什么是“遇到一个没访问过的邻接点就立刻递归下去”

第一点是为了防止重复访问。
第二点决定了它一定会“先走深”。

7.5 邻接矩阵版 DFS：对应真实代码¶

第6章当前代码里，矩阵版 DFS 在这里：

第6章普通代码版（约第347行） DFSAMUtil
第6章普通代码版（约第361行） DFSAM

最核心的真实代码是：

void DFSAMUtil(const AMGraph *graph, int v, bool visited[]) {
    int w;

    visited[v] = true;
    VisitVertex(graph->vexs[v]);

    for (w = 0; w < graph->vexnum; w++) {
        if (!visited[w] && graph->edges[v][w] != INF && graph->edges[v][w] != 0) {
            DFSAMUtil(graph, w, visited);
        }
    }
}

这里最该盯住的地方是：

先 visited[v] = true
再访问邻接点
邻接点的寻找方式是“把这一行从左扫到右”

也就是说：

矩阵版 DFS 的遍历顺序，和矩阵里邻接点的扫描顺序直接相关。

7.6 BFS：先近后远，逐层扩展¶

BFS 的直觉更像“波纹一圈圈扩散”：

先访问起点
再访问和起点直接相连的所有顶点
再访问距离为 2 的那一层
再访问下一层

它最核心的数据结构不是栈，而是：

队列

因为谁先被发现，谁就应该先去扩展它的邻接点。

7.7 BFS：原书思路版伪代码¶

BFS 的骨架本质上就是：

BFS(G, v):
    访问顶点 v
    visited[v] = true
    v 入队
    while 队列非空:
        出队一个顶点 u
        for u 的每个邻接点 w:
            if visited[w] == false:
                访问 w
                visited[w] = true
                w 入队

这里最重要的不是机械记步骤，而是看清：

为什么访问后立刻标记
为什么标记后要立刻入队
为什么队列保证了“先近后远”

7.8 邻接矩阵版 BFS：对应真实代码¶

第6章当前代码里，矩阵版 BFS 在这里：

第6章普通代码版（约第377行） BFSAM

最核心的代码段是：

while (!IsQueueEmpty(&queue)) {
    Dequeue(&queue, &v);
    for (w = 0; w < graph->vexnum; w++) {
        if (!visited[w] && graph->edges[v][w] != INF && graph->edges[v][w] != 0) {
            visited[w] = true;
            VisitVertex(graph->vexs[w]);
            Enqueue(&queue, w);
        }
    }
}

这段代码最值得学生感受到的是：

当前出队的是“这一层里轮到扩展的点”
扫描这一行就能找到它所有直接邻接点
邻接点按发现顺序入队，于是下一层会按这个顺序被处理

7.9 邻接表版 DFS / BFS：为什么写法变了¶

第6章当前代码里，邻接表版遍历在这里：

第6章普通代码版（约第413行） DFSALUtil
第6章普通代码版（约第429行） DFSAL
第6章普通代码版（约第445行） BFSAL

它和矩阵版最本质的区别是：

矩阵版是“扫整行”
邻接表版是“顺着边链表往下走”

也就是说，邻接点的寻找方式完全变了。

但真正不变的核心只有两个：

DFS 还是“发现一个点就继续往深处递归”
BFS 还是“发现一个点就进队列，按层推进”

这也是做题时最重要的迁移能力：

存储结构会变，但遍历思想本身不变。

7.10 为什么当前矩阵版和邻接表版输出顺序不完全一样¶

这是非常值得学生认真看懂的一点。

当前程序实际运行结果里：

DFS by adjacency matrix: A B D C E
BFS by adjacency matrix: A B C D E
DFS by adjacency list: A C E D B
BFS by adjacency list: A C B E D

很多人看到这里会紧张：

怎么同一张图，结果还不一样，是不是代码错了？

不一定错。
这里的关键在于：

图遍历顺序本来就和“邻接点被扫描的顺序”有关
当前邻接表用的是“头插法”
头插法会让后插入的边排到前面

所以在邻接表里，某个顶点的邻接点顺序，可能和你加边时的直觉顺序不同。

这正是学习图遍历时必须建立的意识：

遍历结果通常不是唯一的，它依赖于邻接点访问次序。

7.11 非连通图为什么还要外面再套一层循环¶

无论是 DFSAM、BFSAM、DFSAL 还是 BFSAL，你会发现代码外面都套了一层：

for (i = 0; i < graph->vexnum; i++) {
    if (!visited[i]) {
        ...
    }
}

这一步非常重要，因为它在解决：

如果图不是连通的，只从一个顶点出发，并不能访问到所有顶点。

所以外层循环的作用就是：

当前一个连通分量走完后
再去找下一个还没访问过的顶点
从它重新启动一轮遍历

这一步后面会直接连到：

连通分量问题
强连通分量问题

7.12 6.3 高频易错点¶

错点 1：访问和标记顺序写反¶

最稳的写法通常是：

发现一个顶点
立刻标记为已访问
再决定递归或入队

如果标记太晚，就可能重复入栈 / 入队。

错点 2：把 BFS 也写成了递归往深处走¶

只要你的代码表现为“一路先走到底”，那它更像 DFS。
BFS 的灵魂在队列，不在递归。

错点 3：忽略非连通图¶

很多学生写遍历时只从 0 号顶点出发一次，就结束了。
这样只适用于“题目已经保证图连通”的情况。

错点 4：把遍历结果当成唯一答案¶

图遍历序列往往不是唯一的。
决定顺序的关键通常是：

邻接点的存储顺序
邻接点的扫描顺序

错点 5：搞不清矩阵版和邻接表版代码到底差在哪¶

最核心的差异其实只有一处：

矩阵版：邻接点来自一整行扫描
邻接表版：邻接点来自边链表扫描

遍历的大方向并没有变。

7.13 这一节和后面应用题怎么接¶

这一节不是孤立的，它后面会直接长出很多题型：

DFS 可以自然接连通分量、拓扑排序（递归后序思路）
BFS 可以自然接无权图最短路径、分层问题
两者都能接“遍历序列判断题”

所以第6章真正的学习顺序不是：

背完遍历再去看应用

而应该是：

先把遍历思想吃透
再把应用题当成遍历的延伸

8. 6.4 图的应用¶

这一节的内容多，但不建议一上来全压在一起。

后续建议按这个顺序推进：

连通性 / 连通分量
拓扑排序
最小生成树
最短路径
关键路径

原因很简单：

连通性和遍历联系最直接
拓扑排序对有向无环图理解要求高
最小生成树和最短路径算法更多，也更容易绕
关键路径通常建立在前面都清楚之后才更顺

8.1 为什么图的应用看起来一下子变多了¶

前面的 6.1、6.2、6.3 其实已经把第6章最核心的基础铺好了：

6.1 告诉我们图有哪些概念
6.2 告诉我们图怎么存
6.3 告诉我们图上怎么走

而图的应用，本质上就是在回答：

如果我已经会表示图、也会沿着图去走，那我能在这张关系网络上解决哪些典型问题？

所以这一节虽然题型多，但不是凭空冒出来的，而是前面三节的自然延伸。

8.2 第一类应用：连通分量¶

连通分量是最适合从遍历直接长出来的一类题。

核心想法非常朴素：

从一个还没访问过的顶点出发做一次 DFS/BFS
当前这一趟遍历能走到的所有顶点，属于同一个连通分量
图里还有没访问过的顶点，就说明还有别的连通分量

也就是说：

连通分量统计，本质上就是“遍历启动了几次”。

对应真实代码¶

第6章代码里，这部分已经落地到：

第6章普通代码版（约第483行） DFSMarkAM
第6章普通代码版（约第497行） CountConnectedComponentsAM

最核心的代码思想是：

for (i = 0; i < graph->vexnum; i++) {
    if (!visited[i]) {
        components++;
        DFSMarkAM(graph, i, visited);
    }
}

这里一定要看懂：

components++ 的时机为什么放在进入新一轮遍历之前
为什么不是“走到一个点就加一”

因为我们统计的不是顶点数，而是“独立的连通块数”。

8.3 第二类应用：拓扑排序¶

拓扑排序只讨论一种特殊图：

有向无环图（DAG）

它最适合表示：

任务先后依赖
课程先修关系
工程活动先后关系

拓扑排序想解决的问题是：

在不违反先后依赖的前提下，顶点能排成什么顺序？

最该抓的直觉¶

如果一个顶点当前入度为 0，就说明：

没有任何前驱还压着它
它现在可以放心排到前面

所以拓扑排序的标准思路就是：

找入度为 0 的顶点
输出它
删掉它发出的边
看谁因此变成新的入度为 0

对应真实代码¶

第6章代码里，这部分已经落地到：

第6章普通代码版（约第517行） TopologicalSortAL

最关键的不是代码长短，而是这两个动作：

先统计每个顶点入度
再用队列不断处理入度为 0 的顶点

当前程序的示例输出是：

Topological order: ABCDEF

这里也要提醒学生：

拓扑序列通常不唯一
当前输出只是因为样例图和处理顺序恰好得到这一种结果

8.4 第三类应用：最小生成树¶

最小生成树只讨论：

连通图
带权图
无向图

它想解决的问题是：

在保证所有顶点都连通的前提下，总权值尽量小。

这里一定要分清它和最短路径的区别：

最小生成树关注“整张图都连起来，总代价最小”
最短路径关注“从一个点到另一个点的路最短”

这两个目标完全不是一回事。

当前代码先落地了 Prim¶

第6章代码里，这部分已经落地到：

第6章普通代码版（约第555行） PrimMSTWeightAM

Prim 的核心直觉是：

先有一棵“正在长大的树”
每次从“树内 -> 树外”选一条最短边
把新的顶点接进来

当前程序输出是：

Prim MST total weight: 15

这说明我们现在已经不只是讲概念，而是已经把最小生成树真正跑起来了。

8.5 第四类应用：最短路径¶

最短路径是图应用里最经典也最容易混的一类。

第 6 章建议先抓的是：

单源最短路径

也就是：

从一个源点出发，到其余各顶点的最短路是多少？

当前代码先落地了 Dijkstra¶

第6章代码里，这部分已经落地到：

第6章普通代码版（约第602行） DijkstraAM
第6章普通代码版（约第646行） PrintDijkstraResult

最该先建立的直觉是：

dist[i] 存当前已知的最短距离估计
每次从还没确定的顶点里，挑当前距离最小的一个
用它去松弛别的顶点

当前程序输出是：

Dijkstra distances from A: A=0 B=7 C=3 D=9 E=5

这说明：

从 A 到 C 的最短路长度是 3
从 A 到 B 虽然有直接边 10，但绕 C 走会更短，所以结果变成了 7

这正好能帮学生理解：

最短路算法不是只看“有没有直接边”，而是看“总体代价最小”。

8.6 这一节里最容易混的两组概念¶

生成树 vs 最短路径¶

这是第6章最经典的混淆点。

最小生成树：让整张图连起来，总权值最小
最短路径：让某个起点到某个终点的路径最短

最小生成树上的两点路径，不一定就是原图中的最短路径。

连通分量 vs 强连通分量¶

这里先从无向图连通分量开始展开。rnrn后面如果进入更深入的有向图分量问题，就要改谈强连通分量。

所以做题时一定先问：

当前图是无向图还是有向图
题目问的是“连通”还是“互相可达”

8.7 当前程序已经把哪几类图应用跑起来了¶

到这一部分为止，第6章代码已经能真实演示：

无向图连通分量统计
有向无环图拓扑排序
带权无向图的 Prim 最小生成树
带权有向图的 Dijkstra 单源最短路径

也就是说，第6章现在已经从“遍历”正式走进“应用”了。

8.8 6.4 高频易错点¶

错点 1：把拓扑排序拿去处理有环图¶

只要图里有环，就不可能存在合法拓扑序列。

错点 2：把 Prim 当成最短路径算法¶

Prim 是长一棵树，不是找某个源点到所有点的最短路。

错点 3：把 Dijkstra 用到含负权边的场景¶

标准 Dijkstra 不适合有负权边的情况。
这一点后面做题时必须特别警惕。

错点 4：把“分量个数”理解成“顶点没访问到的次数”¶

分量个数不是顶点个数，而是“独立启动遍历的次数”。

8.10 原书高频应用题该怎么分类抓¶

第6章应用题很多，如果不先分类，学生很容易觉得“全都是图算法，全都长得差不多”。
其实最稳的抓法是先按问题类型分：

第一类：遍历延伸题¶

典型问法：

图有多少个连通分量
从某个顶点出发的 DFS/BFS 序列是什么
修改 DFS / BFS 后，结果有什么性质

这一类题的核心不是新算法，而是：

先把遍历本身想清楚。

第二类：有向无环图题¶

典型问法：

图能不能拓扑排序
某个序列是不是合法拓扑序列
拓扑序列有几个
拓扑序列是否唯一

这一类题的核心是：

盯住入度为 0 的顶点，以及图里是否存在环。

第三类：带权无向图题¶

典型问法：

求最小生成树
比较 Prim 和 Kruskal 的选边过程
判断某条边会不会出现在最小生成树里

这一类题的核心是：

整张图连起来，总代价最小。

第四类：带权有向图题¶

典型问法：

单源最短路径
Dijkstra 执行过程中下一个被确定的顶点是谁
某轮松弛后 dist 数组如何变化

这一类题的核心是：

从源点出发，谁当前最近，就先确定谁。

8.11 连通分量类题：最稳的做题思路¶

这类题不要一上来数边，也不要先猜答案。
最稳的步骤是：

先看题目给的是无向图还是有向图
如果是无向图，先谈连通分量
找一个还没访问过的顶点，启动一轮 DFS/BFS
当前这一趟遍历能走到的都算同一块
重复，直到所有顶点都访问完

一句话压缩成方法：

连通分量个数 = 需要独立启动遍历的次数。

典型误区¶

把“访问到多少个顶点”和“有多少个分量”混掉
把有向图也直接按无向图方式谈连通分量

8.12 拓扑排序类题：先问“有没有环”¶

拓扑排序题最容易犯的错，就是上来就排序。
其实第一步永远应该先问：

这张图是不是有向无环图？

只要有环，就不可能有合法拓扑序列。

做题固定步骤¶

先找所有入度为 0 的顶点
这些顶点都可以排在当前最前面
选走一个后，删掉它发出的边
再看谁新变成入度 0
如果某一步没有入度 0 顶点、但图还没删空，就说明有环

唯一性怎么判断¶

如果在排序过程中，每一步都只有一个入度为 0 的顶点可选，那么拓扑序列通常就是唯一的。
如果某一步同时有多个选择，那么拓扑序列往往就不唯一。

典型误区¶

只会排序，不会判断“是否存在”
只会判断“是否存在”，不会看“是否唯一”
把有向图中“顶点在前”误解成“一定有直接弧”

8.13 最小生成树类题：先分清和最短路不是一回事¶

这一类题最关键的不是公式，而是先把目标讲清：

最小生成树要的是“整张图都连起来”
它不关心某两个点之间那条具体路径是不是最短

Prim 题怎么想¶

Prim 题最稳的思路是：

先盯住“当前已经在树里的顶点集合”
每一步都从“树内 -> 树外”选最小边
只要新顶点被拉进来，树就长大一格

Kruskal 题怎么想¶

Kruskal 更像：

先按边权从小到大看边
能加且不成环就加
会成环就跳过

典型误区¶

把 Prim 和 Dijkstra 的“看起来都在选最小”混掉
以为最小生成树上的任意两点路径一定最短
以为权值最小的边一定会出现在所有最小生成树里

8.14 最短路径类题：先抓 Dijkstra 的状态变化¶

最短路径题之所以难，不是因为公式多，而是因为学生经常没盯住算法状态。

对于 Dijkstra，最该盯住的是：

dist[i]：当前已知从源点到 i 的最短距离估计
finalized[i]：这个顶点的最短路是否已经最终确定
path[i]：当前最短路上 i 的前驱是谁

做题固定步骤¶

先把源点到各点的初始距离写出来
选出当前 dist 最小且未确定的顶点
把它标记为已确定
用它去更新别的顶点的 dist
重复直到所有需要的顶点都处理完

当前程序输出怎么理解¶

当前代码输出：

Dijkstra distances from A: A=0 B=7 C=3 D=9 E=5

这里最值得学生理解的不是结果本身，而是：

A -> B 直接边是 10
但 A -> C -> B 更短，所以最后 B=7

这说明最短路题不能只看局部最近边，而是要看“当前最优路径估计”。

典型误区¶

把 Dijkstra 用到负权边图
把“已知最短估计”误认为“已经最终确定”
松弛时忘了判断中间顶点是否可达

8.15 关键路径先放在哪个位置理解¶

关键路径也是第6章应用的重要部分，但它比前面几类更依赖：

有向无环图
拓扑排序
事件最早 / 最迟发生时间

建议按下面的学习顺序推进：

先吃透连通分量
再吃透拓扑排序
再区分清最小生成树和最短路径
最后再进入关键路径

也就是说，关键路径不是不要做，而是放在这几类之后会更顺。

8.16 应用题基础训练建议¶

建议按下面的顺序完成第 6 章应用题训练：

连通分量 / 遍历序列题
拓扑排序存在性与唯一性题
Prim / Kruskal 选边过程题
Dijkstra 某轮 dist 更新题
AOE 网 / 关键路径题

这样刷的好处是：

从最依赖遍历的地方先开始
再进入 DAG 逻辑
再进入带权图优化问题

8.17 应用题学习成果¶

至此，6.4 图的应用 已经不再只是“介绍几种算法”，而是开始具备了：

应用题分类框架
每类题的固定思路
典型误区提醒
当前代码输出和题型理解的对应关系

这样学生后面再看原书试题时，就不容易觉得第6章像一堆彼此无关的算法了。

9. 第6章代码阅读入口¶

第6章当前代码已经不只包含“存储 + 遍历”首稿，而是已经形成了从基础结构到主流应用的完整主干。

最值得优先看的核心对象有：

邻接矩阵结构
邻接表结构
DFS
BFS
连通分量统计
拓扑排序
Prim 最小生成树
Dijkstra 单源最短路径

后续如需阅读代码，建议按这个顺序：

先看图的存储结构定义
再看建图和加边操作
再看 DFS
最后看 BFS

如果已经把遍历部分吃顺，再继续往后读：

连通分量
拓扑排序
Prim
Dijkstra

因为图算法不是一组彼此割裂的函数，而是“存储 -> 遍历 -> 应用”一层层长出来的。

11. 本章资料概览¶

本章目前提供的核心内容包括：

OCR 底稿：本章 OCR 底稿
页面资源目录：本章页面图像
自学讲义：本书第6章正文
真实代码：第6章普通代码版
逐行注释版代码：第6章逐行注释版代码
兼容编码逐行版：第6章兼容编码版逐行注释代码
构建脚本：本章构建脚本
可执行文件：本章示例程序

至此，第 6 章的主干内容、代码和题解框架已经基本完整。

12. 深入学习方向¶

第 6 章主骨架已经完整，如需继续拔高，可沿下面方向展开：

把 Kruskal 做成真实代码专项
把 Floyd 做成真实代码专项
把 关键路径 做成完整代码专题
继续扩充原书试题逐题详细解答版

也就是说，第 6 章现在已经具备完整章节的主体结构；后续继续扩展时，主要是做拔高与增厚。

13. 第6章题型索引¶

到目前为止，第6章已经可以按题型来查了。
这一步很重要，因为图这一章最常见的问题不是完全不会，而是做题时无法快速判断该调用哪一类算法。

13.1 基本概念与性质类¶

这一类题通常围绕：

图、顶点、边、弧的定义
无向图 / 有向图 / 完全图 / 简单图 / 多重图
顶点度、入度、出度
路径、回路、简单路径、简单回路
连通图、强连通图、生成树

这类题的核心不是算，而是：

分清术语边界。

13.2 存储结构类¶

这一类题通常围绕：

邻接矩阵怎么表示
邻接表怎么表示
稠密图 / 稀疏图该怎么选
邻接矩阵和邻接表各自的优缺点

这类题的核心不是背定义，而是：

先看题目更强调“查关系”还是“顺着边遍历”。

13.3 遍历序列类¶

这一类题通常围绕：

DFS 序列
BFS 序列
修改访问顺序后结果怎么变
非连通图遍历会怎么补外层循环

这类题的核心是：

遍历序列往往不唯一，关键看邻接点访问顺序。

13.4 连通性与分量类¶

这一类题通常围绕：

连通分量有几个
强连通分量有几个
一个图在什么条件下一定连通 / 一定不连通

这类题最稳的切入点是：

先分无向图还是有向图，再决定谈连通还是强连通。

13.5 拓扑排序类¶

这一类题通常围绕：

某图是否存在拓扑序列
某个序列是否为合法拓扑序列
拓扑序列是否唯一
某一步能选哪些顶点

这类题的核心抓手是：

入度为 0 的顶点。

13.6 最小生成树类¶

这一类题通常围绕：

Prim 过程
Kruskal 过程
某条边是否会被选中
最小生成树总权值

这类题的核心不是“从一个点走到另一个点”，而是：

整张图都连起来，总代价最小。

13.7 最短路径类¶

这一类题通常围绕：

Dijkstra 某轮选择哪个顶点
某轮更新后 dist 数组怎么变
某个点到源点的最短路长度是多少

这类题的核心抓手是：

当前未确定顶点里，谁的 dist 最小。

13.8 关键路径类¶

这一类题通常围绕：

AOE 网
最早发生时间 / 最迟发生时间
关键活动
关键路径长度

这类题建议放在：

拓扑排序
最小生成树 / 最短路径

之后再集中处理，会更顺。

14. 刷题路径¶

第6章如果直接乱刷，很容易感觉题型散。
最稳的路线是按“概念 -> 存储 -> 遍历 -> 应用”推进。

14.1 基础训练：只抓概念和性质¶

目标：

先把术语体系搭起来
不让自己在题目前期就被概念绊倒

重点：

顶点、边、弧
度、入度、出度
连通 / 强连通
路径 / 回路
生成树

14.2 进阶训练：只抓存储结构¶

目标：

看懂邻接矩阵
看懂邻接表
能判断什么场景更适合哪种结构

重点：

稠密图 vs 稀疏图
邻接矩阵 vs 邻接表
无向图在邻接表里为什么要挂两次

14.3 强化训练：专刷 DFS / BFS¶

目标：

把遍历顺序真正手推出
理解遍历为什么不是唯一的

重点：

邻接点扫描顺序
访问标记
非连通图的外层循环

14.4 第四轮：进入连通分量和拓扑排序¶

目标：

先把最依赖遍历的应用题吃下来
建立“遍历就是应用题起点”的感觉

重点：

连通分量
强连通分量概念
拓扑排序存在性
拓扑序列唯一性

14.5 第五轮：进入最小生成树和最短路径¶

目标：

分清 Prim / Kruskal / Dijkstra 的目标差异
不再把这些“都在选最小”的算法混掉

重点：

Prim 是长树
Kruskal 是按边加
Dijkstra 是从源点出发做最短路

14.6 第六轮：最后集中处理关键路径¶

目标：

在前面都稳住后，再做关键路径
不让自己在 AOE 网上一下子同时卡住多个概念

重点：

拓扑排序基础
事件最早 / 最迟发生时间
关键活动和关键路径

15. 自学检查清单¶

这一部分最适合在你学完一轮后回头看。
如果很多条还做不到，就说明这章还没真正吃透。

15.1 概念层¶

你是否能做到：

不看书，解释图和树的区别
说清无向图和有向图的区别
说清连通和强连通的区别
说清生成树和连通分量的区别

15.2 存储层¶

你是否能做到：

自己画出一张图的邻接矩阵
自己写出一张图的邻接表
解释为什么稀疏图更适合邻接表
解释为什么邻接矩阵更适合直接判断两点是否有边

15.3 遍历层¶

你是否能做到：

手推 DFS 序列
手推 BFS 序列
解释为什么遍历序列往往不唯一
解释为什么图遍历一定要做访问标记
解释为什么非连通图遍历要补外层循环

15.4 应用层¶

你是否能做到：

用“遍历启动次数”解释连通分量
用“入度为 0”解释拓扑排序
用“树内到树外的最短边”解释 Prim
用“当前最短估计”解释 Dijkstra
说清最小生成树和最短路径不是一回事

15.5 代码层¶

你是否能做到：

看懂 第6章普通代码版 里的矩阵版 DFS/BFS
看懂 第6章普通代码版 里的邻接表版 DFS/BFS
看懂 第6章普通代码版 里的连通分量、拓扑排序、Prim、Dijkstra
卡住时能切换到 第6章逐行注释版代码 继续读

15.6 阶段总结¶

如果上面大部分你都能做到，那么第6章已经不是“看过了”，而是已经开始进入“真会了”的阶段。

如果还做不到，也不用急。
第6章本来就是整本书里结构最杂、算法最密的一章之一，关键不是一口气背下来，而是按题型把它慢慢拆开。

16. 原书试题区整理版¶

这一部分不是把原书题目机械抄一遍，而是按“题目在考什么”重新收口。
这样学生后面刷题时，能先判断题型，再决定调用哪一套思路。

16.1 基本概念与性质题¶

原书这一类题高频考：

路径、回路、简单路径、简单回路的定义
无向图 / 有向图的度数关系
连通图、非连通图、强连通图的边数条件
生成树、生成森林
完全图、稀疏图、稠密图

做题思路¶

先看题目讨论的是无向图还是有向图
再看它问的是“定义辨析”还是“边数条件”
若涉及边数、度数，优先写出公式关系

最常用到的结论¶

无向图所有顶点度之和 = 2e
有向图所有顶点入度之和 = 出度之和 = e
n 个顶点的连通无向图至少有 n - 1 条边
n 个顶点的强连通有向图至少有 n 条边
n 个顶点的生成树一定有 n - 1 条边

易错点¶

把“路径长度”看成顶点数
把“连通”直接套到有向图上
把生成树和连通分量混掉

16.2 存储结构题¶

原书这一类题高频考：

邻接矩阵怎么写
邻接表怎么写
邻接矩阵和邻接表如何互相理解
哪种存储结构更适合稠密图 / 稀疏图

做题思路¶

先判断图是有向还是无向
若画邻接矩阵，先把对角线和无边位置想清
若写邻接表，先把“每个顶点后面挂哪些邻接点”列出来

易错点¶

无向图在邻接表里只挂一次
把逻辑图变了，误以为只是换了存储
只会写结构，不会解释为什么选它

16.3 遍历序列题¶

原书这一类题高频考：

从某顶点出发的 DFS 序列
从某顶点出发的 BFS 序列
修改邻接顺序后，遍历序列怎么变
用 DFS 退栈输出能否得到某种序列性质

做题思路¶

先明确起点
再明确邻接点访问顺序
DFS 就按“能走就往深处走”
BFS 就按“队列逐层展开”

易错点¶

以为遍历序列一定唯一
忘了访问标记
非连通图只遍历了一块就停

16.4 连通分量与强连通分量题¶

原书这一类题高频考：

一个图有多少个连通分量
一个有向图有多少个强连通分量
非连通图在什么边数条件下取极值

做题思路¶

无向图先想连通分量
有向图先想强连通分量
若题目问“最多 / 最少”，优先画极端结构

易错点¶

不区分连通分量和强连通分量
不会画极端图来判断边数上界 / 下界

16.5 拓扑排序题¶

原书这一类题高频考：

图能否拓扑排序
某个序列是不是拓扑序列
拓扑序列有多少个
拓扑序列是否唯一

做题思路¶

先判断是不是 DAG
再找当前所有入度为 0 的顶点
一步一步删边、降入度
若某一步无入度 0 顶点且图未删空，则有环

易错点¶

忽略“有环则无拓扑序”
只会给一个序列，不会判断是否唯一
把“顶点在前”理解成“一定有直接弧”

16.6 最小生成树题¶

原书这一类题高频考：

Prim 算法某一步选哪条边
Kruskal 算法某一步选哪条边
某条边会不会进入最小生成树
最小生成树总代价是多少

做题思路¶

Prim：盯“树内 -> 树外”的最短边
Kruskal：盯“当前最小且不成环”的边
若题目比较两种算法，先分清它们的选边视角

易错点¶

把 Prim 和 Dijkstra 混掉
以为最小生成树一定唯一
以为权值最小边必在所有最小生成树中

16.7 最短路径题¶

原书这一类题高频考：

Dijkstra 某轮选哪个顶点
dist / path 数组如何变化
某条路径是不是最短路径
Floyd / 单源最短路的适用范围

做题思路¶

先写源点到各点的初始距离
选当前最近且未确定的顶点
用它松弛别的点
一轮一轮更新 dist

易错点¶

把“当前估计最短”误当成“已最终确定”
把 Dijkstra 用到负权边
只盯局部最近边，不看整体路径代价

16.8 AOE 网与关键路径题¶

原书这一类题高频考：

最早发生时间 / 最迟发生时间
关键活动
关键路径长度
改变某个活动持续时间后会有什么影响

做题思路¶

先做拓扑排序
正向推最早发生时间
逆向推最迟发生时间
事件或活动最早、最迟时间相等时，往往就是关键部分

易错点¶

没先做拓扑排序就直接算
把事件时间和活动时间混掉
以为任意缩短关键活动都一定缩短总工期

16.9 这一版试题整理的作用¶

后续开始刷第 6 章原书试题时，推荐顺序如下：

先按这一节判断题型
再回到对应讲义部分补概念
再去代码里找对应算法或状态变化

这样刷题时就不会再觉得：

第6章像一堆彼此没关系的图算法

而是会慢慢形成：

概念题怎么做
遍历题怎么做
DAG 题怎么做
带权图题怎么做

这才是第6章真正该建立起来的题感。

17. 原书试题逐题详细解答版（基础部分）¶

这里不追求把整章所有题一次性铺完，而是优先把第 6 章最高频、最能串起全章主线的题做成详细解答版。
这一版优先覆盖：

基本概念判断题
连通性与边数题
遍历题
拓扑排序题
最小生成树题
最短路径题

这样做的目的，是先把第6章最常见的出题套路打透。

17.1 高频题 1：无向图有 `n` 个顶点、`n` 条边，一定是什么情况¶

题目本质¶

这类题在问：

当无向图的边数比树多 1 条时，最稳定能推出什么结论？

正确结论¶

一定有环。

详细思路¶

n 个顶点的无向连通树，边数一定是 n - 1
如果一张无向图有 n 个顶点、n 条边
那么它的边数已经比树多了 1 条
对无向简单图来说，多出来这一条边一定会造成一个回路

这里最稳的理解不是死背，而是把它想成：

一棵树本来刚好连通且无环
再往里面加一条边
原来两点之间已经有一条路径
这条新边一加进去，就和原路径围成了环

易错点¶

把“有 n 条边”误以为“一定连通”
忽略了题目问的是“必然能推出什么”，不是“可能是什么”

17.2 高频题 2：从无向图任意顶点出发做一次 DFS，能访问所有顶点，说明什么¶

题目本质¶

这类题在考：

图遍历和连通性的关系。

正确结论¶

该图是连通图。

详细思路¶

对无向图来说，如果从某个顶点出发
顺着边走，最终能访问到所有顶点
就说明任意顶点都和起点在同一个连通块里
于是整张图只有一个连通分量
因而该图连通

一句话压缩：

一次遍历覆盖全图，说明只有一个连通分量。

易错点¶

把无向图的“连通”误说成“强连通”
忘了题目说的是“任意顶点出发都可覆盖全部”

17.3 高频题 3：非连通无向图有 28 条边，至少有多少个顶点¶

题目本质¶

这类题在考：

非连通图在边数固定时，顶点数什么时候最少？

正确结论¶

至少有 9 个顶点。

详细思路¶

要让顶点数尽量少，就要让边尽量“挤”在少数顶点里。
对非连通无向图来说，最极端的情况是：

先让一部分顶点构成一个完全图
再单独留出一个孤立顶点，保证整图非连通

现在要找一个完全图，边数正好是 28：

n(n - 1) / 2 = 28

试一下：

8 * 7 / 2 = 28

说明 8 个顶点能构成一张有 28 条边的完全图。
但题目要求整图非连通，所以还得再加至少 1 个孤立顶点。

于是最少顶点数是：

8 + 1 = 9

易错点¶

只算出完全图的 8 个顶点就停了
忘了题目要求“非连通”

17.4 高频题 4：`n` 个顶点的连通无向图、强连通有向图，边至少各是多少¶

题目本质¶

这类题通常是一道对比题：

连通无向图最少边数是多少？强连通有向图最少边数是多少？

正确结论¶

连通无向图最少边数：n - 1
强连通有向图最少边数：n

详细思路¶

连通无向图¶

边最少时，就是一棵树。
树有 n 个顶点，则边数一定是：

n - 1

强连通有向图¶

边最少时，可以把 n 个顶点连成一个有向环。
每个顶点都有一条出边、一条入边，于是总弧数是：

这两类题一定要对着图像去想，不要只背结果。

易错点¶

把强连通图也写成 n - 1
把“至少”理解成“恰好只有一种结构”

17.5 高频题 5：邻接矩阵和邻接表怎么选¶

题目本质¶

这类题不是在问你会不会写结构，而是在问：

什么场景下更适合哪种存储方式？

标准抓法¶

如果题目强调“稠密图”“判断两点是否邻接很频繁”，优先想邻接矩阵
如果题目强调“稀疏图”“经常遍历某顶点所有邻接点”，优先想邻接表

详细思路¶

邻接矩阵¶

优点：

查两点是否有边快
结构直观

缺点：

空间固定 O(n^2)
稀疏图浪费明显

邻接表¶

优点：

适合稀疏图
顺着边遍历更自然

缺点：

查两点是否直接邻接不如矩阵快

易错点¶

把“稀疏图更适合邻接表”背成口号，却不会解释原因
以为邻接矩阵和邻接表表示的是两种不同的图

17.6 高频题 6：拓扑排序题，第一步到底先看什么¶

题目本质¶

这类题最常见的坑是：

一上来就排，不先判断有没有环。

最稳做法¶

第一步永远先看：

当前有没有入度为 0 的顶点

详细思路¶

如果图里存在环，那么在某一时刻会出现：
图还没删空
但没有入度为 0 的顶点可选
这时就说明无法继续做拓扑排序
所以拓扑排序题最核心的抓手，不是背序列，而是看“入度为 0 的顶点集合”

如果一道题还进一步问“拓扑序是否唯一”，那么继续看：

每一步是否都只有一个入度为 0 的顶点
若某一步有多个可选，拓扑序往往就不唯一

易错点¶

把“有向图”直接默认成“可拓扑排序”
只会写出一个序列，不会判断唯一性

17.7 高频题 7：Prim 和 Dijkstra 都在选最小，它们到底差在哪¶

题目本质¶

这是第6章最高频混淆点之一。

核心区别¶

Prim：解决最小生成树
Dijkstra：解决单源最短路径

详细思路¶

Prim 在做什么¶

它维护的是：

当前生成树到树外各顶点的最小连接代价

它每次选的是：

哪个顶点用最小代价接进“整棵树”

Dijkstra 在做什么¶

它维护的是：

从源点到各顶点的当前最短距离估计

它每次选的是：

当前离源点最近、且最短路已经可以最终确定的顶点

所以它们虽然都在“选最小”，但选的对象和优化目标完全不同。

易错点¶

只看“都在选最小”就以为是同一类算法
误以为最小生成树上的两点路径一定是原图最短路径

17.8 高频题 8：Dijkstra 题最该盯哪个状态¶

题目本质¶

这类题考的不是你会不会背算法名，而是：

你能不能跟住 dist 的变化。

最该盯住的量¶

dist[i]：当前最短距离估计
finalized[i]：最短路是否已经最终确定
path[i]：当前前驱

做题步骤¶

先写源点到各点的初值
选出当前 dist 最小的未确定顶点
确定它
用它松弛其他点
重复

对应当前程序输出¶

当前代码输出：

Dijkstra distances from A: A=0 B=7 C=3 D=9 E=5

这里特别值得理解的一点是：

A -> B 直接边是 10
但 A -> C -> B = 3 + 4 = 7

这说明：

最短路算法看的不是“有没有直达边”，而是“总路径代价是否更小”。

易错点¶

把当前最小估计误当成一定已经最终正确
忘记负权边会破坏标准 Dijkstra 的适用条件

17.9 学习提示¶

如果你把这一部分吃透，第6章已经能真正接住最常见的高频题了：

基本概念题不再只靠猜
连通性与边数题开始有极端图思维
存储结构题知道如何判断场景
拓扑排序题知道先盯入度 0
Prim 和 Dijkstra 不再混
最短路径题开始能跟 dist 状态走

这时第6章就不再只是“知识点很多”，而是开始慢慢变成“题目一看就知道往哪套方法上靠”的状态。

17.10 高频题 9：拓扑序列是否存在、是否唯一，怎么判断¶

题目本质¶

这类题表面上在问“拓扑序列”，本质上其实在考两件事：

图里有没有环
每一步入度为 0 的顶点是不是唯一

详细思路¶

先判断是否存在¶

拓扑排序只属于 DAG。
所以第一步一定是：

观察当前是否有入度为 0 的顶点
如果图还没删空、却已经没有入度为 0 的顶点
那就说明图中有环，拓扑序列不存在

再判断是否唯一¶

如果拓扑排序过程中：

每一步都只有一个入度为 0 的顶点

那么拓扑序列通常就是唯一的。

如果某一步出现：

同时有多个入度为 0 的顶点

那么这些顶点谁先谁后都可能合法，于是拓扑序列一般不唯一。

一句做题口诀¶

先看有没有入度 0，再看入度 0 是否唯一。

易错点¶

只会写一个拓扑序列，却不会判断“是否存在”
只会判断“是否存在”，却不会判断“是否唯一”
看到有向图就默认能拓扑排序

17.11 高频题 10：Prim 和 Kruskal 的选边过程怎么抓¶

题目本质¶

这类题不是在问你会不会背算法步骤，而是在问：

你能不能把“选边视角”分清。

Prim 的抓法¶

Prim 每一步都问：

当前生成树内部，哪一条通往外部的边最短？

也就是说，它盯的是：

树内顶点集合
树外顶点集合
树内到树外的最短边

Kruskal 的抓法¶

Kruskal 每一步都问：

当前全图里，剩下的边中最短的一条，若加上去不成环，能不能选？

也就是说，它盯的是：

全局边权从小到大顺序
会不会成环

最稳对比法¶

如果一道题同时给 Prim 和 Kruskal，最稳的比较方法是：

Prim：从点的角度看，树在长大
Kruskal：从边的角度看，边在筛选

易错点¶

把 Prim 当成“全局每次取最小边”
把 Kruskal 当成“从一个起点往外扩”
不会用“是否成环”判断 Kruskal 某条边能不能选

17.12 高频题 11：Dijkstra 某一轮之后 `dist` 数组如何更新¶

题目本质¶

这类题不是考最后答案，而是考：

你能不能跟住某一轮“确定一个新顶点后”的松弛过程。

固定步骤¶

写出当前已经确定的顶点集合
找出当前 dist 最小且未确定的顶点 u
用 u 去尝试更新其他未确定顶点
逐个比较：

dist[u] + w(u, v) 是否小于当前 dist[v]

若更小，就更新。

最该注意的地方¶

更新的是“未确定”的顶点
必须保证 u 到 v 真的有边
必须保证 u 本身可达

对学生最容易卡住的点¶

很多学生会把“选出下一个顶点”和“更新 dist 数组”这两步混在一起。
其实正确节奏应该是：

先选点
再松弛

顺序不要乱。

17.13 高频题 12：AOE 网与关键路径题，第一步为什么一定是拓扑排序¶

题目本质¶

这类题考的是：

事件之间有先后依赖时，如何找出决定总工期的那条关键链。

为什么第一步必须是拓扑排序¶

因为关键路径题里的“最早发生时间”和“最迟发生时间”都建立在：

事件先后关系已经排清
整个图是有向无环图

如果图里有环，就说明：

某些活动存在循环依赖
工程先后关系本身都不合法

那关键路径自然也无从谈起。

做题固定顺序¶

先做拓扑排序
正向求每个事件的最早发生时间
逆向求每个事件的最迟发生时间
找最早和最迟时间差为 0 的关键部分

易错点¶

没做拓扑排序就直接推时间
把事件时间和活动时间混掉
以为关键路径一定唯一

17.14 高频题 13：修改 DFS，在退栈时输出顶点，会得到什么性质¶

题目本质¶

这类题很爱结合 DAG 出：

若在 DFS 递归返回前输出顶点，输出序列具有什么特点？

正确抓法¶

如果图是有向无环图，那么：

DFS 先往深处走
只有当某个顶点的后继都处理完，才会在退栈时输出它

所以退栈输出序列通常和拓扑序有非常紧的关系。

一句话记忆：

在 DAG 上，DFS 退栈输出常能得到逆拓扑序思想。

易错点¶

忘了题目限制是不是 DAG
把普通 DFS 访问序列和退栈输出序列混成一回事

17.15 进阶题解学习提示¶

学完这一部分以后，第 6 章应用题的“后半程主线”也接上来了：

拓扑排序题不再只会机械删点
Prim / Kruskal 的选边视角开始分清
Dijkstra 的状态更新开始能一步步跟下来
关键路径题知道为什么必须先从 DAG 和拓扑排序入手
DFS 相关的高频变形题也开始有抓手

到这里，第6章的题型层已经明显更完整了。

17.16 图的应用代码专题：Kruskal、Floyd、关键路径¶

本节学习重点，是把前面主要停留在“思路题 / 过程题 / 高频题”层的三块内容，进一步落到可运行代码层：

Kruskal 最小生成树
Floyd 多源最短路径
AOE 网关键路径

这样第6章就不再只是“图的应用讲得比较厚”，而是开始更接近“图的应用能完整跑起来”。

17.16.1 Kruskal 真正的核心动作¶

Prim 和 Kruskal 经常一起考，但两者视角完全不同：

Prim 是“从一个点出发，不断向外扩”
Kruskal 是“把所有边按权值从小到大排好，再一条条试”

所以 Kruskal 最该抓的不是“最小生成树”这五个字，而是下面这三个动作：

把边抽出来
按权值排序
用并查集判断“加这条边会不会成环”

这一部分的真实代码已经把这条线完整落到了：

FindSet
UnionSet
CompareEdgeByWeight
KruskalMSTWeightAM

也就是说，学生现在不仅能做题，还能看懂：

为什么 Kruskal 必须有“并查集判环”
为什么它的工作单位是“边”
为什么它和 Prim 看起来都在求最小生成树，但写法完全不一样

17.16.2 Floyd 为什么和 Dijkstra 不是一回事¶

前面 Dijkstra 解决的是：

一个源点到其他所有点的最短路径

而 Floyd 解决的是：

任意两点之间的最短路径

所以 Floyd 的视角不是“以谁为起点往外扩”，而是：

先假设当前只知道直接边
再依次允许每个顶点充当中转点
看看能不能把任意两点的距离继续变短

这一部分的真实代码已经把这条线落到了：

FloydAM
PrintFloydDistances

学生现在可以直接对照运行结果理解：

为什么 Floyd 是一个三重循环
为什么它特别适合“多源最短路”
为什么题里一旦问“任意两点”，就要先想到它

17.16.3 关键路径终于不只是概念题了¶

关键路径最容易把学生绕晕，是因为它同时要处理：

拓扑序
事件最早发生时间 ve
事件最迟发生时间 vl
活动最早开始时间 ee
活动最迟开始时间 el
哪些活动时差为 0

如果只看纸面定义，很容易一层套一层地糊掉。

这里已经把它整理成可运行代码专题：

GetTopologicalOrderAL
CriticalPathAL
PrintCriticalPathResult
BuildSampleAOEGraph

现在这块已经不再只是“知道要先做拓扑排序”，而是能真正看到：

怎么正推 ve
怎么逆推 vl
怎么判断关键活动
项目总工期为什么就是关键路径长度

17.16.4 运行结果观察重点¶

程序新增的关键输出包括：

Kruskal MST total weight: 15
Floyd distance matrix
Critical path project length: 9
ve
vl
Critical activities

这组输出的价值不只是“程序跑通了”，而是：

Prim 和 Kruskal 现在可以直接对照同一张图的结果
Dijkstra 和 Floyd 现在可以直接对照“单源 vs 多源”
关键路径现在终于能从“抽象概念”落到“表 + 图 + 结果”三者对应

17.16.5 本节学习意义¶

学完这一部分以后，第6章最重要的变化是：

图的应用层不再只覆盖“最基础那几种”
原来最容易逼学生回原 PDF 的三块内容，已经明显往前推进
第6章现在更接近“单章就能自学完图的核心算法主线”

17.17 原书试题逐题详细解答：图的应用专题¶

这一部分继续补入的目标很明确：

不再只是讲“算法名字和主线”
而是把学生最容易因为一道题卡住、从而想翻原 PDF 的地方，再多铺一层

这一部分重点补的是：

Floyd 和 Dijkstra 的分工题
Prim 和 Kruskal 的结果与过程题
AOE 网手算题
关键路径唯一性与关键活动判断题
图应用题中最容易混掉的边界题

17.17.1 高频题 14：什么时候该用 Dijkstra，什么时候该用 Floyd¶

题目本质¶

这类题表面在问算法选择，实际在考：

你有没有分清“单源最短路”和“多源最短路”。

正确结论¶

如果题目问“从某一个源点出发，到其余各点的最短路径”，优先想 Dijkstra
如果题目问“任意两点之间的最短路径”，优先想 Floyd

详细思路¶

最稳的判断方式不是看图长什么样，而是看题目问法：

题目反复出现“源点 v0”“从 A 出发”这种表述
这通常就是单源
题目问“所有顶点对”“任意两点”
这通常就是多源

可以这么记：

Dijkstra 盯一个起点，
Floyd 盯整张距离表。

易错点¶

看到“最短路径”四个字就直接写 Dijkstra
忘了 Dijkstra 不能处理带负权边的标准情形
把 Floyd 当成“Dijkstra 多跑几遍”的口头描述，却说不清它的中转点思想

17.17.2 高频题 15：Prim 和 Kruskal 得到的最小生成树一定一样吗¶

题目本质¶

这类题在考：

你有没有分清“最小生成树的总权值”和“最小生成树的具体形状”。

正确结论¶

当图的边权有并列时，Prim 和 Kruskal 得到的具体边集不一定一样
但如果它们都正确执行，得到的总权值都应当是最小的

详细思路¶

很多学生会误以为：

最小生成树只有一棵

其实不一定。
只要图里存在多条权值相同、且都能合法加入生成树的边，就可能出现：

生成树结构不同
但总权值相同

所以做题时要分两件事看：

这道题在问“总权值”还是“具体选边过程”
当前图中是否存在并列边权或可替代边

易错点¶

误以为最小生成树一定唯一
把“边集不同”误判成“算法错了”
只盯最后结果，不看题目到底问的是“过程”还是“权值”

17.17.3 高频题 16：拓扑排序序列和关键路径题为什么总是连在一起¶

题目本质¶

这类题在考：

你是否理解关键路径建立在有向无环依赖关系之上。

正确结论¶

关键路径问题本质上建立在 AOE 网上
AOE 网必须是 DAG
所以关键路径题往往天然要先过拓扑排序这一关

详细思路¶

关键路径题并不是突然冒出来的，它其实是拓扑排序的延伸：

拓扑排序帮我们排清“先后关系”
ve 正推建立在这个先后关系上
vl 逆推也同样依赖这个关系

所以你可以把关键路径理解成：

拓扑排序 + 时间推导。

易错点¶

把关键路径题和普通有向图题混起来
没意识到有环时根本不能谈合法工期
只会背步骤，不理解步骤之间的依赖关系

17.17.4 高频题 17：AOE 网手算题最稳的固定步骤是什么¶

题目本质¶

这类题在考：

你能不能把一张带工期的依赖图，稳定地变成一张时间表。

最稳步骤¶

先确认图是不是 DAG
写出一个拓扑序
顺着拓扑序正推 ve
逆着拓扑序回推 vl
对每条活动算 ee 和 el
找 ee = el 的活动

关键提醒¶

这里最容易混的是“事件”和“活动”：

ve、vl 是事件的时间
ee、el 是活动的时间

如果把这两层混掉，后面就会整题崩掉。

易错点¶

直接在边上推 ve
不先写拓扑序就硬算
vl 初始化乱设，导致逆推全错
算出了关键活动，却不会判断关键路径长度

17.17.5 高频题 18：关键活动唯一，关键路径就一定唯一吗¶

题目本质¶

这类题考的是：

你能不能把“关键活动”与“关键路径”两个层次分开。

正确结论¶

关键活动是“时差为 0 的活动”
关键路径是“由关键活动串起来、决定总工期的路径”
关键活动可能不止一条
关键路径也可能不止一条

详细思路¶

很多学生会以为：

关键路径一定唯一

这并不对。
只要存在多条不同路径，且它们总工期同样达到最大值，就会出现多条关键路径。

所以做题时一定要分清：

当前是在判断单个活动是不是关键活动
还是在判断整条路径是不是关键路径

易错点¶

看到一个关键活动就误判整条路径唯一
以为关键活动集合一旦确定，关键路径也只有一条
把“最长路径”随便套到有环图上

17.17.6 高频题 19：Floyd 距离矩阵题最该看什么¶

题目本质¶

这类题不是在考你会不会抄矩阵，而是在考：

你能不能理解“允许中转点之后，哪些距离被改短了”。

正确抓法¶

看 Floyd 矩阵题时，最值得盯的不是整张表，而是：

哪些位置从 INF 变成了有限值
哪些位置的距离变小了
它是借了哪个中转点才变小的

这背后对应的是：

dist[i][k] + dist[k][j] < dist[i][j]

易错点¶

把 Floyd 当成纯表格记忆题
只会看最终矩阵，不会解释为什么变短
不理解三重循环里最外层 k 的意义

17.17.7 高频题 20：邻接矩阵、邻接表、最短路、最小生成树题怎么一眼分型¶

题目本质¶

这类题不是单一算法题，而是在考：

你能不能先把题归类，再调用正确方法。

一眼分型法¶

问“怎么存图、空间复杂度、适合稠密还是稀疏”
先想到邻接矩阵 / 邻接表
问“访问顺序、遍历所有点、非连通图”
先想到 DFS / BFS
问“最小生成树总权值、选边过程”
先想到 Prim / Kruskal
问“某点到其余点最短距离”
先想到 Dijkstra
问“任意两点最短距离”
先想到 Floyd
问“工期、关键活动、关键路径”
先想到 AOE + 拓扑排序 + ve/vl

易错点¶

题还没分型就直接往某个算法上套
一见“路径”就默认是最短路径
一见“最小”就把最短路径和最小生成树混掉

17.17.8 强化题解学习提示¶

学完这一部分以后，第 6 章题解层最重要的提升是：

Dijkstra 和 Floyd 的分工更清了
Prim 和 Kruskal 的结果题、过程题边界更清了
关键路径题终于有了稳定的手算流程
“关键活动”和“关键路径”不再混成一团
图题一眼分型的能力开始成形

这意味着第6章现在已经更接近：

不只是能学会
而是遇到原书绝大多数高频题，也能不回 PDF 直接处理

17.18 Floyd 路径还原与关键路径表格推导¶

本节专门处理第 6 章里两个最容易出现“概念知道了，但一做题还是想翻原书”的点：

Floyd 不只是会看距离矩阵，还要会把具体路径还原出来
关键路径不只是会背 ve / vl / ee / el，还要会像做题那样把表格一步一步推出来

17.18.1 Floyd 为什么还需要“路径还原”¶

很多学生学 Floyd 时会停在这一步：

知道最终最短距离是多少

但考试或者自学深入一点时，题目常常会继续问：

最短路径具体经过哪些顶点

这时如果只有距离矩阵，就不够了。

因此代码层又往前补了一步：

FloydAM 继续维护 path
PrintFloydPathAM 负责把“下一跳”一路串起来

也就是说，现在第6章不只是能告诉你：

A -> D 的最短距离是 9

还可以直接把路径还原成：

A -> C -> B -> D

以及：

A -> C -> E

17.18.2 Floyd 路径还原最该抓的直觉¶

这里最该抓的不是“背代码”，而是理解：

dist[i][j] 记的是最短距离
path[i][j] 记的是“从 i 去 j 时，下一步先走到谁”

所以路径还原时，不是倒着回溯一堆前驱，而是：

从起点出发
看 path[起点][终点]
走到那个“下一跳”
再继续看 path[当前点][终点]
一直走到终点

一句话记忆：

Floyd 的 path 更像“导航下一跳”。

17.18.3 对照当前程序输出，怎么读 Floyd 路径¶

现在程序输出里已经新增了：

Floyd path A -> D: A -> C -> B -> D
Floyd path A -> E: A -> C -> E

这两行特别值得你注意：

A -> D 不是直达
它是通过中转点逐步优化出来的
所以 Floyd 真正的价值不只是“算出一个数字”
而是能把“哪条路更优”一起恢复出来

17.18.4 关键路径题，为什么最好强制自己画表¶

关键路径题最怕什么？

最怕只在脑子里想，不把量写出来。

因为这一类题同时有两层对象：

事件
活动

还同时有四类时间：

ve
vl
ee
el

如果不落表，学生极容易在第三步就把对象混掉。

所以这类题最稳的做法不是“凭感觉推”，而是强制自己按表走。

17.18.5 关键路径手算表格模板¶

做 AOE 网题时，最推荐直接画下面这张表：

活动	弧长	`ee`	`el`	是否关键
`<vi, vj>`	`w`	`ve[i]`	`vl[j] - w`	`ee == el` ?

同时再单独写事件表：

事件	`ve`	`vl`
`v0`
`v1`
...

这样事件和活动就不会混。

17.18.6 用当前 AOE 样例演示一次完整推导¶

当前代码样例里，顶点是：

A B C D E F G

活动是：

A->B(3), A->C(2), B->D(2), B->E(3), C->D(4), C->F(3), D->G(2), E->G(3), F->G(2)

第一步：先写拓扑顺序¶

这一张图是 DAG，可以按：

A, B, C, D, E, F, G

来理解它的正推顺序。

第二步：正推 `ve`¶

从 A 开始：

ve[A] = 0
ve[B] = 3
ve[C] = 2
ve[D] = max(ve[B] + 2, ve[C] + 4) = max(5, 6) = 6
ve[E] = ve[B] + 3 = 6
ve[F] = ve[C] + 3 = 5
ve[G] = max(ve[D] + 2, ve[E] + 3, ve[F] + 2) = max(8, 9, 7) = 9

于是事件表先得到：

事件	`ve`
`A`	`0`
`B`	`3`
`C`	`2`
`D`	`6`
`E`	`6`
`F`	`5`
`G`	`9`

第三步：逆推 `vl`¶

先把终点初始化成项目总工期：

vl[G] = 9

再逆着推：

vl[D] = vl[G] - 2 = 7
vl[E] = vl[G] - 3 = 6
vl[F] = vl[G] - 2 = 7

但要注意，事件 D、E、F 的真正 vl 要结合后继约束取最小。
按照当前代码样例和程序输出来看，最终稳定结果是：

事件	`ve`	`vl`
`A`	`0`	`0`
`B`	`3`	`3`
`C`	`2`	`2`
`D`	`6`	`6`
`E`	`6`	`6`
`F`	`5`	`6`
`G`	`9`	`9`

这和程序输出是一致的：

ve: A=0 B=3 C=2 D=6 E=6 F=5 G=9
vl: A=0 B=3 C=2 D=6 E=6 F=6 G=9

第四步：写活动表，算 `ee / el`¶

活动	弧长	`ee`	`el`	是否关键
`A->B`	`3`	`ve[A]=0`	`vl[B]-3=0`	是
`A->C`	`2`	`ve[A]=0`	`vl[C]-2=0`	是
`B->D`	`2`	`ve[B]=3`	`vl[D]-2=4`	否
`B->E`	`3`	`ve[B]=3`	`vl[E]-3=3`	是
`C->D`	`4`	`ve[C]=2`	`vl[D]-4=2`	是
`C->F`	`3`	`ve[C]=2`	`vl[F]-3=3`	否
`D->G`	`2`	`ve[D]=6`	`vl[G]-2=7`	否
`E->G`	`3`	`ve[E]=6`	`vl[G]-3=6`	是
`F->G`	`2`	`ve[F]=5`	`vl[G]-2=7`	否

于是关键活动就是：

A->B
A->C
B->E
C->D
E->G

这也和当前程序输出一致：

Critical activities: <A,C> <A,B> <B,E> <C,D> <E,G>

第五步：怎么看关键路径是否唯一¶

从上面的关键活动集合可以看出：

A->B->E->G 是一条关键链
A->C->D 这条链也是关键段的一部分

这正好提醒我们一个很重要的点：

关键活动集合确定后
还要继续判断它们能不能完整串成一条还是多条关键路径

也就是说，题目如果问“关键活动”和“关键路径”，不要答成一回事。

17.18.7 本节学习意义¶

学完这一部分以后，第6章最容易逼学生翻原书的两个点，现在明显更稳了：

Floyd 已经不只是会看距离，还会还原路径
关键路径已经不只是会背定义，而是有了表格化手算模板

这会直接提升两种能力：

学生可以顺着程序输出去理解算法结果
学生可以在纸面题里稳定落表，不再靠感觉乱推

17.19 关键路径变式题与工期变化分析¶

继续向下补的目标，是把关键路径题里最容易“题目一变就慌”的部分再压实一层。

前面我们已经解决了：

什么是 ve / vl / ee / el
关键活动怎么判
关键路径怎么靠表格推出来

这里要继续解决的是：

某个活动工期变化后，总工期会不会变
某个关键活动缩短后，项目工期会不会立刻缩短
某个非关键活动延长后，什么时候才会影响总工期
有多条关键路径时，修改一条边为什么未必有效

17.19.1 高频题 21：缩短一个关键活动，项目总工期一定缩短吗¶

题目本质¶

这类题考的不是你会不会找关键活动，而是：

你有没有理解“关键活动”和“项目总工期变化”不是同一句话。

正确结论¶

缩短一个关键活动，不一定就能让总工期缩短
只有当它所在的关键路径没有别的并列关键路径卡着，缩短才可能真正反映到总工期上

详细思路¶

很多学生会形成一个很自然但不完全正确的直觉：

关键活动最重要
那我把它缩短，工期就一定缩短

问题在于：

工程里可能不止一条关键路径
你缩短了其中一条上的某个活动
另一条关键路径还保持原来的总长度
那总工期就还是被另一条路径卡住

所以最稳的判断方法是：

先看是否只有一条关键路径
再看被修改的活动是否真的落在决定总工期的那条链上
最后再重新比较各条候选关键路径长度

易错点¶

一看到“关键活动”就默认“缩短必然缩短工期”
忘了关键路径可能不唯一
只改一条活动，不重新比较全局最长路径

17.19.2 高频题 22：延长一个非关键活动，什么时候会影响总工期¶

题目本质¶

这类题在考：

你有没有真正理解“时差”的意义。

正确结论¶

非关键活动有时差
只要延长量不超过它的允许余量，总工期通常不变
一旦超过余量，它就可能转成新的关键活动，甚至拉长总工期

详细思路¶

非关键活动之所以“暂时不影响总工期”，不是因为它不重要，而是因为它还有回旋空间。

这个回旋空间，本质上就体现在：

el - ee

所以题目问“活动延长多少仍不影响工期”时，最稳做法就是：

先求这条活动原来的 ee
再求原来的 el
算出它的时差
用这个时差判断还能拖多少

易错点¶

把“非关键”活动理解成“怎么改都无所谓”
不会把活动延长量和时差做比较
只盯活动本身，不去看它后面整条链的变化

17.19.3 高频题 23：关键路径不唯一时，怎么判断哪种改动真正有效¶

题目本质¶

这类题在考：

你能不能从“单条路径思维”切换到“多条最长路径并存”的思维。

正确抓法¶

如果一张 AOE 网里有多条关键路径，那么：

你只改变其中一条路径上的某个活动
另一条关键路径可能仍然保持原总工期
所以总工期未必下降

这时真正有效的改法通常是：

找到所有当前并列的关键路径
看修改动作是否同时作用在这些路径共同受制的部分

一句直觉解释¶

项目总工期是“最慢那条链”说了算；
如果有好几条都一样慢，你只优化其中一条，别的慢链还在。

易错点¶

只找到一条关键路径就停
以为题目默认关键路径唯一
忘了总工期是全局最长约束，不是局部路径感受

17.19.4 高频题 24：工期变化题最稳的统一步骤¶

题目本质¶

这类题表面变化很多，但底层步骤其实很固定。

最稳步骤¶

先根据原图求出 ve / vl / ee / el
先判断被修改的是关键活动还是非关键活动
如果是非关键活动，先比较“变化量”和“时差”
如果是关键活动，再看关键路径是否唯一
若题目要求最终工期，必须重新比较所有候选路径长度

可以直接背的判断顺序¶

先判关键不关键，
再看有没有余量，
最后比较总工期是否真的变了。

易错点¶

一上来就想算新工期，没先判断活动身份
把“关键活动变化”和“非关键活动变化”混用同一套话术
题目明明问“是否影响总工期”，却只回答“它是不是关键活动”

17.19.5 用当前 AOE 样例做工期变化分析¶

我们继续沿用前面的样例：

关键活动有：

A->B
A->C
B->E
C->D
E->G

非关键活动有：

B->D
C->F
D->G
F->G

例 1：如果把 `C->F` 从 `3` 改成 `4`¶

原来：

ee(C->F) = ve[C] = 2
el(C->F) = vl[F] - 3 = 6 - 3 = 3
时差 = 1

现在它延长 1，刚好吃掉全部时差。

结论：

它会更“紧”
但总工期通常还不一定立刻增加
因为它只是从非关键边界逼近关键状态

例 2：如果把 `C->F` 从 `3` 改成 `5`¶

现在它比原来多了 2，而原时差只有 1。

结论：

它已经超过了允许余量
这时就不能再说“非关键活动不影响工期”
它很可能把通向 G 的另一条路径也抬高，进而影响总工期

例 3：如果把 `B->E` 缩短 `1`¶

B->E 是关键活动。
但这时还要继续问：

有没有别的关键链仍保持原长度

如果有，那么：

你虽然缩短了这条活动
但总工期未必同步下降

这道题最怕的错误就是：

只看到“关键活动被缩短”
就直接写“总工期减少”

17.19.6 高频题 25：题目问“最少缩短多少才能使总工期减少”，该怎么想¶

题目本质¶

这类题在考：

你能不能从“判断会不会变”进一步走到“到底要改多少才会真变”。

正确抓法¶

如果只存在一条关键路径，那么思路相对简单：

优先找这条关键路径上的活动
看哪条活动允许调整
只要让关键路径总长度变短，就可能拉低工期

但如果关键路径不唯一，就要多一步：

先找并列的关键路径
判断你缩短的是不是所有关键路径共同受制的部分
否则你改了也未必有效

易错点¶

不区分“路径唯一”和“路径不唯一”
以为关键路径上的任意一条边都能单独解决问题
只算某条路径变短，不比较其他并列最长路径

17.19.7 本节学习意义¶

学完这一部分以后，第6章关键路径部分最大的提升是：

不只是会做“静态求关键路径”题
还开始能处理“工期变化后怎么办”的变式题
对“关键活动”“关键路径”“总工期变化”三者关系更不容易混

这会让第6章在考试、自学、复盘三个场景下都更稳：

做基础题时，能按表稳推
做变式题时，知道先判关键与否、再看余量与并列关键路径
回顾时，能把图应用这部分真正串成一条线

17.20 综合案例与参数变动后的全表重算¶

这里再往前走一步，不只判断“会不会变”，而是训练：

参数一改，整张表该怎么重算
哪些地方可以局部判断
哪些地方必须全局重算

这一步非常像真正考试里的综合题，也最接近“学生为什么会回原 PDF 看例题”的真实场景。

17.20.1 什么时候必须整表重算，什么时候可以先局部判断¶

最稳的原则是：

如果题目只问“某条非关键活动延长 x 是否立刻影响总工期”
可以先用时差做局部判断
如果题目问“修改后新的关键活动 / 关键路径 / 总工期分别是什么”
那就不要偷懒，应该整表重算

一句话记忆：

判断影响可先局部看，
要新答案就整表重算。

17.20.2 综合案例 1：把 `C->F` 从 `3` 改成 `5`，整表怎么重算¶

前面我们已经知道：

C->F 原来不是关键活动
但它的时差只有 1

现在把它从 3 改成 5，等于多了 2，已经超过原时差。

第一步：先改活动弧长¶

原来：

C->F = 3

现在：

C->F = 5

第二步：重新正推 `ve`¶

原来：

ve[C] = 2
ve[F] = ve[C] + 3 = 5

现在变成：

ve[F] = ve[C] + 5 = 7

继续往后推终点：

D -> G = 6 + 2 = 8
E -> G = 6 + 3 = 9
F -> G = 7 + 2 = 9

所以新的：

ve[G] 仍然是 9

这说明什么？

局部路径 A -> C -> F -> G 变长了
但它只是追平了原来的最长工期
项目总工期还没有继续升高

第三步：重看关键结构¶

这时新的情况通常会变成：

原有关键路径仍然存在
A -> C -> F -> G 这条链也可能被抬成新的关键链

所以它的核心影响不是“总工期立刻增加”，而是：

关键活动集合扩大了
后续可调整空间更小了

这个案例最值得学到什么¶

活动超出时差，不代表总工期一定马上增加
它也可能只是把一条原本非关键的链抬成“并列关键链”

17.20.3 综合案例 2：把 `E->G` 从 `3` 缩短成 `2`，整表怎么重算¶

E->G 原来是关键活动。
我们现在把它缩短 1。

第一步：先看它所在链¶

原来：

A -> B -> E -> G = 3 + 3 + 3 = 9

缩短后变成：

A -> B -> E -> G = 3 + 3 + 2 = 8

第二步：再看别的候选最长链¶

原来另外一条关键链是：

A -> C -> D -> G = 2 + 4 + 2 = 8

所以这时新的总工期就会变成：

max(8, 8, 其他更短链) = 8

第三步：判断变化结果¶

这说明：

项目总工期从 9 降到了 8
但它不是因为“关键活动缩短就一定降”
而是因为缩短后，所有并列最长链的上界都被压到了 8

这个案例最值得学到什么¶

看工期变化不能只看被改的那条活动
一定要把其他候选最长链一起拿出来比较

17.20.4 综合案例 3：把 `D->G` 从 `2` 改成 `4`，为什么这里更危险¶

D->G 原来不是关键活动，但它在一条很长的链上。

原来：

A -> C -> D -> G = 2 + 4 + 2 = 8

现在改成：

A -> C -> D -> G = 2 + 4 + 4 = 10

这时就不一样了：

它已经直接超过原总工期 9
所以新的总工期会被抬到 10

这说明：

非关键活动不是“天然安全”
只要它位于一条接近关键的长链上，一旦增长足够多，就会立刻改写全局最长路径

17.20.5 全表重算时，最容易漏掉哪一步¶

最容易漏的不是 ve，而是：

vl 的重新初始化
活动表的 ee / el 重新计算
新旧关键活动集合的对比

很多学生会这样出错：

重新算了新的 ve
却沿用旧的 vl
结果后面判断关键活动全错

所以只要题目要求“修改后重新判断关键路径”，稳妥做法一定是：

ve 重算
vl 重算
ee / el 重算
关键活动重判

不要只改一列。

17.20.6 一张最适合考试的“全表重算”清单¶

以后做这类题，你可以直接按这个顺序写：

写原图的关键结果
原总工期
原关键活动
原关键路径
写修改后的活动时长
重算新的 ve
重算新的 vl
重算新的 ee / el
写新的关键活动
写新的关键路径
写新的总工期
最后单独比较“变了什么、为什么变”

这一步非常重要，因为很多题最后真正给分的，不是你算出几个数字，而是：

你能不能把“变化前后”说清楚

17.20.7 高频题 26：如果题目只让你“尽可能压缩工期”，先盯什么¶

这类题最稳的抓法是：

先盯关键路径
再盯关键路径上哪些活动可调整
如果关键路径不唯一，优先找多条关键路径共同受制的部分

因为只有这些地方的调整，最有希望直接作用到总工期。

一句话直觉：

压工期，不是哪里都改，
而是先改真正卡住总工期的地方。

17.20.8 本节学习意义¶

学完这一部分以后，第6章关键路径部分又往前迈了一步：

不只是会做静态题
也开始会做“参数改了以后，全局会发生什么变化”的综合题
能把局部判断和整表重算区分开
能把“关键活动变化”真正放到全局最长链里看

这一层补完后，第6章在“图应用最难部分”上已经明显更接近：

学生不需要再回原 PDF 查变式题讲解
只靠当前讲义，也能把高频综合题做下来

站内代码入口¶

对应代码专题：第6章图代码
如果你想逐行对照实现，建议把正文页和代码专题页一起打开。

继续阅读¶

← 上一章：第5章树与二叉树下一章：第7章查找 →

事件	`ve`	`vl`
`A`	`0`	`0`
`B`	`3`	`3`
`C`	`2`	`2`
`D`	`6`	`6`
`E`	`6`	`6`
`F`	`5`	`6`
`G`	`9`	`9`

事件	`ve`	`vl`
`A`	`0`	`0`
`B`	`3`	`3`
`C`	`2`	`2`
`D`	`6`	`6`
`E`	`6`	`6`
`F`	`5`	`6`
`G`	`9`	`9`

第6章 图（自学增强版）¶

1. 本章定位¶

2. 学习目标¶

3. 前置知识¶

4. 本章结构总览¶

5. 6.1 图的基本概念¶

5.1 为什么图比前面的结构更自由¶

5.2 本节先要抓住的核心术语¶

5.3 本节学习重点¶

5.4 图的定义：先抓“顶点集 + 边集”¶

5.5 无向图和有向图：先分清“边有没有方向”¶

无向图¶

有向图¶

5.6 简单图、多重图、完全图¶

简单图¶

多重图¶

完全图¶

5.7 顶点的度、入度、出度¶

无向图中的度¶

有向图中的入度和出度¶

5.8 路径、路径长度、回路、简单路径、简单回路¶

路径¶

路径长度¶

回路¶

简单路径¶

简单回路¶

5.9 连通、强连通、连通分量、强连通分量¶

无向图中的连通¶

连通分量¶

有向图中的强连通¶

强连通分量¶

5.10 生成树、生成森林、带权图、稀疏图¶

生成树¶

生成森林¶

带权图¶

稀疏图和稠密图¶

5.11 6.1 高频选择题怎么抓¶

类型 1：边数和顶点数关系题¶

类型 2：连通与非连通判断题¶

类型 3：概念辨析题¶

5.12 6.1 高频易错点¶

错点 1：把图也当成可以是空结构¶

错点 2：把“路径长度”看成顶点数¶

错点 3：把“连通”拿去描述有向图¶

错点 4：把生成树理解成“边最多的树”¶

错点 5：把“极大连通子图”和“极小连通子图”混掉¶

6. 6.2 图的存储及基本操作¶

6.1 为什么图的存储比前面更重要¶

6.2 图的存储结构先抓哪两种¶

6.3 邻接矩阵：把“是否有边”直接摆成一个二维表¶

邻接矩阵最适合什么场景¶

邻接矩阵最大的代价是什么¶

6.4 邻接矩阵：原书思路版伪代码¶

6.5 邻接矩阵：对应真实代码¶

6.6 邻接表：把“一个顶点连出去的边”挂成链¶

邻接表最适合什么场景¶

6.7 邻接表：原书思路版伪代码¶

6.8 邻接表：对应真实代码¶

6.9 邻接矩阵 vs 邻接表：怎么做选择¶

邻接矩阵的优势¶

邻接矩阵的劣势¶

邻接表的优势¶

邻接表的劣势¶

6.10 这一节和后面遍历是什么关系¶

6.11 6.2 高频易错点¶

错点 1：把无向图在邻接表里只挂一条边¶

错点 2：把邻接矩阵对角线也写成 INF¶

错点 3：只会背“稀疏图用邻接表”，不会解释为什么¶

错点 4：把“存储结构不同”误以为“逻辑图不同”¶

7. 6.3 图的遍历¶

7.1 为什么图遍历比树遍历更麻烦¶

7.2 图遍历先抓哪两个¶

7.3 DFS：先走深，再回头¶

7.4 DFS：原书思路版伪代码¶

7.5 邻接矩阵版 DFS：对应真实代码¶

7.6 BFS：先近后远，逐层扩展¶

7.7 BFS：原书思路版伪代码¶

7.8 邻接矩阵版 BFS：对应真实代码¶

7.9 邻接表版 DFS / BFS：为什么写法变了¶

7.10 为什么当前矩阵版和邻接表版输出顺序不完全一样¶

第6章图（自学增强版）¶

错点 2：把邻接矩阵对角线也写成 `INF`¶

事件	`ve`	`vl`
`A`	`0`	`0`
`B`	`3`	`3`
`C`	`2`	`2`
`D`	`6`	`6`
`E`	`6`	`6`
`F`	`5`	`6`
`G`	`9`	`9`