王赵彬-0804011020-AOV网拓扑排序.docVIP

合肥学院 计算机科学与技术系 课程设计报告 2009～2010学年第二学期 课程 数据结构与算法 课程设计名称 AOV网拓扑序列生成 学生姓名 王赵彬 学号 0804011020 专业班级 08计科(1)班 指导教师 吕刚、胡春琳 2010年06月 一、问题分析和任务定义 1、题目： 对于给定的AOV网，要求实现所有的拓扑排序。 2、要求和任务： 在这个问题中，要解决的问题是：任意给出的一个AOV图，都要实现它所有的拓扑排序序列。要解决这个问题，首先，要选取一种数据结构来存放这个AOV网中每个顶点的各种信息，包括在图中的位置和每个顶点的入度变化。其次，要采取一种什么样的思想，使算法能输出所有的拓扑排序。通过独立解决这些问题，提高在数据结构的逻辑特性和表示、数据结构的选择应用、算法的设计及其实现等方面的能力，加深对课程基本内容的理解和综合运用，提高分析和解决实际问题的能力，达到理论和实际应用相结合。 3、原始数据输入、输出格式： 输入格式：原始数据要求输入顶点数目、边的数目、每条边的起始点和终点在邻接表中的位置。例如图1所示的图输入如下： please input vexnum:5 please input arcnum:4 请依次输入每条弧的起点和终点序号： 0 1 0 3 2 3 3 4 输出格式：输出的是所有拓扑排序的种数，和每种排序的具体情况。 例如：v0 v1 v2 v3 v4 v0 v2 v1 v3 v4 ………………… v2 v0 v3 v4 v1 该AOV网有7种拓扑排序序列。 4、算法测试用例设计： 1〉设计一个简单的AOV网，如图1，应该输出7种拓扑排序。 2〉设计一个有回路的图，如图2，结果应该是不能进行拓扑排序。 3〉设计一个稍复杂的AOV网，如图3，应该输出 74 种拓扑排序。 图1. 简单的AOV网测试用例 图2。一个有回路的图 图3.一个稍复杂的AOV网 拓扑排序演示：（其中一个序列的） 图4 拓扑排序过程 注意： ①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 ②若图中存在有向环，则不可能使顶点满足拓扑次序。 ③一个DAG的拓扑序列通常表示某种方案切实可行。 【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。 ④一个DAG可能有多个拓扑序列。 【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7， C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。 ⑤当有向图中存在有向环时，拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示，有向边v3，vl和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。 二、数据结构的选择和概要设计 1、数据结构 本问题中，我将采用三种数据结构，邻接表，队列，数组。 1邻接表：邻接表是图的链式存储结构，在邻接表的存储结构中，图中的每个顶点对应一个单链表。从拓扑排序的步骤个方法来看，在整个排序过程中需要频繁地检查顶点的前驱以及作删除顶点和弧的操作、恢复顶点和顶点前驱入度的操作。所以，可以采用邻接表作为有向无环图的存储结构。 为了快速的判断顶点是否有前驱，可以在表头结点中增加一个“入度域（indegree）”用来指示顶点当前的入度。当indegree域的值为0时，表明该顶点没有前驱，可以加入到结果序列中。而删除顶点及以它为尾的弧的操作，可以通过把该顶点的所有邻接点的入度域减一来完成，恢复则入度域加一。 邻接表的定义如下： typedef struct ARCNODE{ int adjvex; //邻接点的位置 ARCNODE *nextarc;//指向下一个结点 }ARCNODE; //邻接表中的结点类型 typedef struct VEXNODE{ int vexdata; //顶点信息 int indegree; //每个顶点的入度 ARCNODE *firstarc; //指向第一个邻接结点 }VEXNODE,AdjList[MAX];//邻接表的表头结点类型 typedef s