图--拓扑排序

《图--拓扑排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.1图的基本术语6.2图的存储结构6.3图的遍历6.4最小生成树6.5最短路径6.6拓扑排序6.7关键路径第6章图6.6拓扑排序AOV网拓扑排序关键路径AOE网6.6拓扑排序网中的顶点表示各门课程的教学活动，有向边表示各门课程的制约关系。课程代号课程名称先修课程0高等数学无1程序设计基础无2C程序设计0，13离散数学04数据结构1，2，35编译方法3，46操作系统401234566.6.1AOV网在有向图中若以顶点表示活动，用有向边表示活动之间的优先关系，则这样的有向图称为以顶点表示活动的网（ActivityOnVertexNetwor

2、k），简称AOV网。6.6拓扑排序应用：工程流程、生产过程中各道工序的流程、程序流程、课程的流程例如:某工程可分为V0、V1、V2、V3、V4、V5、V6,7个子工程，工程流程可用如下AOV网表示。其中顶点：表示子工程（也称活动），有向边：表示子工程间的顺序关系。V5V3V2V0V1V4V66.6.1AOV网假设下图表示一个工程的施工图，判断该工程是否合理？V0V1V5V2V4V3V0V16.6拓扑排序对工程，人们关心的问题：工程能否顺序进行，即工程流程是否“合理”？能否给出一个活动之间的优先关系的有序序列？拓扑排序：构造拓扑有序序列的过

3、程。一个AOV网的拓扑有序序列并不是惟一的。6.6.2拓扑排序何谓“拓扑有序序列”？它是由AOV网中的所有顶点构成的一个线性序列，在这个序列中体现了所有顶点间的优先关系。对于某个AOV网，如果它的拓扑有序序列被构造成功，则该网中不存在有向回路，其各子工程可按拓扑有序序列的次序进行安排。V0V1V5V2V4V3V0V1【例如】：对于下列有向图BDAC可求得拓扑有序序列：ABCD或ACBDBDAC不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}6.6.2拓扑排序如何进行拓扑排序？1）从有向图中选取一个没有前驱的顶点，并输出之;重复

4、上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。2）从有向图中删去此顶点以及所有以它为尾的弧;【注意】这样操作后的结果有两种:一种是网中全部顶点均被输出，说明网中不存在有向回路;另一种是网中顶点未被全部输出，剩余的顶点均有前驱顶点，说明网中存在有向回路。[拓扑排序的步骤]6.6.2拓扑排序V0V5V2V0V1V1V3V4abcghdfeabhcdgfe【实例】－－写出下图的拓扑排序序列序列:【练习】写出表示课程以及课程的制约关系的AOV网的一个拓扑有序序列。课程代号课程名称先修课程0高等数学无1程序设计基础无2C程序设计0，13离

5、散数学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;