图结构

图用于描述对象之间的关系。课程中的图部分采用“算法工具箱 + 综合应用”的设计：Baseline 负责实现可复用的图算法接口，Project 负责把迷宫场景建模成图，再调用 Baseline 中的接口完成求解。

这部分作业的重点不是背固定样例，而是训练两类能力：

• 能把实际对象抽象成顶点，把对象之间的关系抽象成边。
• 能根据边的方向、权重和目标任务，选择合适的图存储结构和算法接口。

学习路径

1. 建图与图表示：从实际问题抽象顶点和边，分别学习邻接表和邻接矩阵。
2. 图遍历：使用 BFS、DFS 和拓扑排序处理可达性、搜索顺序和依赖关系。
3. 最短路径：用无权最短路径和 Dijkstra 计算从起点到其他顶点的最小代价。
4. 最小生成树：用 Prim 和 Kruskal 在带权无向图中选择低成本连接方案。
5. 综合项目：把迷宫文本转化成图或状态图，并调用 Baseline 接口解决实际问题。
6. 运行与作业指导：查看 Baseline、Project 和实验报告的编译运行、输入输出和提交要求。

运行与作业指导

Baseline 和 Project 的完整运行步骤、输入输出规范、报告要求和提交前检查见：运行与作业指导。

Baseline 作业

Baseline 是后续 Project 可以直接调用的图算法工具箱。你需要补全 6 个小模块中的 TODO(student) 代码。

模块	目录	需要完成
邻接表图	adjacency_list/	BFS、DFS、拓扑排序
邻接矩阵图	adjacency_matrix/	BFS、DFS、拓扑排序
无权最短路径	unweighted_shortest_path/	基于 BFS 的单源最短路径
Dijkstra	dijkstra/	非负权图单源最短路径
Prim	mst_prim/	最小生成树
Kruskal	mst_kruskal/	并查集与最小生成树

建议按上表顺序完成。邻接表和邻接矩阵先帮助你理解“图如何被存储”，无权最短路径和 Dijkstra 进一步处理“路径代价”，Prim 和 Kruskal 则处理“如何用较低成本连接全部顶点”。

教程中的轮播图既展示基本步骤，也刻意加入了分支、交叉边、等权边和不同代价路径，用来区分不同图表示和算法的适用场景。

统一约定

• 顶点编号为 0..vertex_count-1。
• directed = 1 表示有向图，directed = 0 表示无向图。
• 不可达距离用 -1 表示。
• 没有前驱的顶点用 -1 表示。
• 不要修改头文件中已经给出的函数签名。
• 不要在算法函数里直接读写文件；读入和打印由测试入口负责。
• 不要把公开样例硬编码进算法函数。

测试方式

进入 src/Graph/Baseline/ 目录后运行：

make
make test-all

make test-all 会编译并运行全部 6 个模块，输出每个模块的公开测试结果。也可以只运行单个模块：

make test-adj-list
make test-adj-matrix
make test-shortest-path
make test-dijkstra
make test-prim
make test-kruskal

每个模块目录下都有 test.in 和 test.out。测试程序读取 test.in，调用你补全的接口，再把结果打印到标准输出。test.out 是一种合法输出示例；对于拓扑排序、最短路径前驱和最小生成树，合法答案可能不唯一，测试会检查输出是否合法。

输入输出总览

邻接表、邻接矩阵、无权最短路径的输入格式：

case_count
vertex_count edge_count directed start_or_source
from to
...

Dijkstra 的输入格式：

case_count
vertex_count edge_count directed source
from to weight
...

Prim 和 Kruskal 的输入格式：

case_count
vertex_count edge_count
from to weight
...

输出字段的含义：

字段	含义
BFS	BFS 的访问顺序
DFS	DFS 的访问顺序
TOPO_OK	是否存在合法拓扑序
TOPO	一种合法拓扑序
DIST	起点到每个顶点的最短距离
PREV	最短路径树中的前驱顶点
OK	是否成功得到最小生成树
TOTAL	最小生成树总权重
EDGE_COUNT	输出的生成树边数

Project 与 Baseline 的关系

Baseline 的任务是“把算法做对”，Project 的任务是“把问题建对”。在迷宫 Project 中，你不会直接拿到一张图，而是拿到一个场景。你需要先判断哪些位置或状态应该成为顶点，再判断什么时候两个顶点之间有边，最后选择合适的 Baseline 接口求解。

完成本章后，你应该能够回答：

• 顶点代表什么对象。
• 边代表什么关系。
• 边是否有方向。
• 边是否有权重。
• 应该使用邻接表还是邻接矩阵。
• 应该调用 BFS、Dijkstra、Prim 还是 Kruskal。

这也是图部分 Project 的核心评分点。