基于紧缩图的拓扑排序.doc

2013-1-18 东北大学信息科学与工程学院 数据结构课程设计报告 题目 基于紧缩图的拓扑排序 课题组长 刘正皓 课题组成员 杨绍伟 杨冰 专业名称 计算机科学与技术 班级 计1208 指导教师 杨雷 2014 年 1月 课程设计任务书 题目： 基于紧缩图的拓扑排序 问题描述： 紧缩邻接表将图的每个顶点的邻接表紧凑的存储在两个向量list和h中。其中向量list依次存储顶点0，1，…，n-1的邻接顶点。向量单元h[i]存储顶点i的邻接表在向量list中的起始位置。 设计要求： 设计基于紧缩图的邻接表的拓扑排序程序。 （1）采用STL的图、栈等数据结构。 （2）实现STL的紧缩邻接表结构图类。 （3）实现紧缩图的邻接表结构的拓扑排序。 　　　　　　　　　　　　 指导教师签字： 2013年12月15日 目录 1 课题概述 1 1.1 课题任务 1 1.2 课题原理 1 1.3 相关知识 2 2 需求分析 2 2.1 课题调研 3 2.2 用户需求分析 3 3 方案设计 4 3.1 总体功能设计 4 3.2 数据结构设计 4 3.3 函数原型设计 5 3.4 主算法设计 5 3.5 用户界面设计 5 4 方案实现 6 4.1 开发环境与工具 6 4.2 程序设计关键技术 6 4.3 个人设计实现（按组员分工） 4.3.1 刘正皓设计实现 7 4.3.2 杨绍伟设计实现 11 4.3.3 杨冰设计实现 12 5 测试与调试 13 5.1 个人测试（按组员分工） 13 5.1.1 刘正皓测试 13 5.1.2 杨绍伟测试 16 5.1.3 杨冰测试 19 5.2 组装与系统测试 20 5.3 系统运行 20 6 课题总结 21 6.1 课题评价 22 6.2 团队协作 22 6.3 个人设计小结（按组员分工） 22 6.3.1 刘正皓设计小结 22 6.3.2 杨绍伟设计小结 22 6.3.3 杨冰设计小结 23 7 附录A 课题任务分工 50 A-1 课题程序设计分工 50 A-2 课题报告分工 51 附录B 课题设计文档（光盘） B-1课程设计报告（电子版） B-2源程序代码（*.H，*.CPP） B-3工程与可执行文件） B-4屏幕演示录像文件（可选） 52 附录C 用户操作手册（可选） 31 C.1 运行环境说明 31 C.2 操作说明 31 1课题概述 课题任务 以STL类模板实现紧缩图邻接表的拓扑排序 课题原理 将图的结点存入两个向量之中，List用以存放全部结点，H用以存放结点间的相互关联关系，通过输入一系列结点信息及其发出弧的信息，确定每个结点的入度，进行拓扑排序序列的输出。拓扑排序算法bool TopologicalSort(ALGraph G) 中，先输出入度为零的顶点，而后输出新的入度为零的顶点，此操作可利用栈实现。该算法大体思想为： 1)遍历有向图各顶点的入度，将所有入度为零的顶点入栈； 2)栈非空时，输出一个顶点，并对输出的顶点数计数； 3)该顶点的所有邻接点入度减一，若减一后入度为零则入栈； 4)重复2)、3)，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环。 流程图如下： 相关知识 STL中的向量模板，通过栈实现图的拓扑排序。 2需求分析 2.1 课题调研 通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R,且R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 比较简单的理解：偏序是指集合中只有部分成员可以比较，全序是指集合中所有的成员之间均可以比较。 用户可以通过输入每个结点和弧的信息讲结点放入图中，再通过栈实现拓扑排序序列的输出； 可以在拓扑排序时同时输出结点信息； 该程序应该有对用户错误输入的辨别纠错功能； 程序应具有演示功能和调试功能。 程序应具有良好的人机接口。程序应能所见即所得的输入数据。这就如同在VS中可视化的开发图形界面一样。程序应能精确的输入数据。每一个点的坐标，每条弧的权值都应能由用户精确控制。这就如同在VS中用代码编辑用户界面一样。 程序应能友好的展现结果。 该程序可以显示时间。 程序应能显示制作者的信息。 3方案设计 3.1 总体功能设计 拓扑排序 参数说明 功能描述 bool TopologicalSort(Graph v,vector int inde