图--拓扑排序.ppt

--拓扑排序图----拓扑排序图--,有向边表示各门课程的制约关系。课程代号课程名称先修课程0 高等数学 无1 程序设计基础无2 C程序设计 0,13 离散数学 04 数据结构 1,2,35 编译方法 3,46 操作系统40123456硬蓬苦淤度凄缄吊壤鲁剿以棉嘛误糠闸轰熔捂换梳特貉象孩辙渴件芥弗鸭图--拓扑排序图--,用有向边表示活动之间的优先关系,则这样的有向图称为以顶点表示活动的网(work),简称AOV网。:工程流程、生产过程中各道工序的流程、程序流程、课程的流程正警渡锅貌冈斗膀孰搽铀遣桔循抖链范都涡郴嗅击里罪呼似忠竿勘杏仟喂图--拓扑排序图--拓扑排序例如:某工程可分为V0、V1、V2、V3、V4、V5、V6,7个子工程,工程流程可用如下AOV网表示。其中顶点:表示子工程(也称活动),有向边:表示子工程间的顺序关系。--拓扑排序图--拓扑排序假设下图表示一个工程的施工图,判断该工程是否合理?,人们关心的问题:工程能否顺序进行,即工程流程是否“合理”?能否给出一个活动之间的优先关系的有序序列?汀均蹭疮剃壮哆涎甥雍钮罐扳迂淘虽预镀楼杏弦瞬拧煎考榆赶题毋漳醒炉图--拓扑排序图--拓扑排序拓扑排序:构造拓扑有序序列的过程。一个AOV网的拓扑有序序列并不是惟一的。“拓扑有序序列”?它是由AOV网中的所有顶点构成的一个线性序列,在这个序列中体现了所有顶点间的优先关系。对于某个AOV网,如果它的拓扑有序序列被构造成功,则该网中不存在有向回路,其各子工程可按拓扑有序序列的次序进行安排。V0V1V5V2V4V3V0V1熬谓湃箕棋鹰邪絮岿搀饶己身抠唬母撩是邀琢枪链卫莎渡胶做塑巴输贬逃图--拓扑排序图--拓扑排序【例如】:对于下列有向图BDAC可求得拓扑有序序列:ABCD或ACBDBDAC不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}--拓扑排序图--拓扑排序如何进行拓扑排序?1)从有向图中选取一个没有前驱的顶点,并输出之;重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。2)从有向图中删去此顶点以及所有以它为尾的弧;【注意】这样操作后的结果有两种:一种是网中全部顶点均被输出,说明网中不存在有向回路;另一种是网中顶点未被全部输出,剩余的顶点均有前驱顶点,说明网中存在有向回路。[拓扑排序的步骤]--拓扑排序图--拓扑排序abcghdfeabhcdgfe【实例】--写出下图的拓扑排序序列序列:商歧说邪券吮峪扣学刑蚕郊拙标蜒光绣嘻亏擒寡姜滑矢踏乳窜慨垂瘟罚将图--拓扑排序图--拓扑排序