算法9拓扑排序.ppt
- 文档编号:18024956
- 上传时间:2023-08-06
- 格式:PPT
- 页数:47
- 大小:2.36MB
算法9拓扑排序.ppt
《算法9拓扑排序.ppt》由会员分享,可在线阅读,更多相关《算法9拓扑排序.ppt(47页珍藏版)》请在冰点文库上搜索。
1,拓扑排序,一、概念1、有向无环图DAG(DirectedAcyclicGraph)无环的有向图2、AOV(ActivityOnVertices)网络:
用顶点表示活动,用有向弧表示活动间的优先关系。
Vi必须先于活动Vj进行。
这种有向图称为用顶点表示活动的网络。
若是图中有向边,则vi是vj的直接前驱;vj是vi的直接后继AOV网中不允许有回路,这意味着某项活动不能以自己为先决条件,4,计划、施工过程、生产流程、程序流程等都是“工程”。
除了很小的工程外,一般都把工程分为若干个叫做“活动”的子工程。
完成了这些活动,这个工程就可以完成了。
例如,计算机专业学生的学习就是一个工程,每一门课程的学习就是整个工程的一些活动。
其中有些课程要求先修课程,有些则不要求。
这样在有的课程之间有领先关系,有的课程可以并行地学习。
5,6,1、在AOV中拓扑有序序列:
将各个顶点(代表各个活动)排列成一个线性有序的序列,使得AOV网络中所有应存在的前驱和后继关系都能得到满足。
拓扑排序把AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。
检测AOV网中是否存在环方法:
对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网必定不存在环。
二、拓扑排序,7,拓扑序列:
C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或:
C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一个AOV网的拓扑序列不是唯一的,8,B,D,A,C,对于有向图,不能求得它的拓扑有序序列。
因为图中存在一个回路B,C,D,9,输入AOV网络。
有n个顶点。
1在AOV网络中选一个没有直接前驱的顶点,并输出之。
2从图中删去该顶点,同时删去所有它发出的有向边。
3重复以上1、2步,直到全部顶点均已输出,拓扑有序序列形成,拓扑排序完成;或图中还有未输出的顶点,再也找不到没有前驱的顶点了。
这时AOV网络中必定存在有向环。
a,b,c,g,h,d,f,e,a,b,h,c,d,g,f,e,没有前驱的顶点删除顶点及以它为尾的弧,弧头顶点的入度减1,需要设一个数组indegreew,记录顶点的入度数,入度为零的顶点,11,3、AOV网络的存储方式-邻接表表示,C0,C1,C2,C3,C4,C5,C0C1C2C30C4C50,012345,inddatafirstarc,130103,1,adjvexnext,30,5,1,50,0,1,50,12,邻接表结点:
typedefstructnodeintadjvex;/顶点域structnode*next;/链域JD;,表头结点:
typedefstructtnodeintind;/入度域structnode*link;/链域TD;TDgM;,AOV网络的存储方式-邻接表表示,13,1把邻接表中所有入度为0的顶点进栈2栈非空时,输出栈顶元素Vj并退栈;在邻接表中查找Vj的直接后继Vk,把Vk的入度减1;若Vk的入度为0则进栈3重复上述操作直至栈空为止。
若栈空时输出的顶点个数不是n,则有向图有环;否则,拓扑排序完毕。
4、拓扑排序算法实现,14,15,输出序列:
6,16,17,输出序列:
6,18,输出序列:
6,19,输出序列:
6,20,输出序列:
6,21,输出序列:
61,22,输出序列:
61,23,输出序列:
61,4,24,输出序列:
61,4,25,输出序列:
61,4,26,输出序列:
61,4,3,27,输出序列:
61,4,3,28,输出序列:
61,4,3,29,输出序列:
61,4,3,30,输出序列:
61,4,3,31,输出序列:
613,4,3,32,输出序列:
613,4,33,输出序列:
613,4,34,输出序列:
613,4,35,输出序列:
613,4,2,36,输出序列:
613,4,2,37,输出序列:
613,4,2,38,输出序列:
6132,4,2,39,输出序列:
6132,4,40,输出序列:
61324,4,41,输出序列:
61324,42,输出序列:
61324,5,43,输出序列:
613245,44,输出序列:
61324,5,45,输出序列:
613245,5,46,5、拓扑排序的算法StatusTopologicalSort(ALGraphG)/对有n个顶点的AOV拓扑排序FindInDegree(G,indegree);/求各顶点入度InitStack(S);/置栈空for(inti=0;inextarc)k=p-adjvex;if(!
(-indegreek)push(S,k);if(countG.vexnum)returnERROR;elsereturnOK;,时间复杂度为O(n+e),47,6、拓扑排序算法分析:
建邻接表:
T(n)=O(e)搜索入度为0的顶点的时间:
T(n)=O(n)拓扑排序:
T(n)=O(n+e),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 拓扑 排序