东北大学数据结构课程设计：紧缩图邻接表的拓扑排序

"这篇文档是东北大学信息科学与工程学院数据结构课程设计报告，主题是基于紧缩图的邻接表实现拓扑排序。报告详细介绍了设计任务、原理、需求分析、方案设计、实现过程、测试与调试以及课题总结。" 在计算机科学中，拓扑排序是对有向无环图(DAG)的一种排序方法，它将图中的所有节点排成一个线性序列，使得对于图中每一条有向边 (u, v)，节点 u 都在这个序列中出现在节点 v 之前。这个任务是针对紧缩图的邻接表结构来实现拓扑排序。 紧缩图的邻接表是一种优化的图存储方式，它将每个顶点的邻接表紧凑地存储在两个向量 `list` 和 `h` 中。向量 `list` 依次存储了从0到n-1的所有顶点的邻接顶点，而向量 `h[i]` 存储顶点 i 的邻接表在向量 `list` 中的起始位置。这种方式减少了内存空间的浪费，提高了访问效率。 设计要求包括以下几点： 1. 使用标准模板库(STL)提供的数据结构，如图、栈等。这允许利用C++标准库的高效实现来构建程序。 2. 实现一个基于STL的紧缩邻接表结构的图类。这个类应该能够方便地表示和操作图的节点和边。 3. 实现拓扑排序算法。这涉及到遍历图的节点，找出没有前驱(即没有入边)的节点并将其添加到排序序列，然后递归地处理剩余的图。 在实现过程中，可能涉及以下步骤： - 初始化图类，包含节点和边的表示。 - 检测图是否为有向无环图，因为只有DAG才能进行拓扑排序。 - 使用栈或队列来处理没有前驱的节点。 - 对于每个节点，检查其所有的邻接节点，如果邻接节点的入度减一后变为0，则将其加入待处理列表。 - 重复上述过程，直到所有节点都被处理。 测试与调试部分会包括对各个模块的单元测试，以及整体系统的集成测试，确保拓扑排序算法的正确性。最后，课题总结部分会对整个项目进行评价，包括团队协作的效果和个人设计的小结。 附录部分包含了课题任务的分工、程序设计分工、报告分工，以及设计文档、源代码、可执行文件和可能的屏幕演示录像，便于评审和后续参考。 这份报告涵盖了从问题理解、设计实现到测试验证的全过程，旨在通过实践巩固和提升学生对数据结构和算法的理解，特别是邻接表和拓扑排序的应用。