图的拓扑排序与关键路径.ppt

发布时间：2022-06-13 发布人：admin 分类：说明书资料大小：0.69M 资料格式：ppt 举报版权申诉

a1156c9c-161f-496f-81a8-51e422ded490.ppt.pdf-第1页.png

第1页 / 共34页

a1156c9c-161f-496f-81a8-51e422ded490.ppt.pdf-第2页.png

第2页 / 共34页

a1156c9c-161f-496f-81a8-51e422ded490.ppt.pdf-第3页.png

第3页 / 共34页

a1156c9c-161f-496f-81a8-51e422ded490.ppt.pdf-第4页.png

第4页 / 共34页

a1156c9c-161f-496f-81a8-51e422ded490.ppt.pdf-第5页.png

第5页 / 共34页

a1156c9c-161f-496f-81a8-51e422ded490.ppt.pdf-第6页.png

第6页 / 共34页

a1156c9c-161f-496f-81a8-51e422ded490.ppt.pdf-第7页.png

第7页 / 共34页

a1156c9c-161f-496f-81a8-51e422ded490.ppt.pdf-第8页.png

第8页 / 共34页

文本预览

有向无环图的应用

本讲内容 1.有向无环图的定义 2.有向无环图的应用拓扑排序关键路径

有向无环图的定义一个没有环的有向图称为有向无环图，简称DAG图。重要应用拓扑排序关键路径

有向无环图的应用一——拓扑排序举例一个计算机技术应用专业的学生必须学习的基础课程有：

课程代号课程名称先修课程 C1 C2 C3 C4 C5 C6 C7 高等数学程序设计离散数学数据结构编译原理操作系统计算机组成原理无无 C1 C2 C3 C2 C4 C4 C7 C2 c1 c3 c4 c6 c7 c2 c5 用顶点表示活动，用弧表示活动间的优先关系的有向图称为Activity On Vertex Network( AOV-网 )。前驱、后继、直接前驱、直接后继学习顺序： c1 c3 c2 c4 c7 c6 c5 c2 c7 c1 c3 c4 c5 c6

何谓“拓扑排序”？假设以有向图表示一个工程的施工图或程序的数据流图（AOV网），则图中不允许出现回路。检查有向图中是否存在回路的方法之按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次一，是对有向图进行拓扑排序。序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。

例如：对于下列有向图 A B C D 可求得拓扑有序序列： A B C D 或 A C B D

反之，对于下列有向图 A B C D 不能求得它的拓扑有序序列。因为图中存在一个回路 {B, C, D}

分享到：

赞收藏

资料库

图的拓扑排序与关键路径.ppt

相关推荐

课程资源

热门标签

最新资料