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

上传人:牧羊曲112 文档编号:4980162 上传时间:2023-05-27 格式:PPT 页数:25 大小:270.50KB
返回 下载 相关 举报
数据结构(牛小飞)3拓扑排序.ppt_第1页
第1页 / 共25页
数据结构(牛小飞)3拓扑排序.ppt_第2页
第2页 / 共25页
数据结构(牛小飞)3拓扑排序.ppt_第3页
第3页 / 共25页
数据结构(牛小飞)3拓扑排序.ppt_第4页
第4页 / 共25页
数据结构(牛小飞)3拓扑排序.ppt_第5页
第5页 / 共25页
点击查看更多>>
资源描述

《数据结构(牛小飞)3拓扑排序.ppt》由会员分享,可在线阅读,更多相关《数据结构(牛小飞)3拓扑排序.ppt(25页珍藏版)》请在三一办公上搜索。

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

2、就出现在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(v=null)/图中有圈 thr

4、ow 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

5、 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

6、 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函数的先后

7、记录下来的顶点序列即为逆向的拓扑排序序列。,结论:,拓扑排序-方法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,

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号