资源描述：
《拓扑排序和关键路径》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、EssentialofLectureSixteen：一、拓扑排序二、关键路径第十六讲1一、有向无环图及其应用有向无环图：没有回路的有向图（a）有向树（b）有向无环图（c）有向图问题：判断一个有向图是否为有向无环图的方法是？2一、有向无环图及其应用应用：工程流程、生产过程中各道工序的流程、程序流程、课程的流程。对整个工程和系统，人们关心的问题是：（1）工程能否顺利进行,，即工程流程是否“合理”；（2）完成整项工程至少需要多少时间，哪些子工程是影响工程进度的关键子工程。（1）拓扑排序（2）关键路径3一、有向无环图及其应用AOV网(activityonvertexnetwork)
2、用顶点表示活动，边表示活动的顺序关系。为求解工程流程是否“合理”，通常用AOV网的有向图表示工程流程。1、拓扑排序4某工程可分为6个子工程，若用顶点表示子工程（也称活动）,用弧表示子工程间的顺序关系。工程流程可用如下AOV网表示：例一、有向无环图及其应用(开始)AF(结束)566744513BEDC5一、有向无环图及其应用例2:计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。例6c1c2c3c4c5c6c7C8c9c10c11c12程序设计离散数学数据结构
3、汇编语言算法分析计算机体系编译方法操作系统高等数学线性代数电子电路数值分析无c1c1,c2c1c3,c4c11c5,c3c3,c6无c9c9c9,c10,c1课程编号课程名称先决条件c4c1c2c3c12c9c10c11c6c7c8c5例2:课程流程图如何安排施工计划？如何安排教学计划？7一个可行的施工计划为：A,B,C,D,E,F一个可行的学习计划为：C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8可行的计划的特点：若在流程图中顶点v是顶点u的前趋，则在计划序列中顶点v也是u的前趋。一、有向无环图及其应用8一、有向无环图及其应用拓扑排序(Top
4、ologicalSort)按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系由此所得顶点的线性序列称之为拓扑有序序列9例如：对于下列有向图BDAC可求得拓扑有序序列：ABCD或ACBD10BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路{B,C,D}11一、有向无环图及其应用拓扑排序方法：第一步：在有向图选一无前趋的顶点v，输出；第二步：从有向图中删除v及以v为尾的孤； 重复第一步和第二步，直到输出全部顶点或有向图中不存在无前趋顶点（此时图中存在环）。12C1C2C3C4C5C6C
5、7C8C9C10C11C12拓扑序列：开始（0）13C2C3C4C5C6C7C8C9C10C11C12拓扑序列：C1（1）C3C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2（2）14C4C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3（3）C5C6C7C8C9C10C11C12拓扑序列：C1--C2--C3--C4（4）15C6C8C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9C6C8C11C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10（8）C6C7C8C9C10C11C
6、12拓扑序列：C1--C2--C3--C4--C5（5）C6C8C9C10C11C12拓扑序列：C1--C2--C3--C4--C5--C7（6）（7）16C6C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11（9）C8C12拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6（10）C8拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12（11）拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12-
7、-C8（12）17C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：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网的拓扑序列不是唯一的如何在计算机上实现对有向图的拓扑排序？18abcghdfeabhcdgfe19一、有向无环图及其应用（1）选择一入度为0顶点v，输出；（2）将v邻接到的顶点的入度减1；（3）重复12，直到输出全部顶点或图中
