图遍历

图遍历用于从一个起点出发访问可达顶点。Baseline 中需要完成 BFS、DFS 和拓扑排序。三者的关注点不同：BFS 按层推进，DFS 沿路径深入，拓扑排序处理有向依赖关系。

BFS：按距离分层访问

BFS 使用队列。先发现的顶点先处理，因此它会按“距离起点经过多少条边”逐层向外扩展。在无权图中，BFS 第一次访问到某个顶点时，经过的边数就是最少边数。

BFS 遍历过程：起点入队

1/8

对应过程：

1. 将起点 A 入队，并立刻标记为已访问。
2. 取出队首 A，把它加入访问序列。
3. 按邻接表顺序发现 D、B、C，全部入队。
4. 取出 D，第一次发现 F。
5. 取出 B，第一次发现 E。
6. 取出 C 时，D 和 E 已经被发现，因此不能重复入队。
7. 继续处理 F，第一次发现 G。
8. 队列为空时结束。

实现 BFS 时，推荐在“入队时”标记已访问，而不是在“出队时”才标记。这样可以避免同一个顶点被多个前驱重复放入队列。

DFS：沿一条路径深入

DFS 可以用递归或显式栈实现。它从当前顶点出发，选择一个尚未访问的邻接点继续深入；当没有新的邻接点时，再回退到上一个顶点。

DFS 递归过程：访问 A

1/10

对应过程：

1. 进入顶点 A，立即标记并写入访问序列，递归栈中只有 A。
2. 按 A 的邻接点顺序先选择 D，递归栈变为 A, D。
3. 从 D 继续进入 F，递归栈变为 A, D, F。
4. 从 F 进入 G；G 没有未访问邻接点，随后开始连续回退。
5. G、F、D 都返回后，控制权回到 A，再检查 A 的下一个邻接点。
6. A 继续递归进入 B。
7. 从 B 递归进入 E。
8. E 的邻接点 F 已经访问过，因此跳过这条边并返回。
9. 回到 A 后访问 C；C 指向的 E 和 D 都已经访问过，只做检查，不会再次递归。
10. 递归栈清空后 DFS 结束，访问序列为 A D F G B E C。

DFS 的关键是“先标记，再递归”。如果图中存在环，晚标记会导致递归在环中反复进入同一批顶点。

拓扑排序：处理有向依赖

拓扑排序只适用于有向无环图。它输出一个顶点序列，使每条有向边 u -> v 中的 u 都出现在 v 前面。课程 Baseline 使用 Kahn 算法。

Kahn 拓扑排序：统计入度

1/6

对应过程：

1. 统计每个顶点的入度。
2. 将所有入度为 0 的顶点放入队列。
3. 取出一个入度为 0 的顶点并加入结果。
4. 删除它的出边影响，使相邻顶点入度减 1；有些顶点需要等待多个前驱都输出后才会入队。
5. 新出现的入度为 0 的顶点继续入队，例如 D 和 E 会在 C 输出后同时变为 0。
6. 若最终输出顶点数等于总顶点数，拓扑排序成功；否则说明图中有环。

遍历模块的输入输出

邻接表和邻接矩阵两个模块的公开输入格式一致：

case_count
vertex_count edge_count directed start
from to
...

输出格式：

CASE 1
BFS ...
DFS ...
TOPO_OK 1
TOPO ...

TOPO_OK 为 1 时，TOPO 后面是一种合法拓扑序；TOPO_OK 为 0 时，TOPO 为空。拓扑排序答案可能不唯一，只要每条有向边的前后关系正确即可。

调试重点

• 是否只访问从起点可达的顶点。
• 是否在入队或递归前及时标记已访问。
• 邻接表是否按加边顺序枚举邻接点。
• 邻接矩阵是否按顶点编号从小到大扫描邻接点。
• 拓扑排序是否能正确识别有向环。

运行与作业指导

本页对应邻接表与邻接矩阵中的 BFS、DFS、拓扑排序。完成相关 TODO 后，建议运行 make test-adj-list 和 make test-adj-matrix。

完整的 Baseline、Project、输入输出规范和报告要求见：运行与作业指导。