YatDS

Appearance

建图与图表示 ​

建图是把实际问题转化为图算法问题的第一步。图由顶点和边组成：顶点表示对象，边表示对象之间的关系。边可以有方向，也可以带权重。

在写任何图算法之前，先完成建模判断：

  1. 哪些对象应该成为顶点。
  2. 两个顶点之间什么时候有边。
  3. 边是单向还是双向。
  4. 边是否需要权重。
  5. 顶点编号如何和原始问题中的对象互相转换。

以迷宫为例，可通行格子可以成为顶点，上下左右相邻且可走的两个格子之间连边。如果每一步代价相同，这是无权图；如果不同地形代价不同，这是带权图；如果钥匙、机关会改变状态，则顶点可能需要写成 (row, col, state)。

邻接表建图 ​

邻接表为每个顶点保存一个邻接点列表。例如 A: B C 表示从 A 可以到达 B 和 C。它适合稀疏图，因为空间占用接近顶点数加边数。

邻接表建图步骤 1
邻接表建图步骤 2
邻接表建图步骤 3
邻接表建图步骤 4
邻接表建图步骤 5
邻接表建图步骤 6
邻接表建图：确定顶点集合
1/6

每一步的含义：

  1. 先给所有顶点编号，课程 Baseline 中通常使用 0..vertex_count-1。
  2. 读入边 (A, D) 后，把 D 放入 A 的邻接点列表；这一步刻意让输入顺序不等于字母顺序。
  3. 继续读入 (A, B) 和 (A, C) 后，A 的邻接表为 D B C，BFS/DFS 会按这个顺序枚举。
  4. 加入 (B, E) 后，图中出现不同分支汇合到右侧的结构。
  5. 加入 (C, E) 和 (C, D) 后，同一个顶点可能从不同路径到达，遍历实现必须正确去重。
  6. 完整邻接表保留加边顺序，适合检查邻接表实现是否错误地改成了编号顺序。

邻接表实现时要关注两件事：加边是否正确处理有向和无向，枚举邻接点时是否遵守模块约定。图 Baseline 中的邻接表模块要求按加边顺序枚举邻接点。

邻接矩阵建图 ​

邻接矩阵使用 matrix[i][j] 表示从顶点 i 到顶点 j 是否存在边。它适合顶点数较少或边较密的图，因为任意两点是否相邻可以用一次数组访问判断。

邻接矩阵建图步骤 1
邻接矩阵建图步骤 2
邻接矩阵建图步骤 3
邻接矩阵建图步骤 4
邻接矩阵建图步骤 5
邻接矩阵建图步骤 6
邻接矩阵建图：初始化矩阵
1/6

每一步的含义：

  1. 创建 vertex_count * vertex_count 的矩阵，初始值表示没有边。
  2. 读入边 (A, D) 后，设置 matrix[A][D] = 1。
  3. 继续写入 (A, B) 和 (A, C) 后，矩阵中 A 行有多个 1。
  4. 遍历 A 的邻接点时，邻接矩阵会按列编号扫描，因此顺序是 B, C, D，不同于邻接表的 D, B, C。
  5. 写入 C 的交叉边后，矩阵更适合快速判断“某两点是否有边”。
  6. 若是带权图，矩阵单元可以保存权重；没有边时用特殊值表示。

邻接矩阵和邻接表的核心差异在于“查边”和“枚举邻接点”的代价不同。邻接矩阵查边快，但枚举一个顶点的邻接点需要扫描整行；邻接表枚举邻接点直接，但判断任意两点是否相邻通常需要查找列表。

Baseline 任务：邻接表图 ​

目录：src/Graph/Baseline/src/adjacency_list/

需要在 graph.cpp 中补全：

  • AdjListBFS：从 start 出发做广度优先遍历，将访问顺序写入 order[]，将访问到的顶点数量写入 count。
  • AdjListDFS：使用递归完成深度优先遍历，每个顶点只访问一次，将访问顺序写入 order[]。
  • AdjListTopologicalSort：使用入度数组和队列完成 Kahn 拓扑排序；有向无环图返回 1，有环图返回 0；对无向图调用时返回 0 并将 count 置为 0。

公开测试覆盖有向无环图、有向环图、无向图、不连通图和单顶点图。运行方式：

sh
make test-adj-list

提交前检查：

  • BFS 是否正确使用队列。
  • DFS 是否正确标记已访问顶点。
  • 拓扑排序是否正确维护入度。
  • 有环图是否不会输出完整拓扑序。
  • 不连通图是否不会误访问其他连通分量。

Baseline 任务：邻接矩阵图 ​

目录：src/Graph/Baseline/src/adjacency_matrix/

需要在 graph.cpp 中补全：

  • AdjMatrixBFS：从 start 出发做广度优先遍历，按顶点编号从小到大扫描邻接点，将访问顺序写入 order[]。
  • AdjMatrixDFS：使用递归完成深度优先遍历，按顶点编号从小到大扫描邻接点。
  • AdjMatrixTopologicalSort：根据矩阵统计入度，使用队列维护入度为 0 的顶点；有向无环图返回 1，有环图返回 0；对无向图调用时返回 0 并将 count 置为 0。

公开测试覆盖有向无环图、有向环图、无向图、不连通图和单顶点图。运行方式：

sh
make test-adj-matrix

提交前检查：

  • 扫描邻接点时是否按编号从小到大处理。
  • BFS 是否正确维护队列。
  • DFS 是否正确避免重复访问。
  • 拓扑排序是否正确统计和更新入度。
  • 能否说明邻接矩阵和邻接表在时间复杂度上的区别。

建图检查表 ​

  • 顶点编号是否连续且从 0 开始。
  • 有向边和无向边是否区分清楚。
  • 无权边和带权边是否区分清楚。
  • 不可通行或不存在的关系是否没有误加边。
  • Project 中是否能从场景数据稳定生成同一张图。
  • 是否能从算法输出反向解释到原始问题。

运行与作业指导 ​

本页对应 Baseline 中的邻接表与邻接矩阵模块。完成相关 TODO 后，建议运行 make test-adj-list 和 make test-adj-matrix。

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