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

拓扑排序算法首先需要计算各顶点的入度，然后在拓扑排序过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有直接后继顶点的入度减1。为了避免重复检测入度为零的顶点，设立一个栈（或队列），以保存当前所有“入度为零”的顶点 若有向G中所有顶点都被输出，则表明G中没有有向环，拓扑排序成功。若仅输出了部分顶点，G中已不存在入度为0的顶点，则表明G中存在有向环，拓扑排序失败。 拓扑排序算法实现：设图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、结束 9.7 拓扑排序（续） 拓扑排序算法的时间复杂度分析 关键是，算法在开始时要找出所有入度为0的顶点（同时可知道其它顶点的入度） 当采用邻接矩阵时，算法在开始时找所有入度为0的顶点需要 O (n2)的时间，加上处理边、顶点的时间，总代价为O(n2+e+n)= O (n2) 当采用邻接表时，因为在顶点表的每个顶点中可以有一个字段来存储入度，所以算法在开始时找所有入度为0的顶点只需要O(e)的时间，加上处理边、顶点的时间，总代价为O(n+2e)=O(n+e) 作业13 概念题：P249，9-3，9-13 第二次上机实习——教学计划编制问题 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的。课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。要求： 要求： （1）输入参数包括：学期总数，一学期的学分上限，每门课的属性，包括课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。 （2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。 （3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。 * Abbr. DS School of Computer，China University of Geosciences 这门课是数据结构A，我的名字是，我的email是 本人于2001年6月至2002年10月参加校CAI项目“《数据结构》网络课程”的开发，并于2004.6获校优秀教学成果二等奖；2005、2006年讲授数据结构考研辅导课。 在本课程中，你将学到高级编程技巧，包括数据结构、抽象数据类型、查找排序算法，也将体会到软件工程——设计和编写大型程序 * 对图G1和G2，其邻接表如下（无权值，故可不要权值域weight） * 已知图G(V,E)和V(G)的一个顶点vi, 当G是连通图时，则从图中的任一顶点出发，按一定规则顺着某些边去访问图中其余顶点，使每一个顶点被访问一次且仅被访问一次。 图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径的基础。 遍历图要比遍历树复杂得多，因为图中的某一个顶点均可能与图中其余顶点相邻接，即图中允许有回路，所以当从某一顶点出发，在访问了其他顶点后有可能顺着某一些边又回到了该顶点。因此，在遍历图时，必须对已被访问过的顶点进行标志，以免重复地进行访问。 从深度优先有哪些信誉好的足球投注网站遍历连通图的过程类似于树的先根遍历; 再从V’出发递归地按照深度优先的方式遍历， 当遇到一个所有邻接于它的顶点都被访问过了的顶点U时，则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点W， 再从W出发递归地按照深度优先的方式遍历， 最后，当任何已被访问过的顶点都没有未被访问的相邻顶点时，则遍历结束。 * * 后四条语句与书不同，更为精简。 visit(v); /*访问顶点v，书中为输出顶点信息*/ 这是递归函数。 void DFS(Graph G, int V){ //深度优先有哪些信誉好的足球投注网站算法实现 G.Mark[V]= VISITED; //访问顶点V，并标记其标志位 PreVisit(G, V); //访问V for(Edge e=G. FirstEdge(V); G.IsEdge(e); e=G. NextEdge(e)) //访问