目标与训练安排

• 把图的方向、权重、自环和平行边语义落实到具体存储设计中；
• 用循环不变量或可达性论证解释遍历、转置与分量算法为什么正确；
• 区分输入规模、邻接记录数和辅助空间，完整分析表示转换及遍历成本；
• 针对错误标记时机、错误去重条件和错误连通概念给出最小反例；
• 根据查询、遍历和更新负载选择邻接矩阵、邻接表、边集数组或并查集。

前置阅读：6.1 图的基本概念、6.2 图的存储结构和6.3 图的遍历与连通性。建议先完成 06T01～06T03 的选择题，再分三次完成本训练。

组别	题号	核心任务	分值	建议用时
一	1～4	存储语义、表示转换与复杂度	40 分	60～75 分钟
二	5～8	完整遍历、标记时机与动态连通	40 分	60～70 分钟
三	9～12	强连通、Kosaraju 与综合选型	40 分	60～75 分钟

共 12 道理论大题，每题 10 分，总计 120 分，全部人工自评。每题提交一份包含条件整理、关键步骤或伪代码、正确性依据、复杂度和边界反例的书面答案。环境为现代浏览器与纸笔，无需编译器。

题目是依据本章教材整理的课程综合练习，不标注为历年真题。定义与复杂度结论参考严蔚敏、吴伟民《数据结构（C 语言版）》、Cormen 等《Introduction to Algorithms》第 3 版第 22 章，以及 OpenDSA 的 Graph Implementations 与 Graph Traversals，并按本章采用的“邻接表保存出边”约定统一表述。

第一组：存储语义与表示转换

第 1 题：一组边在三种表示中的语义

有向带权多重图的顶点为 0,1,2，按顺序读入四条逻辑边：

(0, 1, 0)
(0, 1, 5)
(1, 1, -2)
(2, 0, 4)

三元组依次表示起点、终点和权重。自环和平行边都必须计入度数。

1. 写出按输入顺序保存的边集数组，并写出只存出边的邻接表。（2 分）
2. 计算每个顶点的入度与出度。（2 分）
3. 若邻接矩阵每格是一个 optional<Weight>，重复赋值采用“后写覆盖”，写出最终矩阵，并指出丢失的信息。（3 分）
4. 设计一种矩阵单元类型，使其能够无损保存这些边；说明零权边与无边如何区分。（3 分）

第 1 题参考答案与评分要点

边集数组就是题面给出的四条记录，顺序不变。只存出边的邻接表为：

0: (1,0), (1,5)
1: (1,-2)
2: (0,4)

每条有向边为起点贡献一次出度、为终点贡献一次入度；自环同时为同一顶点贡献一次入度与一次出度。因此：

顶点	入度	出度
0	1	2
1	3	1
2	0	1

“后写覆盖”的单值矩阵为：

	0	1	2
0	无边	5	无边
1	无边	-2	无边
2	4	无边	无边

其中 (0,1,0) 被后来的 (0,1,5) 覆盖，已经无法恢复平行边的数量、顺序和第一个权重。零权边不能用数值 0 与无边共用一种状态。

一种无损方案是令每格保存 vector<Weight>：空向量表示没有边，[0,5] 表示两条从 0 到 1 的平行边。也可以保存带唯一边号的记录列表；关键是“存在性/条数”不能由单个权值猜测。

评分要点（10 分）： 两种表示各 1 分；六个度数全部正确 2 分；覆盖后矩阵 2 分、信息损失 1 分；可保存多值的单元设计 2 分、零权与无边的区分 1 分。

第 2 题：由工作负载选择主存储

系统保存 $n=20000$ 个顶点、$m=60000$ 条有向边。假设普通矩阵每格 4 字节，暂不计容器额外开销。

1. 估算邻接矩阵仅单元本身占多少字节和约多少 MiB。（2 分）
2. 比较普通矩阵与动态数组邻接表在“完整枚举所有顶点的出邻居”时的渐近成本。（2 分）
3. 若业务每秒大量执行 adjacent(u,v)，同时也频繁枚举邻居，提出主存储与辅助索引方案，并写出更新责任。（3 分）
4. 说明为什么“稀疏图一定只能用邻接表”和“矩阵连续内存一定更快”都不是充分的选型结论。（3 分）

第 2 题参考答案与评分要点

矩阵有 $n^2=400000000$ 个单元，共 $1600000000$ 字节，约为

$$\frac{1600000000}{{1024}^2}\approx 1525.9\text{ MiB}.$$

