图--拓扑排序VIP免费

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;