数据结构拓扑排序课件

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

2、。 显然，如果图中含有圈，那么拓扑排序是不可能的，因为对于圈上的两个顶点v和w，v优先于w同时w又优先于v。拓扑排序-定义BDAC不能求得它的拓扑有序序列。因为图中存在一个回路 B, C, D拓扑排序-举例BDAC可求得拓扑有序序列： A B C D 或 A C B D拓扑排序-举例 拓扑序列不是唯一的。v1v3v2v5v6v7v4可能的拓扑序列为：v1,v2,v5,v4,v3,v7,v6v1,v2,v5,v4,v7,v3,v6拓扑排序-举例 拓扑排序-方法11、从有向图中选取一个没有前驱的顶点，并输出;2、从有向图中删去此顶点以及所有以它为尾的弧;3、重复上述两步，直至图空，或者图不空但找不

3、到无前驱的顶点为止。acgbdhfebhacdgfe拓扑序列： 拓扑排序-方法1 拓扑排序-方法11、从有向图中选取一个没有前驱的顶点，并输出;2、从有向图中删去此顶点以及所有以它为尾的弧;3、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。入度为0的顶点弧头顶点的入度减1void topsort( ) for(int counter=0;counterNUM_VERTICES;counter+) Vertex v=findNewVertexOfIndegreeZero( ); /寻找一个尚未被分配拓扑编号的入度为0的顶点if(v=null) /图中有圈 throw new Cyc

4、leFoundException(); v.topNum=counter; /顶点v的拓扑编号for each Vertex w adjacent to v w.indegree-; /弧头顶点的入度减1 拓扑排序-方法1v1v3v2v5v6v7v4出队前的入度顶点 1 2 3 4 5 6 7 v1 v2 v3 v4 v5 v6 v7入队出队0123132v1012132v210321v50131v4200v3,v7v3v7100v6v1v2v5v4p274, 9.2队列和栈是否都能实现拓扑排序？ 拓扑排序-方法1void topsort( ) throws CycleFoundExcepti

5、on 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( ); 拓扑排序-方法1void topsort( ) throws CycleFoundException . while (!q.isEmpty( ) /如果队列非空 .Vertex v=q.d

6、equeue( );v.topNum=+counter;for each Vertex w adjacent to vif(-w.indegree=0)q.enqueue(w); 拓扑排序-方法1总的时间复杂度：O(n+e)算法分析： 拓扑排序-方法1acgbdhfebhacdgfe拓扑序列： 拓扑排序-方法2对有向无环图利用深度优先搜索进行拓扑排序。acgbdhfebhacdgfe 此图的一个拓扑序列为：acgbdhfe退出DFS函数顺序：efgdcahb 拓扑排序-方法2最先退出DFS函数的顶点是出度为零的顶点，为拓扑排序序列中最后一个顶点。因此，按退出DFS函数的先后记录下来的顶点序列即为逆向的拓扑排序序列。结论： 拓扑排序-方法2void DFS-ToplogicalSort () int v； for (v=0; vvexNum; +v) vertexsv.visited = false; / 访问标志初始化 Stack S; /存放顶点，按照出DFS的次序 for (v=0; v=0; w=NextAdjVex(v,w) if (!vertexsw.visited) DFS-T(w); / 对v的尚未访问的邻接顶点w递归调用DFS-T S.push(v); /顶点v的DFS函数执行完毕 / DFS-T 拓扑排序-方法2acgbdhfe写出下图的所有的