这还没有计入行对象、对齐或其他元数据。普通矩阵完整枚举邻接关系需扫描全部 $n^2$ 个位置，为 $\mathrm{\Theta }(n^2)$；邻接表扫描顶点表头和真实出边记录，为 $\mathrm{\Theta }(n+m)$。

适合的起点是以动态数组邻接表作为边的单一事实来源，并为需要热点查询的顶点维护哈希集合或全局边键哈希索引。插入、删除边必须通过同一更新入口同时维护邻接记录和索引；若其中一步失败，应回滚或禁止发布半更新状态。查询可获得期望 $O(1)$，邻居枚举仍与真实出度同阶。

密度只描述 $m$ 与 $n^2$ 的关系，不描述操作频率、内存预算、更新模式或稳定顺序。稀疏图若点对查询极多，可能值得增加索引；小型或较稠密图可能适合矩阵。连续内存改善缓存常数，但不能自动抵消扫描 $n^2$ 个单元的工作量，也不能替代实际基准测试。

评分要点（10 分）： 单元数与字节/MiB 估算 2 分；两种遍历成本 2 分；主存储、索引和统一更新各 1 分；对两个绝对化结论分别从负载、常数或规模角度反驳共 3 分。

第 3 题：无向多重图转换时不丢自环

无向多重图采用邻接表存储。每条逻辑边有唯一 edgeId；普通边 {u,v} 在 u、v 的表中各保存一条同 ID 记录，自环 {u,u} 也在 u 的表中保存两条同 ID 记录。要求转换为边集数组，每条逻辑边恰好输出一次，并保留平行边与自环。

1. 解释只在 u < v 时输出为什么会丢自环。（2 分）
2. 设计 $O(n+m)$ 时间的转换算法，其中 $m$ 是逻辑边数。（3 分）
3. 用“不重不漏”论证算法正确，并说明平行边为什么不会被错误合并。（3 分）
4. 分析输出空间与额外工作空间；若 ID 不连续，可怎样替换布尔数组？（2 分）

第 3 题参考答案与评分要点

自环两端相同，记录中的 u==v 永远不满足 u<v，所以该过滤条件会把全部自环丢弃。

若边号连续落在 [0,m)，可使用布尔数组：

seen[0..m-1] = false
result = empty edge array
for u = 0 .. n-1:
    for record in adjacency[u]:
        if not seen[record.edgeId]:
            seen[record.edgeId] = true
            append (record.from, record.to, record.weight, record.edgeId) to result
return result

若记录只保存另一个端点，则输出时使用当前 u 与 record.to；无向边的端点顺序可规范化为 (min,max)，但不能用端点对作为去重键，因为平行边端点相同而边号不同。

对每个逻辑边号，约定保证邻接表至少有对应记录。第一次遇到该 ID 时输出，之后所有副本因 seen 为真而跳过，所以每条边至少一次且至多一次。平行边具有不同 edgeId，因此会分别输出；自环的两条同 ID 记录只输出一次。

扫描 $n$ 个表头与约 $2m$ 条记录，时间为 $O(n+m)$。边集数组含 $m$ 项，是 $O(m)$ 输出空间；连续 ID 的 seen 是 $O(m)$ 额外工作空间。ID 稀疏时可使用哈希集合，期望时间仍为 $O(n+m)$，额外空间与实际不同 ID 数量同阶。

评分要点（10 分）： 自环反例 2 分；遍历与按 ID 标记算法 3 分；不重、不漏、平行边三点各 1 分；输出/辅助空间和稀疏 ID 方案 2 分。

第 4 题：构造转置图并核算成本

有向图 $G=(V,E)$ 只保存出边邻接表。转置图 $G^T$ 保留顶点集，并把每条边 $u\to v$ 改为 $v\to u$。

1. 写出从邻接表构造 $G^T$ 的伪代码，并给出时间与新增空间。（3 分）
2. 证明构造后的每条边与原图边一一对应。（2 分）
3. 若原图使用邻接矩阵，说明怎样原地得到转置以及复杂度。（2 分）
4. 说明为什么“把每个邻接表内部顺序反转”不是构造转置图，并给出最小反例。（3 分）

第 4 题参考答案与评分要点

transpose = n empty adjacency lists
for u = 0 .. n-1:
    for each edge (u, v, payload) in adjacency[u]:
        transpose[v].push_back((u, payload))

