第6章图

2027 王道 · 专题阅读 · 保留代码与校订注 · 与版本锁一致

第6章图¶

⚠️ 图算法整体难度较大，重点掌握深度优先搜索与广度优先搜索。 要掌握邻接矩阵、邻接表、邻接多重表、十字链表及其特点并能相互转换，以及拓扑排序、最小生成树、最短路径、关键路径。 💡 教材定调：图算法较多，通常只需掌握核心思想与实现步骤，代码实现并非重点。

回源 · PDF 第 206 页 · b_206_5

【知识树】第6章骨架¶

基本概念：有向/无向、度、路径、连通性、生成树、完全图、稠密稀疏图
存储结构：邻接矩阵、邻接表、十字链表、邻接多重表
遍历：DFS、BFS（及生成树/生成森林）
应用
最小生成树：Prim、Kruskal
最短路径：BFS（无权）、Dijkstra、Floyd
拓扑排序（AOV 网）
关键路径（AOE 网）

回源 · PDF 第 206 页 · b_206_0；PDF 第 206 页 · b_206_2

6.1 图的基本概念¶

图可以是空图吗？¶

⚠️ 不可以。 线性表可以是空表，树可以是空树，但图不可以是空图 —— 顶点集 V 必须非空，⚠️ 但边集 E 可以为空（此时只有顶点而无边）。

图 G = (V, E)，|V| 是顶点数，|E| 是边数。

回源 · PDF 第 206 页 · b_206_4；PDF 第 206 页 · b_206_8

有向边和无向边怎么记？¶

有向图：弧是顶点的有序对，记为 ；⚠️ v 是弧尾，w 是弧头，表示从 v 到 w，也称 v 邻接到 w
无向图：边是顶点的无序对，记为 (v, w) 或 (w, v)；w 和 v 互为邻接点

💡 记忆法：尖括号有向，圆括号无向；尾在前、头在后。

回源 · PDF 第 207 页 · b_207_3；PDF 第 207 页 · b_207_4

简单图的两个条件？¶

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

多重图：两顶点间边数超过 1 条，或允许顶点通过一条边与自身关联。 ⚠️ 本书仅讨论简单图。

回源 · PDF 第 207 页 · b_207_13

度、入度、出度的两条求和关系？　★2考¶

无向图：TD(v) = 依附于 v 的边数；⚠️ 全部顶点的度之和 = 边数的 2 倍（每条边关联两个顶点）
有向图：ID(v) 入度、OD(v) 出度，TD(v) = ID(v) + OD(v)；⚠️ 全部顶点的入度之和 = 出度之和 = 边数

★ 考过 2009、2017

回源 · PDF 第 207 页 · b_207_16

简单路径和简单回路的区别？　★1考¶

路径长度 = 路径所含边的数量
回路（环） = 第一个顶点和最后一个顶点相同的路径
简单路径 = ⚠️ 顶点不重复出现的路径
简单回路 = ⚠️ 除第一个和最后一个顶点外，其余顶点不重复的回路
距离 = u 到 v 的最短路径长度；⚠️ 不存在路径则距离为无穷大

⚠️ 重要结论：若一个图有 n 个顶点且边数大于 n − 1，则此图一定有环。

★ 考过 2011

回源 · PDF 第 208 页 · b_208_3

子图和生成子图怎么判断？¶

