拓扑排序课程设计报告.doc

.数据结构课程设计设计题目： 有向图拓扑排序 专 业： 信息与计算科学 学 号： 021240616 姓 名： 黄秋实 指导教师： 文 军 2013年11月28日数据结构课程设计 -拓扑排序一 需求分析1.问题描述 本次课程设计题目是：用邻接表构造图 然后进行拓扑排序，输出拓扑排序序列拓扑排序的基本思想为： 1).从有向图中选一个无前驱的顶点输出；2).将此顶点和以它为起点的弧删除；3). 重复1),2)直到不存在无前驱的顶点；4). 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。 2. 拓扑排序 有向图拓朴排序算法的基本步骤如下： 从图中选择一个入度为0的顶点，输出该顶点； 从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度