运行与作业指导

图模块采用“Baseline 工具箱 + Project 综合应用”的作业结构。Baseline 先训练图表示、遍历、最短路和最小生成树接口；Project 再要求你把迷宫问题建模成图，并调用已经完成的 Baseline 接口解决实际任务。

Baseline 指导

Baseline 位于 src/Graph/Baseline/。你需要补全 Baseline/src/ 下 6 个模块中的 TODO(student)，不要修改头文件中已经给出的函数签名。

模块	目录	主要接口
邻接表图	src/adjacency_list/	AdjListBFS、AdjListDFS、AdjListTopologicalSort
邻接矩阵图	src/adjacency_matrix/	AdjMatrixBFS、AdjMatrixDFS、AdjMatrixTopologicalSort
无权最短路径	src/unweighted_shortest_path/	ShortestPath
Dijkstra	src/dijkstra/	Dijkstra
Prim	src/mst_prim/	Prim
Kruskal	src/mst_kruskal/	DisjointSet、Kruskal

建议完成顺序是邻接表、邻接矩阵、无权最短路径、Dijkstra、Prim、Kruskal。前两个模块帮助你理解图如何存储，中间两个模块处理路径代价，最后两个模块处理带权无向图的低成本连接。

Baseline 编译与测试

进入 Baseline 目录后运行：

cd src/Graph/Baseline
make
make test-all

make test-all 会编译并运行全部公开测试。也可以只运行某个模块：

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

清理编译产物：

make clean

每个模块目录下都有 test.in 和 test.out。测试程序读取 test.in，调用你补全的接口，再把机器可比对的结果打印到标准输出。你也可以手动传入输入文件，例如：

./test_dijkstra src/dijkstra/test.in

test.out 是一种合法输出示例。拓扑排序、最短路径前驱和最小生成树在某些图上可能不唯一，测试会检查结果是否合法，而不是只比较唯一字符串。

Baseline 输入输出规范

邻接表、邻接矩阵、无权最短路径使用：

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	输出的生成树边数

提交前确认：make test-all 通过，没有把公开样例硬编码进算法函数，没有在算法函数里直接读写文件，也没有改动公开接口来绕过测试。

Project 指导

Project 位于 src/Graph/Project/，主题是终端迷宫寻路。你拿到的不是现成图，而是固定迷宫地图；你需要自己判断顶点、边、边权和算法接口。

迷宫字符含义：

字符	含义
#	墙，不能通过
.	普通道路，进入代价为 1
1-9	数字地形，进入代价等于数字
S	起点
K	钥匙点，任务 3 和任务 4 要求先经过该点
D	危险门，进入代价为 8，不需要 K 解锁
E	终点

固定迷宫如下：

#####################
#S#.....#...........#
#.#.###.#.####.####.#
#.#.#.#...#.......#.#
#.#.#.#####.#######.#
#.#.....#...#.....#.#
#.##..###.###.###.#.#
#.#...#1112.....#.#.#
#.#.###.###.#.#####.#
#..1#..D#.#.#...#...#
###.#.###...#####.###
#..9#.#.#K......#.#.#
#2###.#.#.#####.#.#.#
#...4.#.......#....E#
#####################

每个非墙格子可以抽象成一个顶点。上下左右相邻的可走格子之间可以抽象成边。若目标是最少移动次数，通常建无权图并调用无权最短路径；若目标是总代价最低，通常建带权图并调用 Dijkstra。 本 Project 中 K 只是必经点，不改变迷宫通行规则；D 始终可通行，只是在带权任务中进入代价为 8。

Project 编译与运行

进入 Project 目录后运行：

cd src/Graph/Project
make
./graph_project

如果环境没有 make，可以手动编译：

g++ -std=c++17 -Wall project.cpp ../Baseline/src/adjacency_list/graph.cpp ../Baseline/src/adjacency_matrix/graph.cpp ../Baseline/src/unweighted_shortest_path/shortest_path.cpp ../Baseline/src/dijkstra/dijkstra.cpp ../Baseline/src/mst_prim/mst_prim.cpp ../Baseline/src/mst_kruskal/mst_kruskal.cpp -o graph_project

然后运行：

./graph_project

Project 中重点完成这些函数：

• BuildUnweightedMazeGraph(graph)：建立适合最少步数任务的无权图。
• BuildWeightedMazeGraph(graph)：建立适合最低代价任务的带权图。
• RebuildPath(start, goal, prev)：根据 prev[] 还原路径。
• FindRouteFromStartToExit(start, goal)：求 S 到 E 的最少移动路线。
• FindLowCostRouteFromStartToExit(start, goal)：求 S 到 E 的最低代价路线。
• FindKeyThenExitRoute(start, key, goal)：先到 K 再到 E，目标是最少移动次数。
• FindLowCostKeyThenExitRoute(start, key, goal)：先到 K 再到 E，目标是最低总代价。

Project 中不应重新实现完整 BFS 或 Dijkstra。更合理的工作流是先建图，再调用 Baseline 中已经测试通过的接口。

报告指导

实验报告重点说明你的建模和算法选择，而不是粘贴完整代码。报告至少包括：

1. Baseline 完成情况：完成了哪些模块，每个模块的核心思路是什么。
2. Project 问题分析：每个功能任务本质上对应什么图问题。
3. 建图方式：顶点代表什么，边代表什么，边权如何定义。
4. 接口调用：每个任务调用了哪些 Baseline 接口，为什么适合。
5. 运行结果：给出编译命令、运行输出，并解释路径、步数或总代价。
6. 反思总结：Baseline 工具箱如何帮助 Project，哪些边界情况需要注意。

报告建议使用 Markdown 或 PDF。代码只需要贴关键片段，例如建图和接口调用部分，不需要贴完整 Baseline 算法实现。

提交前检查

• Baseline 能在 src/Graph/Baseline/ 下执行 make test-all。
• Project 能在 src/Graph/Project/ 下编译运行。
• 公开接口签名没有被修改。
• Project 复用了 Baseline 接口，而不是绕过接口重写算法。
• 输出能解释为路径、步数、总代价或不可达判断。
• 报告能说明为什么某个任务选择 BFS、Dijkstra 或其他图算法。