初始化表头并扫描每条出边，时间为 $\mathrm{\Theta }(n+m)$；新图保存 $n$ 个表头和 $m$ 条记录，新增空间为 $\mathrm{\Theta }(n+m)$。对原图每条记录，算法恰执行一次追加并产生反向边；新图中的记录又都由某次原边扫描产生，因此没有遗漏或凭空增加。

矩阵表示可对主对角线两侧成对交换 A[i][j] 与 A[j][i]，时间 $\mathrm{\Theta }(n^2)$、除临时变量外额外空间 $\mathrm{\Theta }(1)$。若需要同时保留原矩阵，则另分配一份 $\mathrm{\Theta }(n^2)$ 空间。

反转列表内部顺序只改变同一起点的邻居访问次序，不会交换起点和终点。最小反例是仅有边 0→1 的两顶点图：adj[0]=[1] 反转后仍为 [1]，而转置图应为 adjT[1]=[0]。

评分要点（10 分）： 构造算法 2 分、时间和空间 1 分；双向一一对应论证 2 分；矩阵方法与复杂度 2 分；概念区别 1 分、最小反例 2 分。

第二组：遍历不变量与连通性

第 5 题：完整 BFS 与确定性分量编号

无向图顶点为 0..8，边集为 {0,2}、{2,4}、{1,3}、{3,5}、{6,7}，顶点 8 为孤立点。邻接表已按编号升序。算法从顶点 0 到 8 扫描，每遇到未访问顶点便启动 BFS，并把本次发现的所有顶点标为当前分量号，然后分量号加一。

1. 写出每次 BFS 的起点、访问序列和最终 comp[0..8]。（3 分）
2. 给出完整遍历的伪代码。（2 分）
3. 证明外层一次启动与一个连通分量一一对应。（3 分）
4. 若删除外层扫描，只从 0 启动一次 BFS，会得到什么结果？这是否能证明图不连通？（2 分）

第 5 题参考答案与评分要点

四次 BFS 如下：

分量号	起点	BFS 访问序列
0	0	0,2,4
1	1	1,3,5
2	6	6,7
3	8	8

因此 comp=[0,1,0,1,0,1,2,2,3]。

visited[0..n-1] = false
component = 0
for s = 0 .. n-1:
    if visited[s]: continue
    visited[s] = true
    comp[s] = component
    enqueue(s)
    while queue not empty:
        u = dequeue()
        for v in adjacency[u]:
            if not visited[v]:
                visited[v] = true
                comp[v] = component
                enqueue(v)
    component += 1

一次 BFS 恰好访问与起点连通的全部顶点：沿搜索树可证明被发现点都与起点连通；对任何与起点连通但未发现的点，取路径上第一个未发现点，其前驱被处理时本应发现它，矛盾。外层选中的下一个起点尚未访问，所以不在此前任何分量中；最终扫描所有顶点，又不会漏掉分量。

只从 0 出发会访问 {0,2,4}，其余位置保持未访问。这次结果确实能证明本题这张无向图不连通，因为存在未访问顶点；但它不能给出全部分量及其编号。对有向图，相同现象只说明从 0 不可达那些顶点，不能直接套用无向连通结论。

评分要点（10 分）： 四次序列和标签 3 分；双层 BFS 2 分；可靠性、完整性、一一对应各 1 分；单源结果及无向/有向语义 2 分。

第 6 题：为什么必须在入队时标记

有向图邻接表为 0:[1,2]、1:[3]、2:[3]、3:[4]、4:[]。某错误 BFS 只在顶点出队时设置 visited[u]=true，入队前仅检查当前 visited[v]。

1. 追踪队列，指出顶点 3 为什么会被重复入队。（3 分）
2. 在有环图上，若出队后仍无条件扫描邻居，这个错误还可能造成什么问题？（2 分）
3. 写出正确的发现/入队不变量与关键伪代码。（3 分）
4. 说明修正后的邻接表 BFS 时间与空间复杂度。（2 分）

第 6 题参考答案与评分要点

从 0 出队后，1、2 依次入队。1 出队时 3 尚未访问，于是 3 入队；随后 2 出队时，3 仍未出队、visited[3] 仍是假，所以 3 再次入队。队列会出现 [3,3]。在更密的图中，同一顶点可被多个前驱重复加入。若出队后不跳过已经处理的副本并无条件继续扩展，在有环图中还可能持续产生副本甚至无法终止。

正确不变量是：顶点第一次进入队列之前立即标记；visited[v] 当且仅当 v 已经被发现，因此每个顶点最多入队一次。

visited[s] = true
queue.push(s)
while queue not empty:
    u = queue.pop()
    for v in adjacency[u]:
        if not visited[v]:
            visited[v] = true
            parent[v] = u
            queue.push(v)