设 \(G=(V,E)\)、\(G'=(V',E')\)： - 若 \(V'\subseteq V\) 且 \(E'\subseteq E\)，并且 \(E'\) 中每条边的关联顶点都在 \(V'\) 中，则称 \(G'\) 是 \(G\) 的子图 - 若子图还满足 \(V'=V\)，即保留原图全部顶点，只选取部分边，则称 生成子图

⚠️ 不能把顶点集和边集任意各取一个子集就说成子图：若选中的某条边所关联的顶点没有同时选入 \(V'\)，所得对象连图都不是。

回源 · PDF 第 208 页 · b_208_7；PDF 第 208 页 · b_208_8；PDF 第 208 页 · b_208_9；PDF 第 208 页 · b_208_10

连通分量和强连通分量的定义？　★2考¶

无向图：v 到 w 存在路径则连通；任意两顶点都连通 → 连通图；⚠️ 极大连通子图称为连通分量
有向图：v 到 w 和 w 到 v 都有路径 → 强连通；任意一对顶点都强连通 → 强连通图；⚠️ 极大强连通子图称为强连通分量

⚠️ 在无向图中讨论连通性，在有向图中讨论强连通性。

两个必背结论： - ⚠️ n 个顶点的无向图若边数少于 n − 1，则必然是非连通的 - ⚠️ 非连通图边数最多的情形：n−1 个顶点构成完全图，再加一个孤立顶点 → 最多 (n−1)(n−2)/2 条边 - ⚠️ n 个顶点的有向图要强连通，最少需要 n 条边（构成一个环）

★ 考过 2010、2022

回源 · PDF 第 208 页 · b_208_12

极大连通子图和极小连通子图有什么区别？¶

极大连通子图（连通分量）：⚠️ 子图必须连通，且包含尽可能多的顶点和边
极小连通子图（生成树）：⚠️ 既保持连通又使边数最少

生成树：包含所有顶点的极小连通子图，⚠️ 恰好含 n − 1 条边。 - ⚠️ 移除任意一条边 → 变成非连通图；添加任何一条边 → 形成回路 - 非连通图中，每个连通分量的生成树共同构成生成森林

回源 · PDF 第 209 页 · b_209_3

完全图的边数和稀疏图的判据？¶

无向图：|E| 范围 0 ~ n(n−1)/2；⚠️ 达到 n(n−1)/2 时称为完全图
有向图：|E| 范围 0 ~ n(n−1)；⚠️ 有 n(n−1) 条弧时称为有向完全图（任意两顶点间有方向相反的两条弧）
⚠️ 稀疏图的一般判据：|E| < |V|log₂|V|

其他术语：权、带权图（网）、带权路径长度；⚠️ 有向树 = 一个顶点入度为 0、其余顶点入度均为 1 的有向图。

回源 · PDF 第 209 页 · b_209_13；PDF 第 209 页 · b_209_14

6.2 图的存储¶

邻接矩阵怎么表示带权图？　★3考¶

不带权：A[i][j] = 1（有边）或 0（无边）
带权：A[i][j] = w_ij（有边）或 0 / ∞（无边）

/**/ #define MaxVertexNum 100
typedef struct{
    VertexType vex[MaxVertexNum];                    // 顶点表
    EdgeType edge[MaxVertexNum][MaxVertexNum];       // 邻接矩阵（边表）
    int vexnum, arcnum;
} MGraph;

⚠️ 空间复杂度 O(n²)，与边数无关。

★ 考过 2011、2015、2018

回源 · PDF 第 214 页 · b_214_0

邻接矩阵怎么求度？　★4考¶

⚠️ 无向图：第 i 行（或第 i 列）非零元素的个数 = TD(vᵢ)
⚠️ 有向图：第 i 行非零元素个数 = 出度 OD(vᵢ)；第 i 列非零元素个数 = 入度 ID(vᵢ)

💡 记忆法："行出列入"。

★ 考过 2013、2021、2023

回源 · PDF 第 214 页 · b_214_14

邻接矩阵的六条特点？　★1考¶

⚠️ 无向图的邻接矩阵一定是对称矩阵 → 只需存上（或下）三角；顶点编号固定时邻接矩阵唯一
无向图第 i 行/列非零元素个数 = 度
有向图行数出度、列数入度
⚠️ 很容易判断两顶点间是否有边，但要数出总边数需遍历整个矩阵，代价大
⚠️ 稠密图更适合邻接矩阵
⚠️ Aⁿ[i][j] 表示从顶点 i 到顶点 j 长度为 n 的路径数量

★ 考过 2015、2021

回源 · PDF 第 215 页 · b_215_3

邻接表的两种结点结构？　★1考¶

顶点表结点：data（顶点信息）| firstarc（指向第一条依附该顶点的弧）
边表结点：adjvex（该弧所指向的顶点位置）| nextarc（指向下一条弧）| [info（权值）]

⚠️ 第 i 个单链表称为顶点 vᵢ 的边表（有向图中称出边表），存的是依附于 vᵢ 的边（有向图中是以 vᵢ 为尾的弧）。

typedef struct VNode{
    VertexType data;
    ArcNode *firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct{ AdjList vertices; int vexnum, arcnum; }ALGraph;

★ 考过 2014

回源 · PDF 第 215 页 · b_215_11

邻接表的五条特点？　★1考¶

⚠️ 空间复杂度：无向图 O(|V| + 2|E|)，有向图 O(|V| + |E|) —— 无向图带系数 2 是因为每条边在邻接表中出现两次
⚠️ 稀疏图用邻接表能极大节省空间
⚠️ 查某顶点的所有邻接点：邻接表只需遍历对应边表（快）；判断两顶点之间是否有边：邻接矩阵 O(1) 直接访问（快），邻接表需线性查找（慢）
⚠️ 求度：无向图 = 边表结点个数；有向图出度 = 边表结点个数，入度必须遍历所有顶点的边表，统计 adjvex 等于该顶点编号的结点数
⚠️ 邻接表的表示不唯一 —— 取决于建表算法及输入边的次序

★ 考过 2011

回源 · PDF 第 216 页 · b_216_4

十字链表的两种结点各有几个域？¶

⚠️ 弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上 → 既容易找到以 vᵢ 为尾的弧，也容易找到以 vᵢ 为头的弧 → 很容易求出度和入度。 ⚠️ 顶点结点之间是顺序存储的；十字链表的表示形式不唯一。

💡 记忆法："h 管头、t 管尾"，firstin 找入边、firstout 找出边。

回源 · PDF 第 216 页 · b_216_9；PDF 第 216 页 · b_216_10

邻接多重表解决了邻接表的什么问题？　★1考¶

⚠️ 邻接多重表是无向图的链式存储结构。 问题：邻接表判断两顶点间是否存在边时要分别遍历两个顶点的边表，效率低；且删除边时要在两个链表里各删一次。

⚠️ 核心区别：邻接表用两个结点表示同一条无向边，邻接多重表仅用一个；每条边的结点同时链接在两个链表中。

★ 考过 2024

回源 · PDF 第 217 页 · b_217_13

四种存储方式的总对照？¶

	邻接矩阵	邻接表	十字链表	邻接多重表
空间复杂度	O(\|V\|²)	无向 O(\|V\|+2\|E\|)；有向 O(\|V\|+\|E\|)	O(\|V\|+\|E\|)	O(\|V\|+\|E\|)
找相邻边	遍历对应行或列，O(\|V\|)	⚠️ 找有向图入度必须遍历整个邻接表	很方便	很方便
删除边或顶点	删边方便，删顶点要大量移动数据	⚠️ 无向图中删边或删顶点都不方便	很方便	很方便
适用于	稠密图	稀疏图和其他	⚠️ 只能存有向图	⚠️ 只能存无向图
表示方式	⚠️ 唯一	不唯一	不唯一	不唯一

回源 · PDF 第 218 页 · b_218_0

图的十个基本操作分别解决什么问题？¶

图的基本操作在逻辑上独立于存储结构，但其具体实现和效率取决于邻接矩阵、邻接表等实际存储方式。

Adjacent(G,x,y)：判断 x、y 之间是否有边
Neighbors(G,x)：列出 x 的全部邻接点
InsertVertex / DeleteVertex：插入顶点；删除顶点及其关联边
AddEdge / RemoveEdge：添加或删除边
FirstNeighbor(G,x)：返回 x 的第一个邻接点；没有则返回 −1
NextNeighbor(G,x,y)：已知 y 是 x 的邻接点，返回 y 之后的下一个邻接点；没有则返回 −1
Get_edge_value / Set_edge_value：读取或设置边的权值

⚠️ 写遍历算法时最常用的是 FirstNeighbor + NextNeighbor；分析复杂度时必须再结合存储结构，不能只看抽象操作名。

回源 · PDF 第 218 页 · b_218_2；PDF 第 218 页 · b_218_3；PDF 第 218 页 · b_218_4；PDF 第 218 页 · b_218_5；PDF 第 218 页 · b_218_6

6.3 图的遍历¶

BFS 的基本思想为什么需要队列？¶

BFS 类似树的层序遍历：从起点 v 出发，先访问所有距离为 1 的未访问邻接点，再访问距离为 2、3、……的顶点，即按从近到远、逐层扩展的顺序访问。

⚠️ 当前层访问到的新顶点必须按发现顺序暂存，待当前层处理完后再依次扩展，所以要用队列；BFS 通常采用非递归实现，不沿已访问路径回溯。

若一次 BFS 后仍有未访问顶点，说明图不连通；应另选未访问顶点作为新起点，直到全部顶点都被访问。

回源 · PDF 第 226 页 · b_226_8；PDF 第 226 页 · b_226_9；PDF 第 226 页 · b_226_10

BFS 的遍历控制器和邻接表模板怎么写？¶

void BFSTraverse(ALGraph G) {
    for (int i = 0; i < G.vexnum; ++i) visited[i] = false;
    InitQueue(Q);
    for (int i = 0; i < G.vexnum; ++i)
        if (!visited[i]) BFS(G, i);       // 每个连通分量调用一次
}

void BFS(ALGraph G, int i) {
    visit(i); visited[i] = true; EnQueue(Q, i);
    while (!QueueEmpty(Q)) {
        int v; DeQueue(Q, v);
        for (ArcNode *p = G.vertices[v].firstarc; p; p = p->nextarc) {
            int w = p->adjvex;
            if (!visited[w]) {
                visit(w); visited[w] = true; EnQueue(Q, w);
            }
        }
    }
}

⚠️ 必须在入队时立刻标记已访问；若等到出队才标记，同一顶点可能被多个邻接点重复入队。

回源 · PDF 第 227 页 · b_227_0；PDF 第 227 页 · b_227_1；PDF 第 227 页 · b_227_2；PDF 第 227 页 · b_227_3

BFS 在邻接表和邻接矩阵上的复杂度分别是多少？　★1考¶

辅助队列：每个顶点至多入队一次，最坏空间复杂度 O(|V|)
邻接表：所有顶点访问一次，所有边表扫描一遍 → O(|V|+|E|)（无向边虽存两次，量级不变）
邻接矩阵：每访问一个顶点都要扫描一整行寻找邻接点 → O(|V|²)

⚠️ BFS 的访问原则不变，但时间复杂度由“怎样找邻接点”决定。

★ 考过 2012

回源 · PDF 第 228 页 · b_228_2；PDF 第 228 页 · b_228_3；PDF 第 228 页 · b_228_4；PDF 第 228 页 · b_228_5

为什么 BFS 能求无权图的单源最短路径？¶

无权图中，路径长度按边数计算。BFS 按距离从小到大逐层访问，因此某顶点第一次被访问时，从源点到它所经过的边数一定最少。

初始化：源点 d[u]=0，其余顶点 d[i]=∞。当从顶点 v 第一次发现未访问邻接点 w 时：

visited[w] = true;
d[w] = d[v] + 1;
EnQueue(Q, w);

⚠️ 这个结论只直接适用于各边等价的无权图；带权图不能只按 BFS 层数当作最短路权值。

回源 · PDF 第 228 页 · b_228_6；PDF 第 228 页 · b_228_7；PDF 第 228 页 · b_228_8；PDF 第 228 页 · b_228_9；PDF 第 228 页 · b_228_10

BFS 生成树什么时候唯一？¶

BFS 遍历实际经过的发现边与所有被访问顶点构成广度优先生成树。 - 邻接矩阵表示唯一；从同一源点出发、按固定顶点编号扫描时，生成树唯一 - 邻接表表示不唯一，边结点次序会改变邻接点的访问顺序，因此生成树可能不唯一

⚠️ “同一张图、同一起点”仍不必推出 BFS 序列或生成树唯一；还要看存储表示与邻接点访问次序。

回源 · PDF 第 228 页 · b_228_11；PDF 第 228 页 · b_228_12

DFS 的基本思想和递归实现？　★2考¶

⚠️ DFS 类似于树的先序遍历，遵循尽可能"深"地探索的策略。

思想：访问起始顶点 v → 访问 v 的一个未访问邻接顶点 w₁ → 再访问 w₁ 的未访问邻接顶点 w₂ … ⚠️ 无法继续时回退到上一顶点（递归返回），检查它是否还有未访问的邻接顶点。

void DFS(ALGraph G, int i) {
    visit(i);  visited[i] = TRUE;
    for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
        j = p->adjvex;
        if (visited[j] == FALSE) DFS(G, j);
    }
}

教材例（图 6.11）：遍历结果 abdehcfg。

★ 考过 2015、2016

回源 · PDF 第 229 页 · b_229_9

DFS / BFS 序列是唯一的吗？¶

⚠️ 基于邻接矩阵：邻接矩阵表示唯一 → 同一源点出发的 DFS 和 BFS 序列唯一，生成树也唯一
⚠️ 基于邻接表：边的输入顺序不同则邻接表不同 → DFS 和 BFS 序列可能不唯一，生成树也不唯一

💡 这是选择题高频陷阱，务必分清"基于什么存储结构"。

回源 · PDF 第 229 页 · b_229_12

遍历的时间复杂度由什么决定？¶

⚠️ 只取决于图的存储结构，与访问顺序无关（DFS 和 BFS 一样）： - 邻接矩阵：每个顶点要扫描整行找邻接点 → O(|V|²) - 邻接表：每个顶点和每条边都被访问常数次 → O(|V| + |E|)

⚠️ DFS 的空间复杂度：递归实现依赖递归工作栈，最坏递归深度可达 |V| → O(|V|)。

回源 · PDF 第 230 页 · b_230_0

调用 DFS 的次数和连通分量有什么关系？¶

⚠️ 对无向图：调用 BFS(G,i) 或 DFS(G,i) 的次数恰好等于该图的连通分量数 —— 因为每次调用都会遍历一个连通分量中的所有顶点。

⚠️ 对有向图不成立：仅当从初始顶点到每个顶点都存在路径时，一次遍历才能访问所有顶点；即使整个图是弱连通的，也可能包含非强连通分量，单次调用不一定能访问该子图的所有顶点。

💡 所以两个遍历主函数都要加外层 for 循环：从每个尚未访问的顶点出发启动一次新的遍历。

生成树/生成森林：⚠️ 连通图 → 一棵深度优先生成树；非连通图 → 每个连通分量一棵树，共同构成深度优先生成森林。

回源 · PDF 第 230 页 · b_230_7

6.4 图的应用¶

最小生成树的三条性质？　★2考¶

MST = 带权连通无向图中总权重最小的生成树。 - ⚠️ 有权值相同的边时 MST 可能不唯一；所有边权值互不相同时 MST 唯一；⚠️ 若 G 本身边数就等于顶点数减 1（本身是树），则 MST 就是它自己 - ⚠️ MST 可能不唯一，但所有 MST 的总权重相同且为最小值 - MST 的边数 = 顶点数 − 1

⚠️ 高频陷阱：MST 的总权值最小，但不保证任意两顶点间是最短路径 —— 教材例中 MST 里 A 到 C 长度为 5，而图中 A 到 C 的最短路径是 4。

★ 考过 2012、2017、2023

回源 · PDF 第 238 页 · b_238_5

所有 MST 算法依据的核心性质是什么？¶

⚠️ 设 U 是顶点集 V 的一个非空子集。若 (u, v) 是一条权值最小的边，其中 u ∈ U、v ∈ V − U，则 G 中必存在一棵包含边 (u, v) 的最小生成树。

通用框架：

T = NULL;
while T 未形成一棵生成树:
    找一条最小代价边 (u,v)，且加入 T 后不产生回路;
    T = T ∪ (u,v);

⚠️ Prim 和 Kruskal 都基于这个性质，都采用贪心策略。

回源 · PDF 第 238 页 · b_238_14

Prim 算法的执行过程？　★3考¶

⚠️ Prim 在执行过程上与求单源最短路径的 Dijkstra 较为相似 —— 都是"从已选集合向外挑最近的点"。

从图中任取一个顶点加入树 T
选择一个与当前 T 中顶点集合距离最近的顶点，把该顶点及其相连的最小权值边加入 T
⚠️ 每执行一次，T 中的顶点数和边数各增加 1
重复直到所有顶点都并入 T → 最终必含 n − 1 条边

💡 一句话：Prim 是"长树"，从一个点滚雪球；每次挑离树最近的点。

★ 考过 2015、2017、2018

回源 · PDF 第 239 页 · b_239_2

Kruskal 算法的执行过程和复杂度？　★3考¶

⚠️ Kruskal 按边的权值递增次序选边（与 Prim 从顶点扩展不同）。

初始 T = {V, {}}：包含全部 n 个顶点但不含任何边，每个顶点自成一个连通分量
按权值从小到大依次考察每条边：⚠️ 若该边连接的两顶点属于不同连通分量（可用并查集判断）则加入 T，否则舍弃
直到 E_T 包含 n − 1 条边

复杂度分析：边存在堆中，每次取最小权值边 O(log₂|E|)；并查集判断 O(α(|V|)) 可视为常数 → ⚠️ 总时间复杂度 O(|E| log₂|E|)，不依赖 |V|。

⚠️ 适用性对照：Prim 是 O(|V|²)、与边数无关 → 适合边稠密图；Kruskal 适合边稀疏但顶点较多的图。

💡 一句话：Prim 长树（挑点），Kruskal 挑边（合并森林）。

★ 考过 2015、2018、2020

回源 · PDF 第 239 页 · b_239_15

最短路径的最优子结构是什么？　★2考¶

⚠️ 两点间最短路径上的任意子路径，也是对应端点间的最短路径。

两类问题： - 单源最短路径 → Dijkstra（无权图可用 BFS） - 所有顶点对之间的最短路径 → Floyd

★ 考过 2009、2023

回源 · PDF 第 240 页 · b_240_11

Dijkstra 的三个辅助数组和四个步骤？　★4考¶

三个数组： - final[]：标记各顶点是否已找到最短路径（是否属于 S） - dist[]：源点到各顶点的当前最短路径长度；⚠️ 初始为直接边的权值，无边则为 ∞ - path[]：记录路径，算法结束后回溯重构完整路径

四步： - ① 初始化 S = {0}，dist[i] = arcs[0][i] - ② 从 V − S 中选出 dist[j] 最小的顶点 j 加入 S（⚠️ 此时 j 的最短路径已确定） - ③ 松弛：对 j 的每个邻接点 k，⚠️ 若 dist[j] + arcs[j][k] < dist[k] 则更新 dist[k] - ④ 重复 ②③ 共 n − 1 次

★ 考过 2012、2014、2016、2021

回源 · PDF 第 241 页 · b_241_1；PDF 第 241 页 · b_241_12

Dijkstra 教材例题的四轮结果？　★4考¶

图 6.17，从 v₁ 出发。初始 dist[2]=10, dist[3]=∞, dist[4]=∞, dist[5]=5。 - 第 1 轮：选 dist[5]=5 → S={1,5}；更新 dist[2]=8（1→5→2）, dist[3]=14, dist[4]=7 - 第 2 轮：选 dist[4]=7 → S={1,5,4}；更新 dist[3]=13（1→5→4→3） - 第 3 轮：选 dist[2]=8 → S={1,5,4,2}；更新 dist[3]=9（1→5→2→3） - 第 4 轮：选 dist[3]=9 → 全部入 S

⚠️ 注意 dist[3] 被更新了三次：∞ → 14 → 13 → 9 —— 这正是"每加入一个新顶点就可能发现更短路径"的体现。

★ 考过 2012、2014、2016、2021

回源 · PDF 第 242 页 · b_242_0

Dijkstra 为什么不能用于负权边？¶

⚠️ Dijkstra 基于贪心策略：顶点一旦被加入 S 就不再更新其最短路径。 若存在负权边，⚠️ 后续路径可能通过负权边"绕回"已确定的顶点从而发现更短路径，而 Dijkstra 无法察觉 → 结果错误。

复杂度：⚠️ 邻接矩阵 + 线性扫描 dist[] → O(|V|²)；改用带权邻接表虽能把松弛降到 O(|E|)，但找最小 dist 仍需 O(|V|)，总复杂度仍是 O(|V|²)。 ⚠️ 即使只求源点到某一个特定顶点的最短路径，最坏情况仍需处理所有顶点，复杂度不变。

回源 · PDF 第 242 页 · b_242_8

Dijkstra 和 Prim 有什么异同？¶

相同：流程与操作很相似，都基于贪心策略。 三点不同： - ⚠️ 目的不同：Dijkstra 构建单源点的最短路径树；Prim 构建最小生成树 - ⚠️ 思路不同：Prim 每次选权值最小的边接到已建生成树上；Dijkstra 每次找到源点距离最近且未归入集合的点，并以它为基础更新源点到其他所有顶点的距离 - ⚠️ 适用图不同：Prim 只能用于带权无向图；Dijkstra 可用于带权有向图或无向图

回源 · PDF 第 241 页 · b_241_10

Floyd 的递推公式和含义？¶

\[A^{(k)}[i][j] = \min\{A^{(k-1)}[i][j],\ A^{(k-1)}[i][k] + A^{(k-1)}[k][j]\}\]

⚠️ A^(k)[i][j] 表示从 vᵢ 到 vⱼ、中间顶点编号不超过 k 的最短路径长度。 - 初始 A^(−1)[i][j] = arcs[i][j]，⚠️ 对所有 i 令 A^(−1)[i][i] = 0 - 依次让 k = 0, 1, …, n−1 作为中间顶点 - n 次迭代后 A^(n−1)[i][j] 即为最短路径长度

教材算例（3 个顶点）： - 第 1 轮（以 v₀ 为中间点）：A[2][1] 由 ∞ → 11 - 第 2 轮（以 v₁ 为中间点）：A[0][2] 由 13 → 10 - 第 3 轮（以 v₂ 为中间点）：A[1][0] 由 10 → 9

⚠️ Floyd 的时间复杂度 O(|V|³)；代码只需一个三重循环，常数因子小，中等规模图上实际效率高。

回源 · PDF 第 243 页 · b_243_11

三种最短路径算法的适用性总表？¶

	BFS	Dijkstra	Floyd
用途	单源最短路径	单源最短路径	各顶点之间
无权图	适用	适用	适用
带权图	⚠️ 不适用	适用	适用
带负权值	不适用	⚠️ 不适用	⚠️ 适用
带负权回路	不适用	不适用	⚠️ 不适用
时间复杂度	O(\|V\|²) 或 O(\|V\|+\|E\|)	O(\|V\|²)	O(\|V\|³)

⚠️ Floyd 也适用于带权无向图 —— 只需把每条无向边视为两条方向相反、权值相同的有向边。 💡 也可以对每个顶点各跑一次 Dijkstra 求所有顶点对：|V| × O(|V|²) = O(|V|³)，与 Floyd 相同。

回源 · PDF 第 244 页 · b_244_0；PDF 第 244 页 · b_244_1

DAG 描述表达式比二叉树好在哪？　★1考¶

有向无环图（DAG）= 不含任何有向环路的有向图。

⚠️ 表示含公共子表达式的代数表达式时：二叉树会把重复出现的子结构分别存储，造成空间浪费；DAG 中公共子表达式只需存储一次，通过多个父结点的入边共享。

⚠️ 在表达式的 DAG 表示中，不会出现重复的操作数顶点。

★ 考过 2019

回源 · PDF 第 244 页 · b_244_5

拓扑排序的定义和三个步骤？　★5考¶

AOV 网：顶点表示活动的网络 —— 顶点是活动，有向边表示活动 Vᵢ 必须先于 Vⱼ；⚠️ 这种关系具有传递性，且任何活动不能成为自己的前驱或后继。

拓扑排序的两个条件：每个顶点恰好出现一次；若存在从 A 到 B 的路径，则 B 必须排在 A 之后。

三个步骤： - ① 选择一个没有前驱（入度为 0）的顶点并输出；⚠️ 可能有多个入度为 0 的顶点，随便选一个 → 拓扑序列可能不唯一 - ② 删除该顶点和所有以它为起点的有向边 - ③ 重复，直到 AOV 网为空，或找不到入度为 0 的顶点 —— ⚠️ 后一种情况表明有向图中必然存在环

教材例结果：{1, 2, 4, 3, 5}。

★ 考过 2010、2011、2014、2018、2021

回源 · PDF 第 245 页 · b_245_3

拓扑排序在两种存储下的复杂度？　★2考¶

⚠️ 因为输出每个顶点的同时还要删除以它为起点的边： - 邻接表存储 → O(|V| + |E|) - 邻接矩阵存储 → O(|V|²)

算法实现要点：用栈（或队列）存所有入度为 0 的顶点 → 出栈输出 → 把它指向的所有顶点入度减 1，减到 0 就入栈 → ⚠️ 最后若 count < G.vexnum 则说明有环，排序失败。

★ 考过 2016、2024

回源 · PDF 第 246 页 · b_246_1

怎么用 DFS 实现拓扑排序？　★1考¶

对 DAG 中任意两顶点 u、v： - u 是 v 的祖先 → 先访问 u 再递归访问 v，v 先完成回溯 → ⚠️ u 的结束时间大于 v 的结束时间 - u 是 v 的子孙 → v 的结束时间大于 u - 两者无路径 → 相对顺序任意

⚠️ 结论：把所有顶点按 DFS 结束时间降序排列，即得一个合法的拓扑排序序列。

逆拓扑排序：每次选出度为 0 的顶点输出，删除该顶点和所有以它为终点的边。

★ 考过 2020

回源 · PDF 第 246 页 · b_246_3

拓扑序列唯一的充要条件？　★2考¶

⚠️ 拓扑序列唯一的充要条件：AOV 网中任意两个顶点之间都存在单向路径（任意两活动都有明确先后顺序）。 💡 实际判断法：每次输出顶点时，若当前入度为 0 的顶点都恰好只有一个，则最终序列唯一。

⚠️ 另两条结论： - 入度为零表示没有前驱活动，或其所有前驱活动均已执行完毕 - ⚠️ 可按拓扑排序结果对顶点重新编号，使新邻接矩阵成为上三角矩阵；反过来，若一般有向图的邻接矩阵能通过顶点重排变成上三角矩阵，则它一定是 DAG，因而存在拓扑序列

★ 考过 2011、2024

回源 · PDF 第 246 页 · b_246_7

AOE 网和 AOV 网的本质区别？　★2考¶

	AOV 网	AOE 网
顶点	活动	⚠️ 事件
边	前后关系，无权值	⚠️ 活动及其持续时间，带权值

AOE 网的两个基本性质： - ⚠️ 只有某顶点代表的事件发生后，从它出发的各活动才能开始 - ⚠️ 只有进入某顶点的各活动都完成后，该顶点代表的事件才能发生

⚠️ AOE 网通常只有一个入度为 0 的开始顶点（源点）和一个出度为 0 的结束顶点（汇点）。

关键路径 = ⚠️ 从源点到汇点所有路径中长度最大的那条；其上的活动称为关键活动。 ⚠️ 完成整个工程所需的最短时间 = 关键路径的长度。

★ 考过 2020、2025

回源 · PDF 第 247 页 · b_247_3

关键路径的四个参量怎么算？¶

事件最早发生时间 vₑ(k)：⚠️ 源点到 vₖ 的最长路径长度 vₑ(源点) = 0；vₑ(k) = Max{vₑ(j) + Weight(vⱼ, vₖ)}（vⱼ 是前驱） ⚠️ 按拓扑有序计算（拓扑排序时同步进行）
事件最迟发生时间 vₗ(k)：不推迟总工期的前提下 vₖ 必须发生的最晚时间 vₗ(汇点) = vₑ(汇点)；vₗ(k) = Min{vₗ(j) − Weight(vₖ, vⱼ)}（vⱼ 是后继） ⚠️ 必须按逆拓扑顺序计算（可用栈记录拓扑顺序，再从栈顶弹出）
活动最早开始时间 e(i) = ⚠️ 该弧起点事件的 vₑ 值
活动最迟开始时间 l(i) = ⚠️ 该弧终点事件的 vₗ 值 − 该弧权值
时间余量 d(i) = l(i) − e(i)；⚠️ d(i) = 0 的活动就是关键活动

💡 记忆法："e 看起点的早，l 看终点的迟减权"。

回源 · PDF 第 247 页 · b_247_21

求关键路径的五个步骤和教材算例？　★3考¶

① 令 vₑ(源点)=0，按拓扑有序求各顶点 vₑ
② 令 vₗ(汇点)=vₑ(汇点)，按逆拓扑有序求各顶点 vₗ
③ 求所有弧的 e()
④ 求所有弧的 l()
⑤ 找出所有 d() = 0 的活动构成关键路径

教材算例（图 6.23）： - vₑ：v1=0, v2=3, v3=2, v4=max{3+2, 2+4}=6, v5=6, v6=max{6+1, 6+2, 2+3}=8 - vₗ：v6=8, v5=7, v4=6, v3=min{6−4, 8−3}=2, v2=min{7−3, 6−2}=4, v1=0 - l(i)−e(i)：a1=1, a2=0, a3=1, a4=1, a5=0, a6=3, a7=0, a8=1 - ⚠️ 关键路径 = (v1, v3, v4, v6)

💡 教材应试提示：若是选择题，仅凭 vₑ 的计算过程通常就能推断出关键路径。

★ 考过 2019、2022、2025

回源 · PDF 第 248 页 · b_248_0

加快关键活动一定能缩短工期吗？　★2考¶

⚠️ 不一定，两个陷阱： - ⚠️ 不能任意缩短关键活动的持续时间 —— 一旦过度缩短，原关键路径可能短于其他路径，引发关键路径转移；此后继续压缩该活动也没用，工期已由新的最长路径决定 - ⚠️ 关键路径可能不止一条 —— 存在多条时，只提高其中某一条上的关键活动速度并不能缩短工期；只有加快同时出现在所有关键路径上的公共关键活动才有效

★ 考过 2013、2025

回源 · PDF 第 248 页 · b_248_21

各图算法在两种存储下的复杂度总表？¶

	Dijkstra	Floyd	Prim	Kruskal	DFS	BFS	拓扑排序	关键路径
邻接矩阵	O(n²)	O(n³)	O(n²)	—	O(n²)	O(n²)	O(n²)	O(n²)
邻接表	—	—	—	O(e log₂e)	O(n+e)	O(n+e)	O(n+e)	O(n+e)

回源 · PDF 第 249 页 · b_249_3

【原书试题精选与答案方法】第6章¶

2009、2010、2017、2022 统考的图论数量题，怎样先找“守恒式”和“临界图”？¶

四题答案依次为 A、C、B、D，其实只考两条主线。

度数守恒：无向图恒有

\[\sum_{v\in V}d(v)=2|E|.\]

2009 题由此知度数和必为偶数；2017 题要让顶点数最少，就让“其余顶点”的度尽量取题设允许的最大值 2，列式

\[3\times4+4\times3+2x=2\times16,\]

得 \(x=4\)，共 \(3+4+4=11\) 个顶点。 2. 连通临界：\(n\) 个顶点的连通无向图至少有 \(n-1\) 条边；不连通图最多可把 \(n-1\) 个顶点塞成完全图、另留 1 个孤立点，因此

\[E_{\max,\text{不连通}}=\binom{n-1}{2}.\]

2010 题取 \(n=7\)，超过 \(K_6\) 的 15 条边才必连通，故需 16 条；2022 题中 \(|E|<|V|-1\) 时必不连通，等价于 \(|V|>|E|+1\)。

⚠️ “存在一种连法能连通”只需 \(n-1\) 条边；“任意分配这些边都保证连通”要跨过最大不连通边数。两种问法不能混用。

回源 · PDF 第 212 页 · b_212_20；PDF 第 212 页 · b_212_21；PDF 第 212 页 · b_212_22；PDF 第 212 页 · b_212_23；PDF 第 213 页 · b_213_0；PDF 第 213 页 · b_213_3；PDF 第 213 页 · b_213_4；PDF 第 213 页 · b_213_5；PDF 第 213 页 · b_213_6

6.1 综合 01：28 条边的非连通无向图，为什么至少要 9 个顶点？¶

固定边数而让顶点数最少，应把边尽量集中：取一个完全图，再加一个孤立点保证整体不连通。

由

\[\binom{k}{2}=28\]

得 \(k=8\)，再加 1 个孤立点，所以至少有 9 个顶点。

💡 这与“给定 \(n\)，不连通图最多有多少边”是同一个极值模型：\(K_{n-1}\) 加一个孤立点。

回源 · PDF 第 213 页 · b_213_12；PDF 第 213 页 · b_213_13

2013、2024 统考及 6.2 综合 01：怎样从矩阵或邻接多重表反推图？¶

2013 统考答案 C：有向图中，第 \(i\) 行非零元数是出度，第 \(i\) 列非零元数是入度，顶点总度数是二者之和。带权矩阵里表示“无边”的 \(0\) 或 \(\infty\) 不计。
2024 统考答案 B：邻接多重表中一条无向边只对应一个边结点，但该结点同时挂在两个端点的链上。沿端点的关联链统计边结点，得 \(d(b)=2,d(d)=4\)。
综合 01：从带权有向图邻接矩阵画图时，逐项读取有限的非对角元 \(A[i][j]\)，画弧 \(i\to j\) 并把元素值写成权。

⚠️ 邻接多重表是无向图的结构，考试时统计“依附于顶点的边数”即可；不要被解析 OCR 中“入度/出度”的字样带偏。

回源 · PDF 第 223 页 · b_223_18；PDF 第 223 页 · b_223_19；PDF 第 223 页 · b_223_20；PDF 第 223 页 · b_223_21；PDF 第 223 页 · b_223_22；PDF 第 223 页 · b_223_23；PDF 第 224 页 · b_224_0

6.2 综合 02～03：邻接矩阵、邻接表之间怎样互读并统计边和度？¶

先判有向还是无向，再按同一套对应关系读图：

矩阵 \(A[i][j]=1\) 表示弧 \(i\to j\)；无向图还应有 \(A[j][i]=1\)。
邻接表中，顶点 \(i\) 的边链表列出它的出边；若每条边成对出现且题目未特殊说明，原书按无向图处理。
无向图边数：矩阵非零元数除以 2，或邻接表边结点数除以 2。
有向图边数：矩阵非零元数，或邻接表边结点数。
无向图的度看一行或一条边链；有向图的出度看行/本顶点边链，入度看列/扫描全部边链。

💡 “判断两点是否相邻”时，矩阵直接查元素；邻接表则在相应边链中查找邻接点。

回源 · PDF 第 224 页 · b_224_1；PDF 第 224 页 · b_224_2

6.2 综合 04：怎样重编号，使 DAG 的邻接矩阵只在主对角线上方出现 1？¶

最稳方法是先求一个拓扑序列，再按该序列从 1 到 \(n\) 编号。若有弧 \(v_i\to v_j\)，拓扑序必有 \(i<j\)，所以 1 只会落在上三角。

原书先给出“按出度排序后再调整”的思路，也明确指出拓扑排序更简便。考试写算法时优先写：

反复选入度为 0 的顶点；
按输出次序编号；
删除其出边并更新后继入度。

⚠️ 这要求原图无环；若处理不完全部顶点，就不存在这样的编号。

回源 · PDF 第 224 页 · b_224_3；PDF 第 224 页 · b_224_4；PDF 第 224 页 · b_224_5

6.2 综合 05：邻接表转邻接矩阵，代码骨架怎样写才不漏边？¶

先把矩阵初始化为“无边”，再逐顶点扫描边链：

for (int i = 0; i < G.vexnum; ++i)
    for (int j = 0; j < G.vexnum; ++j)
        arcs[i][j] = 0;            // 带权图按题设初始化为 0 或 ∞
for (int i = 0; i < G.vexnum; ++i)
    for (ArcNode *p = G.vertices[i].firstarc; p; p = p->nextarc)
        arcs[i][p->adjvex] = 1;   // 带权图则写入 p->weight

有向图按每个边结点写一次即可。
无向图的邻接表本就把一条边存两次，因此扫描全部边链后矩阵自然对称。
初始化整张矩阵需要 \(\Theta(|V|^2)\)，随后扫描邻接表为 \(O(|V|+|E|)\)，所以完整转换为 \(\Theta(|V|^2+|E|)\)；对简单图通常写成 \(\Theta(|V|^2)\)。

⚠️ 不要忘记初始化矩阵；否则未出现的边位置可能保留垃圾值。

回源 · PDF 第 224 页 · b_224_6；PDF 第 224 页 · b_224_7；PDF 第 225 页 · b_225_0；PDF 第 225 页 · b_225_1

2015 统考（6.2 综合 06）：为什么 \(A^m[i][j]\) 能数长度为 \(m\) 的路径？¶

设 \(A\) 是图的邻接矩阵。矩阵乘法展开

\[ (A^m)_{ij}=\sum A_{ik_1}A_{k_1k_2}\cdots A_{k_{m-1}j} \]

时，每个乘积项恰好对应一条从 \(i\) 到 \(j\)、长度为 \(m\) 的游走；在 0/1 邻接矩阵中，非零乘积贡献 1，因此总和就是条数。

本题 \(A^2[0][3]=3\)，表示从顶点 0 到顶点 3 有 3 条长度为 2 的路径/游走。推广到 \(B^m\) 时，\(B^m[i][j]\) 的非零值仍表示相应长度的条数。

⚠️ 这里按王道题目口径称“路径”，离散数学中更严格地说是允许重复顶点或边的 walk；统考作答沿教材口径即可。

回源 · PDF 第 225 页 · b_225_2；PDF 第 225 页 · b_225_3；PDF 第 225 页 · b_225_4；PDF 第 225 页 · b_225_5；PDF 第 225 页 · b_225_6；PDF 第 225 页 · b_225_7；PDF 第 225 页 · b_225_8；PDF 第 225 页 · b_225_9

2021 统考（6.2 综合 07）：EL 路径为何只需统计奇度顶点？¶

题干已经给出判据：连通无向图存在包含所有边、长度为 \(|E|\) 的 EL 路径，当且仅当奇度顶点数为 0 或 2。

对邻接矩阵逐行求和得到每个顶点的度，累计奇数度顶点个数，最后判断 count==0 || count==2。

时间复杂度：必须扫描 \(|V|\times|V|\) 的矩阵，故为 \(O(|V|^2)\)。
额外空间：只用若干计数变量，为 \(O(1)\)。

⚠️ source.json 的 OCR 把平方上标漏成了 \(O(n)\)；由矩阵双重循环及原书排版可确定应为 \(O(n^2)\)。

回源 · PDF 第 225 页 · b_225_10；PDF 第 225 页 · b_225_11；PDF 第 225 页 · b_225_12；PDF 第 225 页 · b_225_13；PDF 第 225 页 · b_225_14；PDF 第 225 页 · b_225_15

2023 统考（6.2 综合 08）：怎样用常数额外空间输出所有 K 顶点？¶

K 顶点定义为有向图中 出度大于入度 的顶点。邻接矩阵里：

\[ out(i)=\sum_j A[i][j],\qquad in(i)=\sum_j A[j][i]. \]

逐顶点计算这两个量，若 \(out(i)>in(i)\) 就输出顶点并令计数器加 1，最后返回计数。

时间复杂度 \(O(|V|^2)\)；
只用常数个变量，额外空间 \(O(1)\)。

💡 同一趟内对第 \(i\) 行、第 \(i\) 列同时累加即可，不必真的建立两个度数组。

回源 · PDF 第 226 页 · b_226_0；PDF 第 226 页 · b_226_1；PDF 第 226 页 · b_226_2；PDF 第 226 页 · b_226_3；PDF 第 226 页 · b_226_4

2012、2013、2015、2016 统考的遍历题，怎样用“队列分层、栈式深入”排除？¶

四题答案依次为 C、D、D、D。

2012：邻接表 BFS 每个顶点入队至多一次、每条边扫描常数次，时间 \(O(|V|+|E|)\)。
2013：检验 BFS 序列时，用“当前层的顶点必须先于下一层出现”逐项代入；D 项实为深度优先式深入。
2015：从 \(v_0\) 出发，先选 \(v_1,v_2,v_3\) 中任一个；访问后若仍有未访问后继就继续深入。完整模拟可得 5 种 DFS 序列。
2016：DFS 一旦进入某邻接点，只要它还有未访问邻接点，就不能跳回去访问兄弟分支；D 项违背这一点。

💡 选项题不要凭“看起来像”。在纸上维护 BFS 队列或 DFS 当前递归链，序列是否合法会立刻显现。

回源 · PDF 第 235 页 · b_235_2；PDF 第 235 页 · b_235_3；PDF 第 235 页 · b_235_4；PDF 第 235 页 · b_235_5；PDF 第 235 页 · b_235_6；PDF 第 235 页 · b_235_7；PDF 第 235 页 · b_235_8；PDF 第 235 页 · b_235_9；PDF 第 235 页 · b_235_10

6.3 综合 01：给定具体邻接表时，DFS/BFS 生成树为什么是固定的？¶

邻接表已经固定了每个顶点的邻接点次序，因此必须严格按链表顺序搜索：

DFS 树边依次为 \((1,2),(2,3),(3,4),(4,5)\)；
BFS 树边依次为 \((1,2),(1,3),(1,4),(2,5)\)。

⚠️ “同一个抽象图的遍历序列可能不唯一”不等于“给定具体存储后仍可任选”。邻接矩阵在顶点编号固定时顺序唯一；具体邻接表也把访问次序固定了。

回源 · PDF 第 235 页 · b_235_12；PDF 第 235 页 · b_235_13；PDF 第 235 页 · b_235_14

6.3 综合 02：怎样用 DFS/BFS 判断无向图是否为二分图？¶

从任一未染色顶点开始，把它染红并遍历：

遇到未染色邻接点，就染成与当前顶点相反的颜色并继续遍历；
遇到已染色且颜色相同的邻接点，立即判定不能二分；
颜色不同则跳过；非连通图还要从下一未染色顶点重新启动。

DFS 或 BFS 都可，时间 \(O(|V|+|E|)\)，颜色/访问数组空间 \(O(|V|)\)。

💡 本质判据是“图中不存在奇环”，但算法题直接写双色遍历更稳。

回源 · PDF 第 235 页 · b_235_15；PDF 第 236 页 · b_236_0；PDF 第 236 页 · b_236_1

6.3 综合 03：怎样用一次遍历判断无向图是不是树？¶

无向图是树，当且仅当它连通且边数为 \(|V|-1\)。从任一顶点 DFS：

统计实际访问的顶点数 Vnum；
扫描邻接表时统计边表结点数 Enum；无向边存两次，所以应满足

\[Vnum=|V|,\qquad Enum=2(|V|-1).\]

两式同时成立才返回 true。也可在 DFS 中检测回边，但“连通 + 边数”更直接。

⚠️ 只检查 \(|E|=|V|-1\) 不够：非连通图也可能一部分有环、另一部分孤立，仍凑出同样边数。

回源 · PDF 第 236 页 · b_236_2；PDF 第 236 页 · b_236_3；PDF 第 236 页 · b_236_4

6.3 综合 04：怎样分别用 DFS 和 BFS 判断 \(v_i\) 能否到达 \(v_j\)？¶

从 \(v_i\) 启动一次搜索即可：

DFS：递归访问未访问邻接点，一旦到达 \(v_j\) 就置 can_reach=true 并停止继续展开；
BFS：将 \(v_i\) 入队，逐层检查邻接点，发现 \(v_j\) 立即返回 1；
更简洁的写法是完整搜索后直接检查 visited[j]。

邻接表下时间复杂度均为 \(O(|V|+|E|)\)，额外空间均为 \(O(|V|)\)。

⚠️ 有向图必须按弧方向走；不能因为底层图“看起来连着”就判可达。

回源 · PDF 第 236 页 · b_236_5；PDF 第 236 页 · b_236_6；PDF 第 236 页 · b_236_7；PDF 第 236 页 · b_236_8；PDF 第 236 页 · b_236_9；PDF 第 237 页 · b_237_0；PDF 第 237 页 · b_237_1

6.3 综合 05：输出 \(v_i\) 到 \(v_j\) 的所有简单路径，为什么回溯时必须撤销 visited？¶

用 DFS 维护当前路径 path[0..d]：进入顶点 \(u\) 时把它加入路径并置 visited[u]=1；若 \(u=v_j\) 就输出当前路径；否则递归所有未访问邻接点。

关键在返回前执行：

visited[u] = 0;

这是在恢复搜索现场，使 \(u\) 可以出现在另一条候选路径中。沿当前递归链仍不会重复顶点，所以输出的都是简单路径。

⚠️ 若不撤销，只能得到搜索树首次到达形成的少量路径，会漏掉经过同一顶点但前缀不同的其他合法路径。

回源 · PDF 第 237 页 · b_237_2；PDF 第 237 页 · b_237_3；PDF 第 237 页 · b_237_4；PDF 第 237 页 · b_237_5；PDF 第 237 页 · b_237_6

2012、2015、2020 统考：Prim、Kruskal 与 MST 唯一性怎样区分？¶

三题答案依次为 A、C、A。

2012：MST 的树形可能不唯一，但所有 MST 的总代价必相同；权值相同的边可能有的入树、有的不入树。
2015：Kruskal 每次选当前最小且不成环的边；Prim 从 \(v_4\) 出发则只在“已入树集合—未入树集合”的割边中选。两者候选范围不同，故第 2 条边可不同，答案 C。
2020：Kruskal 依权值递增扫描，用并查集思想拒绝成环边，题图入树次序为 \((b,f),(b,d),(a,e),(c,e),(b,e)\)。

⚠️ “边权互异”是 MST 唯一的充分条件；但有相同边权也仍可能唯一，不能反推。

回源 · PDF 第 261 页 · b_261_11；PDF 第 261 页 · b_261_12；PDF 第 262 页 · b_262_10；PDF 第 262 页 · b_262_11；PDF 第 264 页 · b_264_5；PDF 第 264 页 · b_264_6；PDF 第 264 页 · b_264_7

2012、2016 统考：Dijkstra 每轮怎样选点、怎样更新 dist？¶

两题答案依次为 C、B。统一模板是：

在 \(V-S\) 中选 dist 最小的顶点 \(u\) 加入 \(S\)；
只尝试经 \(u\) 松弛仍在 \(V-S\) 的顶点：

\[dist[v]=\min\{dist[v],dist[u]+w(u,v)\};\]

加入 \(S\) 的先后顺序，就是最短路长度被最终确定的顺序。

2012 题在 \(b,c\) 后依次确定 \(f,d,e\)；2016 题最终 dist 为 \({0,5,7,11,4,9}\)，确定次序为 \(1,5,2,3,6,4\)。

⚠️ Dijkstra 要求边权非负；某顶点一旦入 \(S\)，其最短距离不再修改。

回源 · PDF 第 261 页 · b_261_13；PDF 第 261 页 · b_261_14；PDF 第 262 页 · b_262_0；PDF 第 262 页 · b_262_1；PDF 第 262 页 · b_262_2；PDF 第 262 页 · b_262_14；PDF 第 262 页 · b_262_15；PDF 第 263 页 · b_263_0；PDF 第 263 页 · b_263_1

2021、2023 统考：加权最短路与等权最短路怎样选算法？¶

2021 题答案 C：按 Dijkstra 初始化并连续两轮松弛后，dist 更新为 \((21,3,14,6)\)。做表时每轮只需记录“新入 \(S\) 顶点”和被它改善的列。
2023 题答案 B：所有边权都为 1 时，路径权就是边数；BFS 按距离分层，顶点首次被发现时即得到最短距离，因此一定能求单源最短路。

边界要背清：

BFS：无权图或所有边权相同；
Dijkstra：边权非负，可不相同；
Prim/Kruskal：求 MST，不保证树上两点路径是原图最短路。

回源 · PDF 第 265 页 · b_265_4；PDF 第 265 页 · b_265_5；PDF 第 265 页 · b_265_6；PDF 第 265 页 · b_265_11；PDF 第 265 页 · b_265_12；PDF 第 265 页 · b_265_13；PDF 第 265 页 · b_265_14

2010、2012、2014、2018 统考：拓扑序列怎样判断“存在、数量和合法性”？¶

四题答案依次为 B、C、D、D。

每轮选择任一入度为 0 的顶点输出，并删除其出边。
2010 题在分叉处枚举，得到 3 个序列：abced、abecd、aebcd。
2012 题的矩阵主对角线下全为 0，说明弧只可能从小编号指向大编号，所以一定无环、必有拓扑序；但可能不唯一。
2014 题按入度变化逐步筛选可行序列，答案 D。
2018 题先抓“当前所有入度为 0 的点”：开头只能是 1,5 或 5,1，据此排除。

⚠️ 能完整输出 \(|V|\) 个顶点才证明存在拓扑序；中途再无入度 0 顶点说明剩余部分含环。

回源 · PDF 第 261 页 · b_261_7；PDF 第 261 页 · b_261_8；PDF 第 261 页 · b_261_9；PDF 第 261 页 · b_261_10；PDF 第 262 页 · b_262_3；PDF 第 262 页 · b_262_4；PDF 第 262 页 · b_262_5；PDF 第 262 页 · b_262_8；PDF 第 262 页 · b_262_9；PDF 第 263 页 · b_263_7；PDF 第 263 页 · b_263_8

2016、2020、2021 统考：拓扑排序的复杂度、DFS 逆序与唯一性怎样串起来？¶

三题答案依次为 B、B、A。

邻接表做拓扑排序：顶点与边各处理常数次，时间 \(O(|V|+|E|)\)；邻接矩阵为 \(O(|V|^2)\)。
DAG 的 DFS 中，一个顶点退出递归前，其所有后继都已退出；所以“退出时输出”的顺序是逆拓扑序，反转后才是拓扑序。
若 Kahn 算法每一步都恰有一个入度为 0 的顶点，则拓扑序唯一；若某一步同时有多个，顺序便不唯一。

⚠️ “拓扑序唯一”只能说明所有顶点的先后约束被确定，不能据此唯一还原原图的全部边。

回源 · PDF 第 263 页 · b_263_2；PDF 第 263 页 · b_263_3；PDF 第 263 页 · b_263_4；PDF 第 263 页 · b_263_5；PDF 第 263 页 · b_263_6；PDF 第 264 页 · b_264_8；PDF 第 264 页 · b_264_9；PDF 第 264 页 · b_264_10；PDF 第 264 页 · b_264_11；PDF 第 264 页 · b_264_12；PDF 第 265 页 · b_265_2；PDF 第 265 页 · b_265_3

2013、2019、2020、2022 统考：AOE 网怎样算工期、活动时间和余量？¶

四题答案依次为 C、C、B、B。

核心量为：

\[ e(i)=ve(\text{弧尾}),\qquad l(i)=vl(\text{弧头})-w_i,\qquad d(i)=l(i)-e(i). \]

2013：先找出全部关键路径；要缩短工期，所加速的活动集合必须覆盖每一条关键路径，故选 C。
2019：活动 \(d\) 最早开始为 12，最迟开始为 \(21-7=14\)。
2020：关键路径是源点到汇点权值和最大的路径；若有多条关键路径，只缩短其中一条上的活动未必缩短总工期。
2022：逐活动算余量，\(g\) 的余量最大，为 6。

⚠️ 加长任一关键活动一定会拖延原工期；缩短某个关键活动却未必缩短工期，因为其他关键路径可能仍保持原长度。

回源 · PDF 第 262 页 · b_262_6；PDF 第 262 页 · b_262_7；PDF 第 263 页 · b_263_9；PDF 第 263 页 · b_263_10；PDF 第 263 页 · b_263_11；PDF 第 263 页 · b_263_12；PDF 第 264 页 · b_264_0；PDF 第 264 页 · b_264_1；PDF 第 265 页 · b_265_0；PDF 第 265 页 · b_265_1；PDF 第 265 页 · b_265_7；PDF 第 265 页 · b_265_8；PDF 第 265 页 · b_265_9；PDF 第 265 页 · b_265_10

2011、2019、2025 统考的综合判断，怎样避免把“必要”说成“充分”？¶

三题答案依次为 C、A、C。

2011：拓扑排序若只能输出部分顶点，剩余顶点都有前驱，说明有向图含环；这才是正确叙述。
2019：把表达式树中重复的运算或操作数顶点合并成 DAG，可减少顶点数；题中表达式最少需 5 个顶点，选 A。
2025：有限无向图中若每个顶点度都至少为 2，从任一点不断沿未立即返回的边前进，最终必重复顶点，从而形成回路。

同时记住两个常见反例：有向图无环只保证存在拓扑序，不保证唯一；BFS 只能直接保证等权图的最短路，不能处理一般不等权图。

回源 · PDF 第 262 页 · b_262_12；PDF 第 262 页 · b_262_13；PDF 第 264 页 · b_264_2；PDF 第 264 页 · b_264_3；PDF 第 264 页 · b_264_4；PDF 第 265 页 · b_265_15；PDF 第 265 页 · b_265_16

6.4 综合 01：“破圈法”为什么确实能得到最小生成树？¶

方法正确，它就是逆向删除法：在任一回路中删去一条权值最大的边，反复进行直到无环。

删回路上的边不会破坏连通性，因为回路中仍有另一条路连接两端。
对任一回路，其中一条最大权边可以不属于某棵 MST；删去它后，至少仍保留一棵 MST 的可能性。
最后图连通且无环，含 \(|V|-1\) 条边；又始终未排除全部 MST，因此所得生成树即为 MST。

💡 有并列最大边时任删其中一条仍可行，但最后得到的 MST 可能不唯一。

回源 · PDF 第 265 页 · b_265_18；PDF 第 265 页 · b_265_19；PDF 第 266 页 · b_266_0；PDF 第 266 页 · b_266_1

6.4 综合 02：一张图同时考矩阵、遍历、强连通、拓扑和 MST，作答顺序怎样安排？¶

按“存储 → 有向性质 → 无向加权性质”分层做：

由弧写邻接矩阵；按固定邻接次序从 1 DFS，序列为 1,2,3,5,7,4,6。
连续识别只有出弧、没有入弧的顶点并剥离；本图最终每个顶点单独成强连通分量，共 7 个。
反复删入度为 0 的顶点，可给出 1,2,4,6,3,5,7 与 1,4,2,6,3,5,7 两个拓扑序列。
视为无向图后，Prim 可依次选 1-2,1-3,3-6,3-5,5-7,6-4；Kruskal 则按边权从小到大且避环。

⚠️ 同一幅图在第 4 问已明确“视为无向图”，不要把有向图的强连通判断带进 MST。

回源 · PDF 第 266 页 · b_266_2；PDF 第 266 页 · b_266_3；PDF 第 266 页 · b_266_4；PDF 第 266 页 · b_266_5；PDF 第 266 页 · b_266_6；PDF 第 266 页 · b_266_7；PDF 第 266 页 · b_266_8；PDF 第 266 页 · b_266_9

6.4 综合 03：Dijkstra 表格怎样保证“顺序不能颠倒”？¶

每轮必须先从未确定顶点中选当前 dist 最小者，再用它松弛其他顶点。原题从顶点 1 出发的确定顺序为

\[1,2,3,4,5,6.\]

最终结果：

到 2：\(v_1\to v_2\)，长度 7；
到 3：\(v_1\to v_3\)，长度 11；
到 4：\(v_1\to v_2\to v_4\)，长度 16；
到 5：\(v_1\to v_3\to v_5\)，长度 18；
到 6：\(v_1\to v_3\to v_6\)，长度 19。

💡 “顺序不能颠倒”指每轮纳入 \(S\) 的次序，不是要求按顶点编号机械填写。

回源 · PDF 第 267 页 · b_267_1；PDF 第 267 页 · b_267_2；PDF 第 267 页 · b_267_3

6.4 综合 04：AOE 网从邻接表到关键路径，怎样按四步完成？¶

由图写出邻接表；
按拓扑序前推 \(ve\)，源点置 0；
从汇点按逆拓扑序回推 \(vl\)，令 \(vl(\text{汇点})=ve(\text{汇点})\)；
对每条活动弧算 \(e,l\)，满足 \(e=l\) 的是关键活动。

本题完成工程至少需 16 个时间单位，关键路径为

\[V_1\to V_3\to V_5\to V_7\to V_9,\]

加速活动 \(a_2,a_6,a_9,a_{12}\) 可以缩短工期。

⚠️ 若有多条关键路径，必须确认被加速活动能同时影响所有仍为最长的路径。

回源 · PDF 第 267 页 · b_267_4；PDF 第 267 页 · b_267_5；PDF 第 267 页 · b_267_6；PDF 第 268 页 · b_268_0；PDF 第 268 页 · b_268_1；PDF 第 268 页 · b_268_2；PDF 第 268 页 · b_268_3；PDF 第 268 页 · b_268_4

6.4 综合 05：由工序表构造 AOE 网后，怎样统一算事件与活动时间？¶

把工序作为弧、事件作为顶点；若多项工序共享前驱或后继，必要时用虚活动保持依赖关系。随后：

\[ ve(k)=\max_{\langle j,k\rangle}\{ve(j)+w(j,k)\}, \]

\[ vl(j)=\min_{\langle j,k\rangle}\{vl(k)-w(j,k)\}. \]

活动 \(i=\langle j,k\rangle\) 有 \(e(i)=ve(j)\)、\(l(i)=vl(k)-w(j,k)\)，余量 \(d(i)=l(i)-e(i)\)。本题关键活动为 B、E、G，完成工程至少需 8 个时间单位。

💡 表格题建议先列 \(ve/vl\)，再列 \(e/l/d\)；不要直接凭最长路径目测每条活动的最晚开始时间。

回源 · PDF 第 268 页 · b_268_5；PDF 第 268 页 · b_268_6；PDF 第 268 页 · b_268_7；PDF 第 268 页 · b_268_8；PDF 第 268 页 · b_268_9；PDF 第 268 页 · b_268_10；PDF 第 268 页 · b_268_11；PDF 第 268 页 · b_268_12；PDF 第 268 页 · b_268_13；PDF 第 268 页 · b_268_14

6.4 综合 06：Dijkstra 生成的最短路径树一定是 MST 吗？¶

Dijkstra 的最短路径前驱关系会在“从源点可达的顶点”上构成最短路径树；只有当所有顶点都从源点可达时，它才是原图的一棵生成树。它优化的是“源点到每个顶点的距离”；Prim 优化的是“整棵树的边权总和”，目标不同，所以前者不一定是 MST。

原书反例中：

Dijkstra 树边为 \((a,b),(a,c),(a,d)\)，总权 15；
Prim 树边为 \((a,d),(b,d),(c,d)\)，总权 7。

⚠️ 两算法都表现为逐步扩张集合，不能因代码形似就认定结果相同。

回源 · PDF 第 269 页 · b_269_0；PDF 第 269 页 · b_269_1；PDF 第 269 页 · b_269_2；PDF 第 269 页 · b_269_3；PDF 第 269 页 · b_269_4；PDF 第 269 页 · b_269_5；PDF 第 269 页 · b_269_6

6.4 综合 07：怎样用 DFS 的结束时间得到拓扑序？¶

在 DAG 上 DFS。顶点 \(v\) 的所有后继递归结束后，才记录 \(v\) 的结束时间；因此每条弧 \(v\to w\) 都满足 finish[v] > finish[w]。

把所有顶点按结束时间从大到小排列，就得到一个拓扑序；等价写法是在顶点退出 DFS 时压栈，最后依次出栈。

⚠️ 只有 DAG 才能这样得到拓扑序。通用实现还应使用三色标记检测回边；若发现指向“正在访问”顶点的边，就说明有环。

回源 · PDF 第 269 页 · b_269_7；PDF 第 269 页 · b_269_8；PDF 第 269 页 · b_269_9

2009 统考（6.4 综合 08）：为什么“每次走离当前点最近的边”不是最短路算法？¶

这种局部贪心不保证从源点到当前顶点的累计距离最小。原书反例中，规则会走

\[A\to B\to C,\]

但真正最短路径是

\[A\to D\to C.\]

Dijkstra 的贪心对象不是“当前边最小”，而是从所有未确定顶点中选取源点累计距离 dist 最小的顶点。

💡 反驳一个贪心算法，只需给出一个满足题设但局部最优导致全局非最优的反例。

回源 · PDF 第 269 页 · b_269_10；PDF 第 269 页 · b_269_11；PDF 第 269 页 · b_269_12

2011 统考（6.4 综合 09）：压缩上三角矩阵怎样还原图并求关键路径？¶

先按行优先把一维数组分成 \(5,4,3,2,1\) 个元素，依次填回 6 阶矩阵主对角线上方；对角线填 0，下三角填 \(\infty\)。由有限元素画弧并标权。

再按 AOE 方法计算，原书得到：

事件最早时间：\((0,4,9,13,12,16)\)；
事件最迟时间：\((0,4,9,13,13,16)\)；
关键活动：\(a_{0-1},a_{1-2},a_{2-3},a_{3-5}\)；
关键路径长度：\(4+5+4+3=16\)。

⚠️ 上三角压缩数组不存主对角线；还原时要自己补 0，并把不存在的弧补为 \(\infty\)。

回源 · PDF 第 269 页 · b_269_13；PDF 第 269 页 · b_269_14；PDF 第 269 页 · b_269_15；PDF 第 270 页 · b_270_0；PDF 第 270 页 · b_270_1；PDF 第 270 页 · b_270_2；PDF 第 270 页 · b_270_3；PDF 第 270 页 · b_270_4；PDF 第 270 页 · b_270_5；PDF 第 270 页 · b_270_6；PDF 第 270 页 · b_270_7；PDF 第 270 页 · b_270_8；PDF 第 270 页 · b_270_9；PDF 第 270 页 · b_270_10

2014 统考（6.4 综合 10）：OSPF 题怎样抽象成图、设计邻接表并跑 Dijkstra？¶

先剥离网络背景：路由器是图的顶点，链路和直连网络是与顶点关联的对象，整体可抽象为无向图。

链式存储可用路由器作表头结点；弧结点用 Flag 区分链路与网络，并用联合体保存 ID/IP 或 Prefix/Mask，共同保存 Metric 和下一指针。

从 R1 按 Dijkstra 策略得到：

192.1.1.0/24：直达，费用 1；
192.1.5.0/24：R1→R3，费用 3；
192.1.6.0/24：R1→R2，费用 4；
192.1.7.0/24：R1→R2→R4，费用 8。

💡 大题先写“顶点、边、权分别对应什么”，再写结构体，能避免被业务字段淹没。

回源 · PDF 第 270 页 · b_270_11；PDF 第 270 页 · b_270_12；PDF 第 270 页 · b_270_13；PDF 第 270 页 · b_270_14；PDF 第 270 页 · b_270_15；PDF 第 270 页 · b_270_16；PDF 第 271 页 · b_271_0；PDF 第 271 页 · b_271_1；PDF 第 271 页 · b_271_2；PDF 第 271 页 · b_271_3；PDF 第 271 页 · b_271_4；PDF 第 271 页 · b_271_5

2017 统考（6.4 综合 11）：Prim 选边与 MST 唯一性怎样完整回答？¶

从 \(A\) 开始，Prim 每轮只在“已入树集合 \(S\) 与外部顶点之间”的边中选最小者。原题依次选：

\[ (A,D),(D,E),(C,E),(B,C). \]

本图 MST 唯一：虽然 \((A,E)\) 与 \((C,E)\) 同权，但用前者替换后会使 \(A,D,E\) 成环，不能形成另一棵等权生成树。

对一般带权连通图，“任一回路内各边权值互不相同”可保证 MST 唯一。原书明确把它作为充分条件，本题不要求给充分必要条件。

⚠️ “所有边权互异”更强也正确；“存在相同边权”不能直接推出 MST 不唯一。

回源 · PDF 第 271 页 · b_271_6；PDF 第 271 页 · b_271_7；PDF 第 272 页 · b_272_0；PDF 第 272 页 · b_272_1；PDF 第 272 页 · b_272_2；PDF 第 272 页 · b_272_3；PDF 第 272 页 · b_272_4

2018 统考（6.4 综合 12）：最经济组网有多个 MST 时，TTL 为什么也会不同？¶

先用 Prim 或 Kruskal 求无向带权图的 MST。原题有两种最经济方案，总代价都为 16；图可用邻接矩阵或邻接表存储。

但 MST 只保证总造价最小，不保证任意两城市间的跳数相同：

方案 1 中 TL 到 BJ 路径过长，TTL=5 不足，H2 收不到；
方案 2 中 TL 与 BJ 更近，H2 可以收到。

⚠️ “MST 代价相同”不代表树形相同，更不代表端到端路径长度、时延或 TTL 结果相同。

回源 · PDF 第 272 页 · b_272_5；PDF 第 272 页 · b_272_6；PDF 第 272 页 · b_272_7；PDF 第 272 页 · b_272_8；PDF 第 272 页 · b_272_9；PDF 第 272 页 · b_272_10

2024 统考（6.4 综合 13）：怎样判定有向图是否存在唯一拓扑序？¶

先计算所有顶点入度，随后模拟 Kahn 拓扑排序。每一步都检查当前入度为 0 的顶点数：

恰为 1：取出它，删除其出边并继续；
大于 1：已有多种选择，拓扑序不唯一，返回 0；
为 0 且尚未处理完：图中有环，不存在拓扑序，返回 0；
最终处理满 \(|V|\) 个顶点：返回 1。

邻接矩阵实现时间 \(O(|V|^2)\)，入度数组空间 \(O(|V|)\)。

💡 判“唯一”比普通拓扑排序多的唯一条件，就是每一轮候选顶点都恰好一个。

回源 · PDF 第 272 页 · b_272_11；PDF 第 272 页 · b_272_12；PDF 第 272 页 · b_272_13；PDF 第 272 页 · b_272_14；PDF 第 273 页 · b_273_0

2025 统考（6.4 综合 14）：复杂 AOE 网怎样逐问算工期、并行、余量与补救？¶

原书先前推 \(ve\)、后推 \(vl\)，得到工程最短完成时间 12，关键活动为 \(a,e,m,n\)，关键路径对应事件序列 \(1,3,4,7,5\)。

活动 \(e\) 的执行窗口为 \([2,5]\)；与其窗口有重叠、因而可能同时进行的活动为 \(b,c,d\)。
时间余量最大的活动是 \(j\)，余量为 6。
活动 \(b\) 在时刻 6 才开始：若仍要按时完工，其持续时间最多为 4；若保持 \(b\) 的持续时间 5，则把活动 \(k\) 从 2 压缩到 1。

⚠️ “可同时进行”看时间窗口是否重叠，不是只看拓扑上是否互为前驱；补救题则把延迟后的时间代入到汇点约束 \(\le12\)。

回源 · PDF 第 273 页 · b_273_1；PDF 第 273 页 · b_273_2；PDF 第 273 页 · b_273_3；PDF 第 273 页 · b_273_4；PDF 第 273 页 · b_273_5；PDF 第 273 页 · b_273_6；PDF 第 273 页 · b_273_7；PDF 第 274 页 · b_274_0

【原书归纳总结与思维拓展】第6章¶

图的边数、连通分量与森林棵数，有哪些可以直接套用的极值模型？¶

把普通选择题中的零散结论收成四条：

连通无向图最少 \(n-1\) 条边；当 \(n\ge2\) 时，强连通有向图最少 \(n\) 条弧，构成有向环（单顶点图无需弧也已强连通）。
固定边数、求非连通图最少顶点：边尽量集中成完全图，再加孤立点。
固定顶点和边、求连通分量最多：边尽量集中到尽可能少的顶点中，其余顶点各自孤立。
无向森林有 \(n\) 个顶点、\(e\) 条边时，树的棵数为

\[c=n-e.\]

💡 极值题的共同策略是：为了让“剩余部分”最多或整体顶点最少，把边集中到完全图里。

回源 · PDF 第 211 页 · b_211_22；PDF 第 211 页 · b_211_23；PDF 第 212 页 · b_212_0；PDF 第 212 页 · b_212_1；PDF 第 212 页 · b_212_2；PDF 第 212 页 · b_212_3；PDF 第 212 页 · b_212_4；PDF 第 212 页 · b_212_7；PDF 第 212 页 · b_212_8；PDF 第 212 页 · b_212_11；PDF 第 212 页 · b_212_12；PDF 第 212 页 · b_212_17；PDF 第 212 页 · b_212_18；PDF 第 212 页 · b_212_19

邻接矩阵与邻接表的计数、唯一性和复杂度，怎样做成一张心中对照表？¶

邻接矩阵空间 \(O(|V|^2)\)，顶点编号固定时表示唯一；查边 \(O(1)\)，找一个顶点全部邻接点要扫一行。
邻接表空间 \(O(|V|+|E|)\)，链内次序取决于输入和插入算法，因此表示不唯一；稀疏图更省空间。
无向图中矩阵非零元数、邻接表边结点数都等于 \(2|E|\)；有向图中都等于 \(|E|\)。
有向图邻接表求出度只扫本链，求入度通常要扫全部边链，时间 \(O(|V|+|E|)\)。
\(A^m[i][j]\) 统计从 \(i\) 到 \(j\) 长度为 \(m\) 的路径/游走数。

⚠️ 带权矩阵要先确认题目用 0 还是 \(\infty\) 表示无边，不能把“无边标记”计入度数。

回源 · PDF 第 222 页 · b_222_9；PDF 第 222 页 · b_222_10；PDF 第 222 页 · b_222_11；PDF 第 222 页 · b_222_12；PDF 第 222 页 · b_222_13；PDF 第 222 页 · b_222_14；PDF 第 222 页 · b_222_15；PDF 第 222 页 · b_222_16；PDF 第 222 页 · b_222_17；PDF 第 222 页 · b_222_18；PDF 第 222 页 · b_222_19；PDF 第 222 页 · b_222_20；PDF 第 222 页 · b_222_21；PDF 第 222 页 · b_222_22；PDF 第 222 页 · b_222_23；PDF 第 222 页 · b_222_24；PDF 第 223 页 · b_223_0；PDF 第 223 页 · b_223_1；PDF 第 223 页 · b_223_2；PDF 第 223 页 · b_223_3；PDF 第 223 页 · b_223_4；PDF 第 223 页 · b_223_5；PDF 第 223 页 · b_223_6；PDF 第 223 页 · b_223_7；PDF 第 223 页 · b_223_8；PDF 第 223 页 · b_223_9；PDF 第 223 页 · b_223_10；PDF 第 223 页 · b_223_11；PDF 第 223 页 · b_223_12；PDF 第 223 页 · b_223_13；PDF 第 223 页 · b_223_14

十字链表与邻接多重表，怎样一句话选对对象？¶

十字链表用于有向图：弧结点同时挂在同弧头链和同弧尾链上，便于同时求入度、出度。
邻接多重表用于无向图：每条无向边只存一个边结点，却同时挂在两个端点的边链上，适合修改、删除和统计关联边。

口诀：有向“十字”分头尾，无向“多重”连两端。

回源 · PDF 第 223 页 · b_223_15；PDF 第 223 页 · b_223_16；PDF 第 223 页 · b_223_17

BFS、DFS 的访问标记、复杂度和序列唯一性，怎样统一记忆？¶

二者都必须在发现顶点时及时设置 visited，否则有环图会重复访问。

邻接表：时间均为 \(O(|V|+|E|)\)；邻接矩阵：时间均为 \(O(|V|^2)\)。
BFS 用队列，顶点最多入队一次，适合分层和等权最短路。
DFS 用递归栈/显式栈，适合回溯、连通性、环检测和路径枚举。
一次 DFS/BFS 启动访问一个无向连通分量；外层启动次数就是连通分量数。
抽象图的邻接表次序未定时，序列可能不唯一；给定具体存储次序后必须按该次序执行。

此外，BFS 生成树给出起点到各点的最少边数，因此其树高不大于 DFS 生成树树高。

回源 · PDF 第 233 页 · b_233_8；PDF 第 233 页 · b_233_9；PDF 第 233 页 · b_233_10；PDF 第 233 页 · b_233_11；PDF 第 233 页 · b_233_12；PDF 第 233 页 · b_233_13；PDF 第 233 页 · b_233_14；PDF 第 233 页 · b_233_15；PDF 第 233 页 · b_233_16；PDF 第 233 页 · b_233_17；PDF 第 233 页 · b_233_18；PDF 第 233 页 · b_233_19；PDF 第 234 页 · b_234_0；PDF 第 234 页 · b_234_1；PDF 第 234 页 · b_234_2；PDF 第 234 页 · b_234_3；PDF 第 234 页 · b_234_4；PDF 第 234 页 · b_234_5；PDF 第 234 页 · b_234_6；PDF 第 234 页 · b_234_7；PDF 第 234 页 · b_234_8；PDF 第 234 页 · b_234_9；PDF 第 234 页 · b_234_10；PDF 第 234 页 · b_234_11；PDF 第 234 页 · b_234_12；PDF 第 234 页 · b_234_13；PDF 第 234 页 · b_234_14；PDF 第 234 页 · b_234_15；PDF 第 234 页 · b_234_16；PDF 第 234 页 · b_234_17；PDF 第 234 页 · b_234_18；PDF 第 234 页 · b_234_19；PDF 第 234 页 · b_234_20；PDF 第 234 页 · b_234_21；PDF 第 234 页 · b_234_22；PDF 第 234 页 · b_234_23；PDF 第 235 页 · b_235_0；PDF 第 235 页 · b_235_1

MST 的“存在、唯一、候选边”三类判断，分别抓什么？¶

只有带权连通无向图才谈 MST；连通时一定存在。
MST 树形可能不唯一，但最小总代价一定相同。
Prim 的候选边必须跨越当前割 \((S,V-S)\)；Kruskal 的候选边来自全局未处理边，但加入后不得成环。
边权全互异可保证 MST 唯一；有相同权值不代表一定不唯一。
“取权值最小的 \(n-1\) 条边”不可靠，因为它们可能成环或不能连通全部顶点。

💡 判断某条边能否入某棵 MST 时，比死记算法更稳的是检查割性质与环性质。

回源 · PDF 第 258 页 · b_258_3；PDF 第 258 页 · b_258_4；PDF 第 258 页 · b_258_5；PDF 第 258 页 · b_258_6；PDF 第 258 页 · b_258_7；PDF 第 258 页 · b_258_8；PDF 第 258 页 · b_258_9；PDF 第 258 页 · b_258_10；PDF 第 258 页 · b_258_11；PDF 第 258 页 · b_258_12；PDF 第 258 页 · b_258_13；PDF 第 258 页 · b_258_14；PDF 第 258 页 · b_258_15；PDF 第 258 页 · b_258_16

BFS、Dijkstra、Floyd 与 MST 算法的适用边界，怎样不串台？¶

BFS：无权图或等权图的单源最短路。
Dijkstra：非负权图的单源最短路；不能处理负权边。
Floyd：所有顶点对最短路，可有负权边，但不能有负权回路。
Prim/Kruskal：求连通无向网的 MST，不保证源点到各点路径最短。

Dijkstra 每轮只会修改 \(V-S\) 中顶点的暂定距离；已加入 \(S\) 的顶点距离已经确定。

⚠️ “算法都使用贪心”只说明局部框架相似，不代表优化目标或输出相同。

回源 · PDF 第 258 页 · b_258_17；PDF 第 258 页 · b_258_18；PDF 第 258 页 · b_258_19；PDF 第 258 页 · b_258_20；PDF 第 258 页 · b_258_21；PDF 第 258 页 · b_258_22；PDF 第 259 页 · b_259_1

拓扑排序的存在、唯一、矩阵三角化与 DFS 输出，怎样形成闭环？¶

能完整拓扑排序 \(\Longleftrightarrow\) 有向图无环。
每一步入度为 0 的候选唯一 \(\Longrightarrow\) 拓扑序唯一；某一步有多个候选则不唯一。
按任一拓扑序重编号，邻接矩阵会成为主对角线一侧全零的三角形；反之，若矩阵已呈这种三角形，则图必无环。
DFS 退出顺序是逆拓扑序，反转后得到拓扑序。
拓扑序唯一时，该唯一序列中每对相邻顶点都必须存在“前者指向后者”的直接弧；否则二者可以交换。即便如此，图仍可增删不改变先后约束的跨越边，所以唯一拓扑序仍不能唯一确定原图。

⚠️ 强连通有向图必含环，因此顶点数大于 1 时不可能有拓扑序。

回源 · PDF 第 259 页 · b_259_2；PDF 第 259 页 · b_259_3；PDF 第 259 页 · b_259_4；PDF 第 259 页 · b_259_5；PDF 第 259 页 · b_259_6；PDF 第 259 页 · b_259_7；PDF 第 259 页 · b_259_8；PDF 第 259 页 · b_259_9；PDF 第 259 页 · b_259_10；PDF 第 259 页 · b_259_11；PDF 第 259 页 · b_259_12；PDF 第 259 页 · b_259_13；PDF 第 259 页 · b_259_14；PDF 第 259 页 · b_259_15；PDF 第 259 页 · b_259_16；PDF 第 259 页 · b_259_17；PDF 第 259 页 · b_259_18；PDF 第 259 页 · b_259_19；PDF 第 260 页 · b_260_0；PDF 第 260 页 · b_260_1；PDF 第 260 页 · b_260_2；PDF 第 260 页 · b_260_3；PDF 第 260 页 · b_260_4；PDF 第 260 页 · b_260_5；PDF 第 260 页 · b_260_6；PDF 第 260 页 · b_260_7；PDF 第 260 页 · b_260_8；PDF 第 260 页 · b_260_9；PDF 第 260 页 · b_260_10；PDF 第 260 页 · b_260_11；PDF 第 260 页 · b_260_12；PDF 第 260 页 · b_260_13

AOE 网的最长路径、关键活动和“加速是否有效”，怎样一次判清？¶

AOE 网中，源点到汇点的最长路径长度是工程最短完成时间；活动余量为 0 时是关键活动。

求最早时间向前取 max，求最迟时间向后取 min。
改变任一活动时，关键路径可能重新分配，不能只改旧表中的一个数就下结论。
若存在多条关键路径，只有让所有关键路径都缩短，工期才会缩短。
缩短公共关键活动也不能无限缩；缩到某个阈值后，另一条路径可能成为新的关键路径。

⚠️ 邻接矩阵某列全为 \(\infty\) 只说明该顶点无入边、可作工程起点；不能据此断言关键路径一定存在。

回源 · PDF 第 260 页 · b_260_15；PDF 第 260 页 · b_260_16；PDF 第 261 页 · b_261_1；PDF 第 261 页 · b_261_2；PDF 第 261 页 · b_261_3；PDF 第 261 页 · b_261_4；PDF 第 261 页 · b_261_5；PDF 第 261 页 · b_261_6

图算法为什么要通过统一基本操作隔离存储结构？¶

原书用 FirstNeighbor、NextNeighbor 等基本操作封装“怎样找邻接点”。上层 DFS、BFS、连通性与许多应用算法只依赖相同的参数和返回值，因此可在邻接矩阵、邻接表之间复用算法骨架。

矩阵版 NextNeighbor(G,x,y) 从第 \(y+1\) 列继续扫描第 \(x\) 行；
邻接表版先在 \(x\) 的边链中找到 \(y\)，再返回其后继边结点中的邻接点。

💡 考算法题时，若题目允许使用图的基本操作，就优先用抽象接口写主逻辑；只有题目明确要求某存储结构时，再展开底层扫描。

回源 · PDF 第 274 页 · b_274_1；PDF 第 274 页 · b_274_2；PDF 第 274 页 · b_274_3；PDF 第 274 页 · b_274_4；PDF 第 274 页 · b_274_5；PDF 第 274 页 · b_274_6；PDF 第 274 页 · b_274_7

原书章末六条易错结论，怎样压成考场检查表？¶

图可能有环，遍历必须用 visited 防止重复访问。
DFS 是回溯式过程，递归可改为显式栈；访问邻接点前先判未访问。
BFS 是队列支持的分层推进，不是递归回退过程。
顶点编号固定时邻接矩阵唯一；邻接表受边输入次序影响，不唯一。
MST 是带权连通无向图中含 \(n-1\) 条边、连通无环且总权最小的生成子图。
多条关键路径并存时，加速某一个关键活动未必缩短工期；应检查它是否影响所有关键路径。

把这六条当作选择题末轮排错清单，能挡住大多数“把可能说成必然”的选项。

回源 · PDF 第 274 页 · b_274_8；PDF 第 274 页 · b_274_9；PDF 第 274 页 · b_274_10；PDF 第 274 页 · b_274_11；PDF 第 274 页 · b_274_12；PDF 第 274 页 · b_274_13；PDF 第 274 页 · b_274_14

思维拓展：怎样用最直接的方法判断给定顶点是不是割点？¶

对候选顶点 \(v\)：

暂时删除 \(v\) 及所有关联边；
从剩余任一顶点做一次 DFS 或 BFS；
若仍有剩余顶点未被访问，则删除 \(v\) 后图不连通，\(v\) 是割点；否则不是。

若逐个顶点重复，朴素总复杂度约为 \(O(|V|(|V|+|E|))\)。原书只要求描述这一直接方法；一次 DFS 求出全部割点的 Tarjan 方法属于进一步拓展，不作为王道本题主线。

回源 · PDF 第 275 页 · b_275_0；PDF 第 275 页 · b_275_1；PDF 第 275 页 · b_275_2；PDF 第 275 页 · b_275_3

【易混点】第6章成对概念对照¶

概念 A	概念 B	一句话切分
图	线性表 / 树	⚠️ 顶点集不能为空（但边集可空）
	(v,w)	有向弧，v 尾 w 头 vs 无向边
度之和 = 2\|E\|	入度和 = 出度和 = \|E\|	无向图 vs 有向图
连通分量	强连通分量	无向图的极大连通子图 vs 有向图的极大强连通子图
极大连通子图	极小连通子图	点边尽可能多 vs 保持连通边最少（生成树）
邻接矩阵	邻接表	唯一、稠密图、判边 O(1) vs 不唯一、稀疏图、找邻接点快
十字链表	邻接多重表	⚠️ 只存有向图 vs ⚠️ 只存无向图
邻接表两个结点表示一条无向边	邻接多重表一个结点	删边/判边效率的根源
DFS	BFS	类似先序遍历、用栈（递归） vs 类似层次遍历、用队列
基于邻接矩阵的遍历序列	基于邻接表的	唯一 vs 可能不唯一
Prim	Kruskal	O(\|V\|²)、稠密图、挑点 vs O(\|E\|log₂\|E\|)、稀疏图、挑边
MST 唯一性	MST 权值	权值有相同则可能不唯一 vs 总权值一定唯一且最小
MST	最短路径	⚠️ MST 中两点间路径未必最短
Dijkstra	Prim	求最短路径树、可用于有向图 vs 求 MST、只能无向图
Dijkstra	Floyd	单源、不能负权、O(\|V\|²) vs 全源、可负权不可负环、O(\|V\|³)
AOV 网	AOE 网	顶点是活动、边无权 vs 顶点是事件、边是活动带权
拓扑排序	逆拓扑排序	选入度为 0 vs 选出度为 0
e(i)	l(i)	起点的 vₑ vs 终点的 vₗ 减权值
关键活动	非关键活动	d(i)=0 vs d(i)>0 有时间余量

【必背数字】第6章¶

数字	含义
n(n−1)/2 / n(n−1)	无向完全图 / 有向完全图的边数
n − 1	生成树的边数；无向图连通所需的最少边数
(n−1)(n−2)/2	n 个顶点的非连通图最多的边数
n	n 个顶点的有向图强连通所需的最少边数
\|E\| < \|V\|log₂\|V\|	稀疏图的一般判据
O(\|V\|²)	邻接矩阵空间复杂度；DFS/BFS 基于邻接矩阵的时间复杂度
O(\|V\|+2\|E\|) / O(\|V\|+\|E\|)	无向图 / 有向图邻接表的空间复杂度
Aⁿ[i][j]	从 i 到 j 长度为 n 的路径数量
O(\|V\|²) / O(\|E\|log₂\|E\|)	Prim / Kruskal 的时间复杂度
O(\|V\|²) / O(\|V\|³)	Dijkstra / Floyd 的时间复杂度
A^(k)[i][j] = min{A^(k−1)[i][j], A^{(k−1)[i][k]+A}(k−1)[k][j]}	Floyd 递推式
(v1, v3, v4, v6)	教材关键路径算例的答案
d(i) = l(i) − e(i) = 0	关键活动的判据

【口诀速记】第6章¶

维度	口诀	解释
度与边	无向 2E，有向入=出=E	无向图度之和 = 2\|E\|；有向图入度和 = 出度和 = \|E\|
存储选型	稠密矩阵、稀疏邻接表、有向十字、无向多重	十字链表只存有向图，邻接多重表只存无向图
邻接矩阵求度	行出列入	有向图第 i 行非零个数=出度，第 i 列=入度
最小生成树	稠密 Prim，稀疏 Kruskal	O(\|V\|²) 与边数无关 vs O(\|E\|log₂\|E\|) 与顶点数无关
Prim vs Dijkstra	Prim 挑点建树，Dijkstra 挑点算距	Prim 只能带权无向图，Dijkstra 有向无向都行
最短路径三选一	无权 BFS，带权 Dijkstra，负权或全源 Floyd	负权回路三者都不行
拓扑排序	找入度 0，输出不完就有环	唯一性看每步是否只有一个入度为 0 的顶点
关键路径	正推取 max，逆推取 min	vₑ 按拓扑序取 max；vₗ 按逆拓扑序取 min
活动时间	e 看起点的早，l 看终点的迟减权	d(i)=l(i)−e(i)=0 就是关键活动

回源 · PDF 第 206 页 · b_206_3；PDF 第 206 页 · b_206_4

【解题路线】第6章：图题怎么下手¶

① 先数顶点和边 → ⚠️ 无向图度之和 = 2|E|；有向图入度和 = 出度和 = |E|
② 问存储结构选型 → 稠密图用邻接矩阵；稀疏图用邻接表；⚠️ 有向图要频繁求入度用十字链表；无向图要频繁判边删边用邻接多重表
③ 最小生成树 → ⚠️ 稠密图选 Prim（O(|V|²)，与边数无关）；边稀疏顶点多选 Kruskal（O(|E|log₂|E|)）
④ 最短路径三选一：
无权图 → BFS
带权、非负、单源 → Dijkstra
⚠️ 有负权，或要求全源 → Floyd（负权回路谁都不行）
⑤ 拓扑排序 → 反复找入度为 0 的顶点；⚠️ 输出不完 = 有环；唯一性看每步是否只有一个入度为 0 的顶点
⑥ 关键路径四步：⚠️ 拓扑序求 vₑ（取 max）→ 逆拓扑序求 vₗ（取 min）→ e(i) 取起点的 vₑ、l(i) 取终点的 vₗ 减权值 → d = 0 的就是关键活动

⚠️ 三个常设的陷阱：MST 中两点间路径未必最短；关键路径可能不止一条，只压一条没用；Dijkstra 遇负权边会给出错误答案。

回源 · PDF 第 206 页 · b_206_5；PDF 第 206 页 · b_206_6

第6章 图

第6章 图¶