数据结构D图2.ppt

图的应用
有向无环图及其应用 拓扑排序 关键路径
最短路径
从某个源点到其余各顶点的最短路径
每一对顶点间的最短路径
有向无环图及其应用
一个无环的有向图叫做有向无环图,
简称DAG图
判断有向图中是否存在环的方法
有向树
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
有向无环图也是描述一项工程或系统的进行过程的有效工具
C12
C10
C11
C9
C1
C2
C3
C4
C6
C5
C7
C8
拓扑排序AOV-网(Activity On Vertex)
顶点--活动
弧--活动间的优先关系
AOV-网不应该出现有向环
上例的拓扑排序序列之一:
C1,C9, C2,C4,C10,C11, C3,C12,C6,C5, C7,C8
关键路径 AOE-网(Activity On Edge)
AOE-网是带权的有向无环网
顶点--事件或状态
弧--活动及发生的依次关系
权--活动持续的时间
源点--入度为0的顶点(只有一个)
汇点--出度为0的顶点(只有一个)
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
AOE-网要研究的问题
完成整项工程至少需要多少时间?
哪些活动是影响整个工程进度的关键?
关键路径:路径长度最长的路径
(从源点到汇点)
e(i)表示活动ai的最早开始时间
l(i)表示活动ai的最迟开始时间(不推迟整个工期)
e(i)=l(i)的活动叫做关键活动, 关键路径上的活动都是关键活动.
ve(j) 表示事件vj的最早发生时间
vl(j)表示事件vj的最迟发生时间(不推迟整个工期)
e(i), l(i), ve(j),vl(j)的关系
若活动ai由弧<j,k>表示,其持续的
时间记为dut(<j,k>), 则
e(i) = ve(j)
l(i) = vl(k) - dut(<j,k>)
Vj
Vk
ai
求ve(j)和vl(j)分两步进行:
(1) 从ve(0)=0开始向前递推:
ve(j) = max{ve(i) + dut(<i,j>)}
i
Vi
Vj
ai
Vi
Vj
ai
(2) vl(n-1)=ve(n-1)开始向后递推:
vl(i) = min{vl(j) - dut(<i,j>)}
j
求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
V1
V8
V2
V7
V9
V5
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