每个顶点至多入队、出队一次，每条出边在其起点出队时检查一次，时间 $\mathrm{\Theta }(n+m)$；visited、队列及可选父节点数组共占 $O(n)$ 辅助空间，图自身存储不重复计入辅助空间。

评分要点（10 分）： 正确队列追踪及重复原因 3 分；环与无条件扩展风险 2 分；发现不变量 1 分、正确伪代码 2 分；时间和辅助空间 2 分。

第 7 题：显式栈复现递归 DFS

有向图邻接表按升序为 0:[1,2]、1:[2,3]、2:[3]、3:[]。递归 DFS 在进入顶点时输出它，并按邻接表顺序递归。

1. 写出从 0 开始的递归 DFS 输出。（1 分）
2. 说明“把当前顶点所有未访问邻居按升序依次压入普通顶点栈”为什么通常不能复现递归顺序，并追踪本图反例。（3 分）
3. 使用栈帧 (u,nextIndex) 设计与递归版本一致的算法。（3 分）
4. 给出等价性不变量，以及时间、空间和长链边界分析。（3 分）

第 7 题参考答案与评分要点

递归输出为 0,1,2,3。若普通 LIFO 栈把 1、2 按升序压入，2 位于栈顶，下一次访问 2，输出会以 0,2,... 开始，已经与递归版本不同。简单地改成逆序压栈，在存在共享后继或要求精确复现回溯事件时仍容易丢失“当前顶点处理到第几个邻居”的状态。

visited[0] = true
output(0)
push frame (0, 0)
while stack not empty:
    frame = reference to stack.top
    u = frame.u
    if frame.nextIndex == adjacency[u].size:
        pop frame
        continue
    v = adjacency[u][frame.nextIndex]
    frame.nextIndex += 1
    if not visited[v]:
        visited[v] = true
        output(v)
        push frame (v, 0)

不变量：栈中从底到顶正好对应递归调用链；每个帧的 nextIndex 指向该调用尚未检查的第一个邻居。发现未访问邻居时压入新帧等价于递归调用，邻居耗尽时弹帧等价于函数返回。因此进入顺序与递归算法逐步一致。

每条边至多检查一次、每个顶点至多压栈一次，时间 $O(n+m)$；visited 与最深调用链占 $O(n)$ 辅助空间。长度接近 $n$ 的长链会让语言调用栈存在溢出风险，显式栈把同样的线性状态放在可控的堆容器中，但不会把最坏空间降为 $O(1)$。

评分要点（10 分）： 输出 1 分；普通压栈反例与追踪 3 分；完整帧算法 3 分；等价不变量、复杂度、长链边界各 1 分。

第 8 题：静态、只增边与可删除图的连通查询

同一组无向图业务有三种版本：

• A：图构建后不再修改，需要输出每个连通分量中的全部顶点；
• B：初始无边，只有 add(u,v) 与 connected(u,v)，不要求输出路径；
• C：在 B 的基础上增加任意 remove(u,v)。

1. 为 A、B 分别选择本章合适的方法，并说明输出能力。（3 分）
2. 给出 B 中并查集维护的不变量及单次操作的均摊复杂度。（3 分）
3. 解释普通并查集为什么不能直接正确支持 C，并给出一个三顶点反例。（2 分）
4. 若 C 的操作序列全部预先已知，给出一种进一步研究的离线方向；无需写完整算法。（2 分）

第 8 题参考答案与评分要点

A 可用邻接表上的完整 DFS/BFS：一次搜索得到一个分量，并可在搜索过程中收集全部顶点，总时间 $\mathrm{\Theta }(n+m)$。B 适合并查集：加边时合并两端代表元，查询时比较代表元；它快速回答是否连通，但不保存一条可输出的实际路径。

并查集不变量是：两个顶点属于同一集合，当且仅当当前已加入边使它们无向连通。初始每点自成集合；加入 {u,v} 时合并两个分量恰好反映新边造成的连通闭包。使用路径压缩和按秩或按大小合并时，每次操作均摊为 $O(\alpha (n))$，总空间 $O(n)$。

普通并查集只会合并集合，无法拆分。反例：先加入 {0,1}、{1,2}，三个顶点被合并；再删除 {1,2} 后，0 与 2 已不连通，但并查集仍报告同一代表元。

