目标

• 区分单源遍历、完整遍历与搜索森林；
• 判断无向连通分量以及有向图的弱连通、强连通；
• 解释原图与转置图的双向可达检查；
• 理解 Kosaraju 的两轮 DFS、SCC 划分与凝聚图；
• 根据问题是否动态增边选择遍历或并查集。

前置知识

建议先阅读6.3 图的遍历与连通性，并能在邻接表上手推一次 DFS 或 BFS。

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔记录 visited、完成顺序和分量编号。
• 输入：本页按源文件顺序呈现的 12 道四选一选择题。
• 预期输出：一份独立作答记录，并能为每题写出“遍历覆盖范围”或“有向可达方向”的依据。

作答方法

1. 先确认图是有向还是无向，再判断可达是否对称；
2. 区分“一次从起点搜索”与“外层扫描所有顶点”；
3. 遇到强连通问题时，同时检查正向与反向可达；
4. 点击“提交答案”后核对解析，做错的题重新画出分量或凝聚图。

题型覆盖与边界

类型	本 Lab 的处理方式
正常情况	单源可达、完整遍历、无向分量标号和 SCC 划分
边界情况	孤立顶点、只有单向可达但从起点覆盖全图
易错情况	混淆弱连通与强连通、把访问顺序当作分量定义
方法选型	比较 DFS/BFS、Kosaraju 与只增边并查集

选择题

答题进度已答 0/12正确 0

第 1 题

难度★考点单源遍历、可达、有向图标识ch06-03-q01

有向图的顶点集为 $\{0,1,2,3\}$，边集为 $\{0\to 1,1\to 2,3\to 2\}$。从顶点 $0$ 启动一次 DFS 或 BFS，最终被访问的顶点集合是（ ）。

查看提示

只沿箭头方向从 0 出发，不要因为 3 指向 2 就反向访问 3。

请选择一个答案

A$\{0\}$

B$\{0,1\}$

C$\{0,1,2\}$

D$\{0,1,2,3\}$

第 2 题

难度★★考点完整遍历、连通分量、搜索森林标识ch06-03-q02

无向图有顶点 $\{0,1,2,3,4,5\}$，边集为 $\{\{0,1\},\{1,2\},\{3,4\}\}$。按顶点编号从小到大扫描，每遇到未访问顶点就启动一次 BFS。总共会启动多少次 BFS？

请选择一个答案

A1 次

B2 次

C3 次

D4 次

第 3 题

难度★★考点visited、标记时机、DFS、BFS标识ch06-03-q03

在基础 DFS/BFS 中，为避免同一顶点在等待期间被多个邻居重复加入栈或队列，最合适的标记时机是（ ）。

请选择一个答案

A首次发现并加入栈或队列时

B从栈或队列取出后

C扫描完整张图以后

D只有遇到环时才标记

第 4 题

难度★★考点邻居顺序、DFS、BFS、连通分量标识ch06-03-q04

对同一张无向图改变各邻接表中的邻居顺序，再重新运行完整 DFS。下列哪一项一定不变？

请选择一个答案

A顶点发现顺序

BDFS 搜索树的边

C每个顶点的完成时间

D连通分量的顶点划分

第 5 题

难度★★考点强连通、单源可达、有向图标识ch06-03-q05

有向图只有边 $0\to 1$、$1\to 2$。从 $0$ 出发能遍历全部顶点。关于整张图，下列说法正确的是（ ）。

请选择一个答案

A一定强连通

B弱连通但不强连通

C既不弱连通也不强连通

D顶点 2 一定能到达顶点 0

第 6 题

难度★★★考点弱连通分量、强连通分量、有向图标识ch06-03-q06

有向图边集为 $\{0\to 1,1\to 0,1\to 2,2\to 3,3\to 2\}$。它的弱连通分量数与强连通分量数分别是（ ）。

请选择一个答案

A1 和 1

B1 和 2

C2 和 1

