图的应用
? 7.5 有向无环图及其应用
7.5.1 拓扑排序
7.5.2 关键路径
? 7.6 最短路径
? 7.6.1 从某个源点到其余各顶点的最短路径
? 7.6.2 每一对顶点间的最短路径
7.5 有向无环图及其应用
? 一个无环的有向图叫做 有向无环图,
? 简称 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
有向无环图也是
描述一项工程或系统的进行过程的有效工具
±à 1? ?? 3ì ?? 3? ?¤DT ??
C1 3ì Dò éa ?? où ′? ?T
C2 ?? é￠ êy ?§ C1
C3 êy ?Y ?á ? C 1,C 2
C4 o? ±à ó? ?? C1
C5 ó? ?? éa ?? ·? ?? C 3,C 4
C6 ?? ?? oú ?- ?í C 11
C7 ±à ò? ?- ?í C 5,C 3
C8 2ù ×÷? μ í3 C 3,C 6
C9 ·? μè êy ?§ ?T
C 10 ?? D? ′ú êy C9
C 11 ?? í¨?? ?í C9
C 12 êy ?μ ·? ?? C 1C 9C 10
C12
C10
C11
C9
C1
C2
C3
C4
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-网 (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
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
ê? ?t j 1 2 3 4 5 6 7 8 9
v e ( j ) 0 6 4 5 7 7 16 14 18
v l ( j ) 0 6 6 8 7 10 16 14 18
o? ?ˉ 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
V1
V8
V2 V7
V9V5
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
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
?给定带权有向图 G和源点 v,求从 v到 G中其
余各顶点的最短路径
?例,求 v0到其余顶点的最短路径
V1
V5
V2
V4
V0
V3
5 50
100
10
60
2010
30
始点 终点 最短路径 路径长度
v0 v1 无
v2 (v0,v2) 10
v3 (v0,v4,v3) 50
v4 (v0,v4) 30
v5 (v0,v4,v3,v5) 60
迪杰斯特拉 (Dijkstra)算法
? (1)设置两个顶点的集合 T和 S;
? 集合 S存放已找到最短路径的顶点
? 集合 T存放当前还未找到最短路径的顶点
? (2)初始状态时,S只包含源点 v0 ;
? (3)从 T中选取某个顶点 vi(要求 vi 到 v0的路径长度最短 ) 加
入到 S中,;
? (4)S中每加入一个顶点 vi,都要修改顶点 v0到 T中剩余顶点的
最短路径长度值 ;
? 它们的值为原来值与 新值 的较小者 ;
? 新值是 vi的最短路径长度值加上 vi到该顶点的路径长度
? (5)不断重复 (3)和 (4),直到 S包含全部顶点 ;
V1
V5
V2
V4
V0
V3
5 50
100
10
60
2010
30
迪杰斯特拉 (Dijkstra)算法举例
带权邻接矩阵为,
? ? 10 ? 30 100
? ? 5 ? ? ?
? ? ? 50 ? ?
? ? ? ? ? 10
? ? ? 20 ? 60
? ? ? ? ? ?
最短路径的求解过程
终点 v1 v2 v3 v4 v5 vi
步骤 1 ? 10 ? 30 100 v2
(v0,v2) (v0,v4) (v0,v5)
步骤 2 ? 60 30 100 v4
(v0,v2,v3) (v0,v4) (v0,v5)
步骤 3 ? 50 90 v3
(v0,v4,v3) (v0,v4,v5)
步骤 4 ? 60 v5
(v0,v4,v3,v5)
步骤 5 ?
无
7.6 最短路径
7.6.2 每一对顶点间的最短路径
?给定带权有向图 G,求 G中每个顶点到其余
各顶点的最短路径
?例,求有向网 G的每一对顶点的最短路径
V0
V2
V1
6
2
4
113
有向网 G
0 4 11
6 0 2
3 ? 0
邻接矩阵
Floyd算法
? (1)递推产生一个矩阵序列 A0,A1,...,Ak,...An
? 其中 Ak[i,j]表示从顶点 vi到 vj的路径上所经过的顶
点序号不大于 k的最短路径长度
? (2)初始时,A0为邻接矩阵,
? (3)Ak+1[i,j]=min{Ak[i,j],Ak[i,k+1]+Ak[k+1,j]}
? (0<=k<=n-1)
0 4 11
6 0 2
3 ? 0
A0=
0 4 6
5 0 2
3 7 0
A2=
0 4 6
6 0 2
3 ? 0
A1=
实验与习题
?理论习题 7.10,7.11
?实验算法题, 7.15
? 7.5 有向无环图及其应用
7.5.1 拓扑排序
7.5.2 关键路径
? 7.6 最短路径
? 7.6.1 从某个源点到其余各顶点的最短路径
? 7.6.2 每一对顶点间的最短路径
7.5 有向无环图及其应用
? 一个无环的有向图叫做 有向无环图,
? 简称 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
有向无环图也是
描述一项工程或系统的进行过程的有效工具
±à 1? ?? 3ì ?? 3? ?¤DT ??
C1 3ì Dò éa ?? où ′? ?T
C2 ?? é￠ êy ?§ C1
C3 êy ?Y ?á ? C 1,C 2
C4 o? ±à ó? ?? C1
C5 ó? ?? éa ?? ·? ?? C 3,C 4
C6 ?? ?? oú ?- ?í C 11
C7 ±à ò? ?- ?í C 5,C 3
C8 2ù ×÷? μ í3 C 3,C 6
C9 ·? μè êy ?§ ?T
C 10 ?? D? ′ú êy C9
C 11 ?? í¨?? ?í C9
C 12 êy ?μ ·? ?? C 1C 9C 10
C12
C10
C11
C9
C1
C2
C3
C4
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-网 (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
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
ê? ?t j 1 2 3 4 5 6 7 8 9
v e ( j ) 0 6 4 5 7 7 16 14 18
v l ( j ) 0 6 6 8 7 10 16 14 18
o? ?ˉ 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
V1
V8
V2 V7
V9V5
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
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
?给定带权有向图 G和源点 v,求从 v到 G中其
余各顶点的最短路径
?例,求 v0到其余顶点的最短路径
V1
V5
V2
V4
V0
V3
5 50
100
10
60
2010
30
始点 终点 最短路径 路径长度
v0 v1 无
v2 (v0,v2) 10
v3 (v0,v4,v3) 50
v4 (v0,v4) 30
v5 (v0,v4,v3,v5) 60
迪杰斯特拉 (Dijkstra)算法
? (1)设置两个顶点的集合 T和 S;
? 集合 S存放已找到最短路径的顶点
? 集合 T存放当前还未找到最短路径的顶点
? (2)初始状态时,S只包含源点 v0 ;
? (3)从 T中选取某个顶点 vi(要求 vi 到 v0的路径长度最短 ) 加
入到 S中,;
? (4)S中每加入一个顶点 vi,都要修改顶点 v0到 T中剩余顶点的
最短路径长度值 ;
? 它们的值为原来值与 新值 的较小者 ;
? 新值是 vi的最短路径长度值加上 vi到该顶点的路径长度
? (5)不断重复 (3)和 (4),直到 S包含全部顶点 ;
V1
V5
V2
V4
V0
V3
5 50
100
10
60
2010
30
迪杰斯特拉 (Dijkstra)算法举例
带权邻接矩阵为,
? ? 10 ? 30 100
? ? 5 ? ? ?
? ? ? 50 ? ?
? ? ? ? ? 10
? ? ? 20 ? 60
? ? ? ? ? ?
最短路径的求解过程
终点 v1 v2 v3 v4 v5 vi
步骤 1 ? 10 ? 30 100 v2
(v0,v2) (v0,v4) (v0,v5)
步骤 2 ? 60 30 100 v4
(v0,v2,v3) (v0,v4) (v0,v5)
步骤 3 ? 50 90 v3
(v0,v4,v3) (v0,v4,v5)
步骤 4 ? 60 v5
(v0,v4,v3,v5)
步骤 5 ?
无
7.6 最短路径
7.6.2 每一对顶点间的最短路径
?给定带权有向图 G,求 G中每个顶点到其余
各顶点的最短路径
?例,求有向网 G的每一对顶点的最短路径
V0
V2
V1
6
2
4
113
有向网 G
0 4 11
6 0 2
3 ? 0
邻接矩阵
Floyd算法
? (1)递推产生一个矩阵序列 A0,A1,...,Ak,...An
? 其中 Ak[i,j]表示从顶点 vi到 vj的路径上所经过的顶
点序号不大于 k的最短路径长度
? (2)初始时,A0为邻接矩阵,
? (3)Ak+1[i,j]=min{Ak[i,j],Ak[i,k+1]+Ak[k+1,j]}
? (0<=k<=n-1)
0 4 11
6 0 2
3 ? 0
A0=
0 4 6
5 0 2
3 7 0
A2=
0 4 6
6 0 2
3 ? 0
A1=
实验与习题
?理论习题 7.10,7.11
?实验算法题, 7.15