若全部操作离线已知，可研究“按时间分治 + 可回滚并查集”，或把边的有效时间区间加入线段树后在递归过程中合并并回滚。也可对只有删除的特殊序列逆序处理，把删除变为加边。在线任意动态连通需要比普通并查集更复杂的数据结构。

评分要点（10 分）： A/B 方法和输出差异 3 分；并查集不变量 2 分、复杂度 1 分；删除失效解释与反例 2 分；合理离线方向 2 分。

第三组：强连通与综合选型

第 9 题：用原图和转置图判断强连通

给定非空有向图 $G$ 和任意起点 $s$。算法先在 $G$ 中从 $s$ 遍历，再在 $G^T$ 中从 $s$ 遍历；两次都访问全部顶点时返回“强连通”。

1. 证明该条件充分且必要。（4 分）
2. 给出只做第一次正向遍历会误判的三顶点反例。（2 分）
3. 使用邻接表时分析构造转置和两次遍历的总复杂度。（2 分）
4. 说明空图为什么需要单独约定，并说明更换起点是否改变最终判断。（2 分）

第 9 题参考答案与评分要点

必要性：若 $G$ 强连通，则任意顶点之间互相可达，所以在 $G$ 中从 $s$ 可达所有点；反转所有边后仍强连通，因此在 $G^T$ 中也可达所有点。

充分性：第一次遍历保证对任意顶点 $v$，存在 $s⇝v$。第二次在转置图中存在 $s⇝v$，反转回原图就是 $v⇝s$。于是对任意 $u,v$，可沿 $u⇝s⇝v$ 到达，故图强连通。

反例可取 0→1、1→2。从 0 正向能访问全部顶点，但 2 无法回到 0，图不强连通。

构造转置、第一次遍历和第二次遍历各为 $O(n+m)$，总时间仍为 $O(n+m)$；同时保存两份邻接表时空间为 $O(n+m)$，访问数组为 $O(n)$。空图没有可选起点，“是否强连通”在不同教材中可能约定不同，接口必须显式定义。本证明对任意实际顶点 $s$ 都成立，所以非空图更换起点不会改变最终布尔结论。

评分要点（10 分）： 必要性 2 分、充分性 2 分；最小反例 2 分；时间和空间 2 分；空图约定与起点独立性各 1 分。

第 10 题：手推 Kosaraju 的两轮 DFS

有向图顶点为 0..7，邻接表按编号升序，边为：

0→1, 1→2, 2→0, 2→3,
3→4, 4→3, 4→5,
5→6, 6→7, 7→5

第一轮按顶点编号扫描，在原图上 DFS，并在顶点完成时压入列表；第二轮按完成时间递减顺序，在转置图上对未分量化顶点 DFS。

1. 写出第一轮从 0 开始的发现顺序与完成顺序。（2 分）
2. 写出第二轮处理起点的顺序及得到的三个 SCC。（3 分）
3. 画出凝聚图，并标出分量间的有向边。（2 分）
4. 解释为什么第二轮必须按完成时间递减，而不是递增；给出本图中的失败现象。（3 分）

第 10 题参考答案与评分要点

第一轮从 0 可沿链访问全部顶点，发现顺序为 0,1,2,3,4,5,6,7。7 只能回到已发现的 5，因此先完成 7，再依次完成 6、5、4、3、2、1、0。完成顺序为 7,6,5,4,3,2,1,0，递减完成时间的处理序列为 0,1,2,3,4,5,6,7。

第二轮在转置图中：

1. 从 0 启动，得到 {0,1,2}；
2. 扫到 3 时未标记，从 3 启动，得到 {3,4}；
3. 扫到 5 时未标记，从 5 启动，得到 {5,6,7}。

记三个分量为 A、B、C，原图跨分量边为 2→3 与 4→5，凝聚图为 A→B→C。

第一轮递减完成时间使第二轮在转置凝聚图中从“没有边通向尚未处理分量”的 SCC 开始，搜索不会越界吞并其他 SCC。若反过来按递增完成时间，先从 7 所在的 C 开始；转置凝聚图为 C→B→A，一次 DFS 就能到达 B 和 A，会把三个 SCC 错标成一个分量。

评分要点（10 分）： 两种顺序各 1 分；三个 SCC 及启动过程 3 分；凝聚图节点与两条边 2 分；正确顺序作用 1 分、反序在本图的具体失败 2 分。

第 11 题：凝聚图为什么一定是 DAG

把有向图的每个强连通分量缩成一个超级顶点；原图存在跨分量边时，在超级顶点之间连边，得到凝聚图。

