《数据结构chapter92图的遍历,拓扑排序.ppt

拓扑排序算法首先需要计算各顶点的入度，然后在拓扑排序过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有直接后继顶点的入度减1。为了避免重复检测入度为零的顶点，设立一个栈（或队列），以保存当前所有“入度为零”的顶点 若有向G中所有顶点都被输出，则表明G中没有有向环，拓扑排序成功。若仅输出了部分顶点，G中已不存在入度为0的顶点，则表明G中存在有向环，拓扑排序失败。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 拓扑排序算法实现：设图G的顶点数为n，采用邻接矩阵作为存储结构 1、对各顶点求入度 2、初始化栈S，拓扑序列长度计数器size初始化为0 3、把所有入度为0的顶点入栈S 4、当栈S非空时循环 4.1 输出栈顶元素v并出栈；size++； 4.2 获得所有与v邻接的未被访问的顶点w 4.3 把w的入度减1； 4.4 若w的入度为0则入栈S 直至栈空为止 5、如果sizen，则有向图有环，不存在拓扑序列，拓扑排序失败；否则，拓扑排序成功 6、结束 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 9.7 拓扑排序（续） 拓扑排序算法的时间复杂度分析 关键是，算法在开始时要找出所有入度为0的顶点（同时可知道其它顶点的入度） 当采用邻接矩阵时，算法在开始时找所有入度为0的顶点需要 O (n2)的时间，加上处理边、顶点的时间，总代价为O(n2+e+n)= O (n2) 当采用邻接表时，因为在顶点表的每个顶点中可以有一个字段来存储入度，所以算法在开始时找所有入度为0的顶点只需要O(e)的时间，加上处理边、顶点的时间，总代价为O(n+2e)=O(n+e) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 作业13 概念题：P249，9-3，9-13 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 第二次上机实习——教学计划编制问题 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的。课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。要求： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 数 据 结 构 DATA STRUCTURE, DS  授课教师：郭 艳 授课班级: 191091-4 中国地质大学计算机学院 2011年春 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 上堂课要点回顾 图的基本概念与抽象数据类型定义 连通图、连通分量、生成树 度、入度、出度 图的设计与实现 A C B G1 邻接矩阵 邻接表 0 A 1 B 2 C 2 ∧ 1 ∧ 0 ∧ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 两种图存储结构的比较 设G是顶点数为n，边数为e的有向图， d是顶点v或v1的出度 　基本操作 GraphInitiate(G) IsVertex(G,vertex) InsertVertex(G,vertex) IsEdge(G,v1,v2) InsertEdge(G,v1,v2,weigh