图的应用 7.5有向无环图及其应用 7.5.1拓扑排序 7.5.2关键路径 7.6最短路径 7.6.1从某个源点到其余各顶点的最短路径 7.6.2每一对顶点间的最短路径
图的应用 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径 7.6 最短路径 • 7.6.1 从某个源点到其余各顶点的最短路径 • 7.6.2 每一对顶点间的最短路径
7.5有向无环图及其应用 个无环的有向图叫做有向无环图 简称DAG图 判断有向图中是否存在环的方法 有向树 DAG图 有向图
7.5 有向无环图及其应用 一个无环的有向图叫做有向无环图, 简称DAG图 判断有向图中是否存在环的方法 有向树 DAG图 有向图
有向无环图是 描述含有公共子式的表达式的有效工具 (a+b)*(b*(C+d)十(C+d)*e)*(C+d)*e) ⑥b 用二叉树描述表达式 用DAG描述表达式
有向无环图是 描述含有公共子式的表达式的有效工具. ((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) * * * * * + + + + + a b b c c c d d d 用二叉树描述表达式 e e * * * * + + + a b b c d 用DAG描述表达式 e
有向无环图也是 描述一项工程或系统的进行过程的有效工具 编号课程名称预修课 C1程序设计基础无 C2离散数学 C3数据结构C1C2 C4汇编语言 C5语言设计分析C3C4 C6计算机原理c1l C7编译原理 C5. C3 C12 C8操作系统 C3 C6 C9高等数学无 (CoC C C10线性代数 C9 Cll普通物理C9 C12数值分析CC9cl0
有向无环图也是 描述一项工程或系统的进行过程的有效工具 编号 课程名称 预修课 C1 程序设计基础 无 C2 离散数学 C1 C3 数据结构 C1,C2 C4 汇编语言 C1 C5 语言设计分析 C3,C4 C6 计算机原理 C11 C7 编译原理 C5,C3 C8 操作系统 C3,C6 C9 高等数学 无 C10 线性代数 C9 C11 普通物理 C9 C12 数值分析 C1C9C10 C12 C10 C11 C9 C1 C2 C3 C4 C6 C5 C7 C8
7.5.1拓扑排序 AOV-kXX (Activity On Vertex) 口顶点一一活动 0弧一一活动间的优先关系 AOV一网不应该出现有向环 上例的拓扑排序序列之一: C1,C9,C2C4,C10,C1l,C3,C12,C6,C5,C7,C8
7.5.1 拓扑排序 AOV-网(Activity On Vertex) 顶点－－活动 弧－－活动间的优先关系 AOV－网不应该出现有向环 上例的拓扑排序序列之一： C1,C9, C2,C4,C10,C11, C3,C12,C6,C5, C7,C8
7.5.2关键路径 AOE-kXX(Activity On Edge AOE一网是带权的有向无环网 顶点一一事件或状态 弧一一活动及发生的依次关系 口权—一活动持续的时间 口源点一一入度为0的顶点(只有一个) 出度为0的顶点(只有一个) V a a。=4
7.5.2 关键路径 AOE-网(Activity On Edge) AOE－网是带权的有向无环网 顶点－－事件或状态 弧－－活动及发生的依次关系 权－－活动持续的时间 源点－－入度为０的顶点（只有一个） 汇点－－出度为０的顶点（只有一个） V4 V1 V3 V8 V2 V7 V9 V6 V5 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4
AO-网要研究的间题 口完成整项工程至少需要多少时间? u哪些活动是影响整个工程进度的关键? 口关键路径:路径长度最长的路径 (从源点到汇点) e(i表示活动a1的最早开始时间 l(表示活动a的最迟开始时间(不推迟整个工期) ()=1()的活动叫做关键活动关键路径上的活动 都是关键活动 ve()表示事件v的最早发生时间 v(表示事件v的最迟发生时间(不推迟整个工期)
AOE-网要研究的问题 完成整项工程至少需要多少时间？ 哪些活动是影响整个工程进度的关键？ 关键路径：路径长度最长的路径 （从源点到汇点） e(i)表示活动ai的最早开始时间 l(i)表示活动ai的最迟开始时间(不推迟整个工期) e(i)=l(i)的活动叫做关键活动, 关键路径上的活动 都是关键活动. ve(j) 表示事件vj的最早发生时间 vl(j)表示事件vj的最迟发生时间(不推迟整个工期)
e(i),1(i),ve(j),V1(j的关系 若活动a由弧k>表示,其持续的 时间记为dut(≤jk>),则 ve( l(1)=v(k)-dut(≤k>) 求ve(和v(分两步进 )从ve()=0开始向前递推 ve(=maxie(1)+ dut(i,j>) (2)vl(n-1)=ve(n-1)开始向后递推 V(=mn{v()-dut()}
e(i), l(i), ve(j),vl(j)的关系 若活动ai由弧表示,其持续的 时间记为dut(), 则 e(i) = ve(j) l(i) = vl(k) - dut() Vj Vk ai 求ve(j)和vl(j)分两步进行: (1) 从ve(0)=0开始向前递推: ve(j) = max{ve(i) + dut()} i Vi Vj ai Vi Vj ai (2) vl(n-1)=ve(n-1)开始向后递推: vl(i) = min{vl(j) - dut()} j
求ADE网的关键路径举例 a Ve 事件j123456789 vel 4577161418 0668710161418 活动i 91011 e(1) 000645 71614 i)02366877101614
求AOE网的关键路径举例 V4 V1 V3 V8 V2 V7 V9 V6 V5 a1=6 a2=4 a3=5 a4=1 a5=1 a6=2 a7=9 a8=7 a9=4 a10=2 a11=4 事件j 1 2 3 4 5 6 7 8 9 ve(j) 0 6 4 5 7 7 16 14 18 vl(j) 0 6 6 8 7 10 16 14 18 活动i 1 2 3 4 5 6 7 8 9 10 11 e(i) 0 0 0 6 4 5 7 7 7 16 14 l(i) 0 2 3 6 6 8 7 7 10 16 14
a1=6 八(2)4 a2=9V-o=? Vo 整个工期为18 关键路径有两条V12V2V5VnV9 关键活动有六个:a1,a4,an,a3,aoa1
V1 V8 V2 V7 V5 V9 a1=6 a4=1 a7=9 a8=7 a10=2 a11=4 整个工期为18 关键路径有两条:(V1 ,V2 ,V5 ,V7 ,V9 ), (V1 ,V2 ,V5 ,V8 ,V9 ) 关键活动有六个: a1 , a4 , a7 , a8 , a10, a11