数据结构(牛小飞)3拓扑排序.ppt
拓扑排序,拓扑排序,复习,小结和作业,复习,图的深度优先搜索：简单路径,图的广度优先搜索：最短路径,图的遍历方法,拓扑排序,问题的引入拓扑排序的定义拓扑排序方法1拓扑排序方法2练习,拓扑排序-问题引入,某学校的部分课程结构,java语言,数据结构,数据库原理,算法分析与设计,操作系统,软件工程,软件测试,如何制定教学计划？,拓扑排序-定义,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,由此所得顶点的线性序列称之为拓扑有序序列。,拓扑排序是对有向无圈图的顶点的一种排序，使得如果存在一条从vi到vj的路径，那么在排序中vj就出现在vi的后面。,显然，如果图中含有圈，那么拓扑排序是不可能的，因为对于圈上的两个顶点v和w，v优先于w同时w又优先于v。,拓扑排序-定义,不能求得它的拓扑有序序列。,因为图中存在一个回路 B,C,D,拓扑排序-举例,可求得拓扑有序序列：A B C D 或 A C B D,拓扑排序-举例,拓扑序列不是唯一的。,可能的拓扑序列为：,v1,v2,v5,v4,v3,v7,v6,v1,v2,v5,v4,v7,v3,v6,拓扑排序-举例,拓扑排序-方法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,v1,v3,v2,v5,v6,v7,v4,0,1,2,3,1,3,2,v1,012,132,v2,10,v5,0,1,v4,0,v3,v7,v3,v7,10,0,v6,v1,v2,v5,v4,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,对有向无环图利用深度优先搜索进行拓扑排序。,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)vertexsv.visited=false;/访问标志初始化 Stack S;/存放顶点，按照出DFS的次序 for(v=0;vvexNum;+v)if(!vertexsv.visited)DFS-T(v);/对尚未访问的顶点调用DFS while(!Empty(S)/输出拓扑排序的结果System.out.print(S.pop();,拓扑排序-方法2,void DFS-T(int v)/从顶点v出发，深度优先搜索遍历连通图 vertexsv.visited=true;for(w=FirstAdjVex(v);w=0;w=NextAdjVex(v,w)if(!vertexsw.visited)DFS-T(w);/对v的尚未访问的邻接顶点w递归调用DFS-T S.push(v);/顶点v的DFS函数执行完毕/DFS-T,拓扑排序-方法2,a,c,g,b,d,h,f,e,写出下图的所有的拓扑序列,拓扑排序-练习,写出下图的所有的拓扑序列,拓扑排序-练习,小结和作业,拓扑排序,1.什么是拓扑排序,3.拓扑排序算法,2.如何进行拓扑排序,作业：P273,9.1,9.3,9.41,
