电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

图--拓扑排序VIP免费

图--拓扑排序_第1页
1/13
图--拓扑排序_第2页
2/13
图--拓扑排序_第3页
3/13
6.1图的基本术语6.2图的存储结构6.3图的遍历6.4最小生成树6.5最短路径6.6拓扑排序6.7关键路径第第66章图章图6.6拓扑排序•AOV网•拓扑排序•关键路径•AOE网6.6拓扑排序网中的顶点表示各门课程的教学活动,有向边表示各门课程的制约关系。课程代号课程名称先修课程0高等数学无1程序设计基础无2C程序设计0,13离散数学04数据结构1,2,35编译方法3,46操作系统401234566.6.1AOV网在有向图中若以顶点表示活动,用有向边表示活动之间的优先关系,则这样的有向图称为以顶点表示活动的网(ActivityOnVertexNetwork),简称AOV网。6.6拓扑排序应用:工程流程、生产过程中各道工序的流程、程序流程、课程的流程例如:某工程可分为V0、V1、V2、V3、V4、V5、V6,7个子工程,工程流程可用如下AOV网表示。其中顶点:表示子工程(也称活动),有向边:表示子工程间的顺序关系。V5V3V2V0V1V4V66.6.1AOV网假设下图表示一个工程的施工图,判断该工程是否合理?V0V1V5V2V4V3V0V16.6拓扑排序对工程,人们关心的问题:工程能否顺序进行,即工程流程是否“合理”?能否给出一个活动之间的优先关系的有序序列?•拓扑排序拓扑排序::构造拓扑有序序列的过程。构造拓扑有序序列的过程。•一个AOV网的拓扑有序序列并不是惟一的。6.6.2拓扑排序何谓“拓扑有序序列”?它是由它是由AOVAOV网中的所有顶点构成的一个线性网中的所有顶点构成的一个线性序列,序列,在这个序列中体现了所有顶点间的优先关系在这个序列中体现了所有顶点间的优先关系。。•对于某个AOV网,如果它的拓扑有序序列被构造成功,则该网中不存在有向回路,其各子工程可按拓扑有序序列的次序进行安排。V0V1V5V2V4V3V0V1【例如】:对于下列有向图BDAC可求得拓扑有序序列:ABCD或ACBDBDAC不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}6.6.2拓扑排序如何进行拓扑排序?1)从有向图中选取一个没有前驱的顶点,并输出之;重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。2)从有向图中删去此顶点以及所有以它为尾的弧;【注意】这样操作后的结果有两种:一种是网中全部顶点均被输出,说明网中不存在有向回路;另一种是网中顶点未被全部输出,剩余的顶点均有前驱顶点,说明网中存在有向回路。[拓扑排序的步骤]6.6.2拓扑排序V0V5V2V0V1V1V3V4abcghdfeabhcdgfe【实例】--写出下图的拓扑排序序列序列:【练习】写出表示课程以及课程的制约关系的AOV网的一个拓扑有序序列。课程代号课程名称先修课程0高等数学无1程序设计基础无2C程序设计0,13离散数学04数据结构1,2,35编译方法3,46操作系统40123456【练习】写出下图所示网所有可能的拓扑有序序列。【练习答案】写出下图所示网所有可能的拓扑有序序列。可能的拓扑有序序列有:v1,v2,v3,v4,v5,v6;v1,v2,v3,v5,v4,v6;v1,v2,v4,v3,v5,v6;v2,v1,v4,v3,v5,v6;v2,v1,v3,v4,v5,v6;v2,v1,v3,v5,v4,v6;v2,v4,v1,v3,v5,v6;

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

图--拓扑排序

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部