数据结构(牛小飞)3拓扑排序

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,拓扑排序,拓扑排序,复习,小结和作业,复习,图的深度优先搜索：,简单路径,图的广度优先搜索：,最短路径,图的遍历方法,v,1,v,3,v,2,v,5,v,6,v,7,v,4,拓扑排序,问题的引入,拓扑排序的定义,拓扑排序方法,1,拓扑排序方法,2,练习,拓扑排序,-,问题引入,某学校的部分课程结构,java,语言,数据结构,数据库原理,算法分析与设计,操作系统,软件工程,软件测试,如何制定教学计划,？,拓扑排序,-,定义,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,由此所得顶点的线性序列称之为,拓扑有序序列,。,拓扑排序是,对有向无圈图的顶点的一种排序，使得如果存在一条从,v,i,到,v,j,的路径，那么在排序中,v,j,就出现在,v,i,的后面。,显然，,如果图中含有圈，那么拓扑排序是不可能的,，因为对于圈上的两个顶点,v,和,w,，,v,优先于,w,同时,w,又优先于,v,。,拓扑排序,-,定义,B,D,A,C,不能求得它的拓扑有序序列。,因为图中存在一个回路,B,C,D,拓扑排序,-,举例,B,D,A,C,可求得拓扑有序序列,：,A B C D,或,A C B D,拓扑排序,-,举例,拓扑序列不是唯一的,。,v,1,v,3,v,2,v,5,v,6,v,7,v,4,可能的拓扑序列为：,v,1,v,2,v,5,v,4,v,3,v,7,v,6,v,1,v,2,v,5,v,4,v,7,v,3,v,6,拓扑排序,-,举例,拓扑排序,-,方法,1,1,、从有向图中选取一个没有前驱的顶点，并输出,;,2,、从有向图中删去此顶点以及所有以它为尾的弧,;,3,、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,a,c,g,b,d,h,f,e,b,h,a,c,d,g,f,e,拓扑序列,：,拓扑排序,-,方法,1,拓扑排序,-,方法,1,1,、从有向图中选取一个没有前驱的顶点，并输出,;,2,、从有向图中删去此顶点以及所有以它为尾的弧,;,3,、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。,入度为,0,的顶点,弧头顶点的入度减,1,void topsort(),for(int counter=0;counterNUM_VERTICES;counter+),Vertex v=,findNewVertexOfIndegreeZero,();,/,寻找一个尚未被分配拓扑编号的入度为,0,的顶点,if(v=null),/,图中有圈,throw new CycleFoundException();,v.topNum=counter;,/,顶点,v,的拓扑编号,for each Vertex w adjacent to v,w.indegree-;,/,弧头顶点的入度减,1,拓扑排序,-,方法,1,v,1,v,3,v,2,v,5,v,6,v,7,v,4,出队前的入度,顶点,1 2 3 4 5 6 7,v,1,v,2,v,3,v,4,v,5,v,6,v,7,入队,出队,0,1,2,3,1,3,2,v,1,0,1,2,1,3,2,v,2,1,0,3,2,1,v,5,0,1,3,1,v,4,2,0,0,v,3,v,7,v,3,v,7,1,0,0,v,6,v,1,v,2,v,5,v,4,p274,9.2,队列和栈是否都能实现拓扑排序？,拓扑排序,-,方法,1,void topsort()throws CycleFoundException,Queue q=new Queue();,int counter=0;,/,对输出顶点计数,for each Vertex v,if(v.indegree=0),/,顶点的入度为,0,，则入队,q.enqueue(v);,while(!q.isEmpty(),/,如果队列非空,if(counter!=NUM_VERTICES),/,有圈,throw new CycleFoundException();,拓扑排序,-,方法,1,void topsort()throws CycleFoundException,.,while(!q.isEmpty(),/,如果队列非空,.,Vertex v=q.dequeue();,v.topNum=+counter;,for each Vertex w adjacent to v,if(-w.indegree=0),q.enqueue(w);,拓扑排序,-,方法,1,总的时间复杂度：,O(n+e),算法分析：,拓扑排序,-,方法,1,a,c,g,b,d,h,f,e,b,h,a,c,d,g,f,e,拓扑序列,：,拓扑排序,-,方法,2,对有向无环图利用,深度优先搜索,进行拓扑排序,。,a,c,g,b,d,h,f,e,b,h,a,c,d,g,f,e,此图的一个拓扑序列为：,a,c,g,b,d,h,f,e,退出,DFS,函数顺序：,e,f,g,d,c,a,h,b,拓扑排序,-,方法,2,最先退出,DFS,函数的顶点是出度为零的顶点，为拓扑排序序列中最后一个顶点。,因此，按退出,DFS,函数的先后记录下来的顶点序列即为逆向的拓扑排序序列。,结论：,拓扑排序,-,方法,2,void,DFS-,ToplogicalSort,(),int,v,；,for,(v=0;vvexNum;,+,v),vertexs,v,.visited,=,false,;,/,访问标志初始化,Stack S;,/,存放顶点，按照出,DFS,的次序,for,(v=0;v=0;w=NextAdjVex(v,w),if,(!,vertexs,w,.visited,)DFS-T(w);,/,对,v,的尚未访问的邻接顶点,w,递归调用,DFS-T,S.push(v);,/,顶点,v,的,DFS,函数执行完毕,/DFS-T,拓扑排序,-,方法,2,a,c,g,b,d,h,f,e,写出下图的所有的拓扑序列,拓扑排序,-,练习,写出下图的所有的拓扑序列,拓扑排序,-,练习,v,1,v,3,v,2,v,5,v,6,v,7,v,4,小结和作业,拓扑排序,1.,什么是拓扑排序,3.,拓扑排序算法,2.,如何进行拓扑排序,作业：,P273,9.1,9.3,9.41,