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

1、拓扑排序,拓扑排序,复习,小结和作业,复习,图的深度优先搜索：简单路径,图的广度优先搜索：最短路径,图的遍历方法,拓扑排序,问题的引入 拓扑排序的定义 拓扑排序方法1 拓扑排序方法2 练习,拓扑排序-问题引入,某学校的部分课程结构,java语言,数据结构,数据库原理,算法分析与设计,操作系统,软件工程,软件测试,如何制定教学计划？,拓扑排序-定义,按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。,由此所得顶点的线性序列称之为拓扑有序序列。,拓扑排序是对有向无圈图的顶点的一种排序，使得如果存在一条从vi到vj的路径，那么在排

2、序中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、重复上述两步，直至图空，或者图不

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

4、(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,0 1 2,1 3 2,v2,1 0,v5,0,1,v4,0,v3,v7,v3,v7,1 0,0,v6,v1,v2,v5,v4,p274, 9.2 队列和栈是否都能实现拓扑排序？,拓扑排序-方法1,void topsort( ) throw

5、s 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( )

6、/如果队列非空 . ,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,拓扑排序

7、-方法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