1. 用反证法证明凝聚图不可能含有向环。（4 分）
2. 说明证明依赖 SCC 的哪一项性质。（2 分）
3. 若把“强连通分量”改成“弱连通分量”，凝聚图中的跨分量边会怎样？（2 分）
4. 给出凝聚图为后续处理提供的两个直接用途。（2 分）

第 11 题参考答案与评分要点

假设凝聚图存在由不同超级顶点组成的有向环

$$C_1\to C_2\to \cdots \to C_k\to C_1.$$

每个 $C_i$ 内部任意两点互相可达，而环上的跨分量边又让任意一个分量能够沿环到达其他所有分量并返回。因此这些分量并在一起后仍然强连通，与每个 SCC 是极大的强连通顶点集合矛盾。所以凝聚图无环，是 DAG。

证明关键不只是“分量内部连通”，而是双向可达加极大性。弱连通分量按忽略方向后的无向连通性划分；任何跨越两个弱连通分量的有向边在忽略方向后都会把它们连接起来，故不同弱连通分量之间根本不存在边，所谓凝聚图只有孤立超级顶点。

凝聚图可用于：对 SCC 做拓扑排序；在分量级别进行可达性动态规划；寻找源/汇分量；把有环问题先压缩成 DAG 后再分析。任选两个并说明对象已从原顶点缩为分量即可。

评分要点（10 分）： 假设环、推出合并后互达、与极大性矛盾共 4 分；SCC 性质 2 分；弱连通跨边结论与理由 2 分；两个合理用途各 1 分。

第 12 题：从问题语义到算法与表示

对下列五项任务，分别写出推荐的表示、核心算法、时间复杂度，并指出一个不能混淆的概念或前提：

1. 静态无向稀疏图：输出所有连通分量；
2. 静态有向稀疏图：判断整图是否强连通；
3. 静态有向稀疏图：划分全部 SCC；
4. 稠密小图：反复查询指定点对是否直接相邻；
5. 无向图只增边：频繁查询两点是否连通，不要求路径。

前四项各 2 分，第五项 2 分。答案只写算法名而没有表示、复杂度或前提，每项至多得 1 分。

第 12 题参考答案与评分要点

任务	推荐表示与算法	时间复杂度	关键前提或易混点
无向分量	邻接表；外层扫描 + DFS/BFS	$\mathrm{\Theta }(n+m)$	一次单源搜索只得到一个分量；孤立点也是分量
判断强连通	出边邻接表；在 $G$ 与 $G^T$ 从同一顶点各遍历一次	$\mathrm{\Theta }(n+m)$	从某点可达全部顶点不等于任意两点互达
划分全部 SCC	邻接表；Kosaraju 或 Tarjan	$\mathrm{\Theta }(n+m)$	弱连通分量不能替代 SCC；Kosaraju 第二轮顺序不可省
稠密点对查询	邻接矩阵；直接访问 A[u][v]	单次 $\mathrm{\Theta }(1)$，空间 $\mathrm{\Theta }(n^2)$	查询的是直接边，不是路径可达；带权图须区分无边与零权
只增边连通查询	并查集；加边时 union、查询时比较 find	均摊 $O(\alpha (n))$，空间 $O(n)$	仅适用这里的无向连通与只增边条件，不能输出路径或处理普通删除

选型顺序应是先确认“直接相邻还是路径可达、无向还是有向、只判断还是划分、静态还是动态”，再根据规模与高频操作选择存储。把所有题都回答成 DFS/BFS，或者看到“连通”就无条件使用并查集，都会丢失题目语义。

评分要点（10 分）： 每项 2 分，其中表示/算法 1 分，复杂度与关键前提合计 1 分。合理的等价方法可以得分，例如 SCC 使用 Tarjan；但必须保持相同语义并说明复杂度。

完成清单与复盘

• 12 题均写出图的方向、权重、自环/平行边约定以及输入规模符号；
• 第 1～4 题区分了逻辑边、邻接记录和矩阵单元，并证明转换不重不漏；
• 第 5～8 题写出了发现时标记、搜索森林或集合划分不变量；
• 第 9～11 题分别完成双向可达、Kosaraju 顺序和凝聚图无环证明；
• 第 12 题先判断问题语义，再给表示、算法、复杂度和适用前提；
• 按每题 10 分独立自评，并为每个失分点记录一张最小反例图。

复盘思考：任选两道题，改变其中一个条件——例如允许平行边、把无向改为有向、加入删除操作或要求输出路径——说明原方法的哪一条不变量首先失效，以及需要更换表示、算法还是仅补充索引。