D2 和 2

第 7 题

难度★★★考点强连通、转置图、可达标识ch06-03-q07

对一张非空有向图任选顶点 $s$。下列哪组条件能够判定整张图强连通？

请选择一个答案

A只要求 $s$ 在原图中能到达全部顶点

B只要求转置图中全部顶点的入度非零

C要求从 $s$ 在原图和转置图中都能访问全部顶点

D要求忽略方向后从 $s$ 能访问全部顶点

第 8 题

难度★★考点强连通分量、最大顶点集合、互相可达标识ch06-03-q08

下列哪一项最准确地描述有向图的一个强连通分量？

请选择一个答案

A任意一条有向路径上的全部顶点

B任意两个顶点之间至少存在一条边的集合

C内部任意两点互相可达且不能继续扩大的顶点集合

D忽略方向后形成一棵树的顶点集合

第 9 题

难度★★★考点SCC、凝聚图、DAG标识ch06-03-q09

把有向图的每个强连通分量缩成一个顶点，并保留分量间的边。所得凝聚图一定具有哪项性质？

请选择一个答案

A一定是完全图

B一定是无环有向图

C一定是无向树

D所有顶点入度都为 1

第 10 题

难度★★★考点Kosaraju、完成顺序、转置图标识ch06-03-q10

采用“第一轮在原图上记录完成顺序”的 Kosaraju 实现时，第二轮应当怎样处理？

查看提示

记住组合：原图记完成顺序，转置图按完成时间递减收集。

请选择一个答案

A在原图上按发现时间递增启动 BFS

B在转置图上按完成时间从大到小启动 DFS

C在转置图上按顶点入度从小到大启动 DFS

D忽略方向后只运行一次 DFS

第 11 题

难度★★考点Kosaraju、复杂度、邻接表标识ch06-03-q11

有向图以邻接表存储，$n=|V|$、$m=|E|$。构造转置图并执行两轮完整 DFS 的 Kosaraju 算法，时间复杂度为（ ）。

请选择一个答案

A$O(n)$

B$O(m)$

C$O(n+m)$

D$O(nm)$

第 12 题

难度★★★考点并查集、动态连通性、DFS、BFS标识ch06-03-q12

一张无向图初始没有边，之后只执行“加入一条边”和“询问两点当前是否连通”，且操作次数很多。若不要求输出实际路径，优先选择（ ）。

请选择一个答案

A每次查询都重新运行 Floyd

B带路径压缩和按大小合并的并查集

C每次加入边都重建邻接矩阵并排序

DKosaraju 强连通分量算法

答案总览（建议完成全部题目后查看）

1. 第 1 题：C
2. 第 2 题：C
3. 第 3 题：A
4. 第 4 题：D
5. 第 5 题：B
6. 第 6 题：B
7. 第 7 题：C
8. 第 8 题：C
9. 第 9 题：B
10. 第 10 题：B
11. 第 11 题：C
12. 第 12 题：B

完成清单

• 12 道题均在展开解析前独立作答；
• 能说明完整遍历为何总能访问全部顶点，却不能据此直接判断图连通；
• 能用 $G$ 与 $G^T$ 的两次遍历判断非空有向图是否强连通；
• 能解释 SCC 凝聚图为什么不可能含有向环；
• 能说出 Kosaraju 两轮 DFS 的图、记录时机与处理顺序。

思考题

1. 为什么改变邻接表中的邻居顺序可能改变 DFS 树，却不会改变 SCC 划分？
2. 判断整张图强连通只需两次单源遍历，为什么划分全部 SCC 还需要完成顺序？
3. 并查集为什么适合无向图增量连通性，却不能直接维护有向图强连通性？

复盘

• 我是否先区分了“从 $s$ 可达所有点”和“任意两点互相可达”？
• 我是否把孤立顶点计为独立连通分量？
• 我能否不看代码复述 Kosaraju 的两轮处理顺序？