7.4 最小生成树一、最小生成树概念
1,设无向连通图 G=（ V,{E}），
其子图 G’=（ V,{T}） 满足：
① V(G’)=V(G) n个顶点
② G’是连通的
③ G’中无回路则 G’是 G的生成树
7.4 最小生成树具有 n个顶点的无向连通图 G
其任一生成 G’恰好含 n-1条边
生成树不一定唯一，如
4个顶点选择 3条边有如下 5种形状 (5× 4= 20种 ):
其中 16种为生成树,（保证了连通）
生成树代价对图中每条边赋于一个权值（代价），则构成一个网，
网的生成树 G’=(V,{T})的 代价 是 T中各边的权值之和，
最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。
最小生成树也不一定唯一。
7.4 最小生成树最小生成树的实用例子很多例 1,N台计算机之间建立通讯网顶点表示 computer
边表示通讯线权值表示通讯线的代价（通讯线长度,computer间距离等）
要求：
① n台计算机中的任何两台能通过网进行通讯；
② 使总的代价最小。 -------求最小生成树 [T]
7.4 最小生成树最小生成树的实用例子例 2,邮递员送信线路 [T]
顶点表示投递点边表示街道权值表示街道的长度要求：
① 完成 n个投递点的投递；
② 使总路径长度最短,即求最小生成树 [T]
7.4 最小生成树二、最小生成树性质 MST
设 N=（ V,{E}）是一个连通网，
U是顶点集 V的一个非空子集。
若（ u,v）是一条具有最小权值的边，其中 u∈U,v∈V -U,
即（ u,v） =Min{cost(x,y)|x∈U,y∈V -U}
则必存在一棵包含边（ u,v）的最小生成树。
u v-u
u v
u’ v’
含义：将顶点分为两个不相交的集合 U和 V-U，
若边（ u,v）是连接这两个顶点集的最小权值边，则边（ u,v）必然是某最小生成树的边。
三、普里姆（ Prim）最小生成树算法设 N=（ V,{E}）是一个连通网，
V=[1,2,…,n}是 N的顶点集合，
辅助集合 U，初值为 {Uo}，
用来存放当前所得到的最小生成树的顶点；
辅助集合 TE，初值为 {}，
用来存放当前所得到的最小生成树的边。
Prim算法步骤
1,TE=Ф,U={u0}
2,当 U≠V,重复下列步骤：
(1)选取（ u0,v0)=min{cost(u,v)|u∈U,v∈V -U},保证不形成回路
(2)TE=TE+（ u0,v0),边（ u0,v0)并入 TE
(3)U=U+{V0},顶点 V0 并入 U
初始化,①
②
①
④
⑤
5
2
1
③
3 4
6
6
5 5
6
⑥
①
1
③
第 1步：
6
①
1
③
4
第 2步：
④
6
①
1
③
4 2
第 3步：
5② ④
6
①
1
③
4 2
第 4步：
23
⑤
② 5 ④
6
①
1
③
4
第 5步：特点,以连通为主选代价最小的邻接边算法 minispantree_PRIM的几点说明,
1,G为 网 的邻接矩阵即 G.arcs[i,j]=wij 或 为无穷大
2,辅助数组 closedge[1..n] 有两个分量,
closedge[k].adjvex存放边 (k,j)依附的另一顶点 j( j∈ U)
closedge[k].lowcost存放边 (k,j)的权值，当值为 0时，表示顶点 k已加入到集合 U中。
区别顶点 ∈ U或 ∈ V-U，是根据,.lowcost=0 ∈ U
.lowcost 〉 0 ∈ V-U
closedge[k].adjvex ∈ U 而 k ∈ V-U
Prim算法实现,见书 P175.
算法 minispantree_PRIM的几点说明,
3,int minimum(closedge)
{ min=∞; h=1;
for ( k=1;k<= vtxnum ;k++)
if ((closedge[k].lowcost!=0)&&(closedge[k].lowcost<min))
{ min:=closedge[k].lowcost; h:=k;}
return h;
} //minimum
例子：
V
Closedge
1 2 3 4 5 6 U V-U TE
VEX
L O W C O S T 0
①
6
①①
11
①①
55
①①
∞
①①
∞
{ 1 }
{ 2,3,4,5,6 } {}
0
③③
55 0
①①
55
③③
66
③③
44
{ 1,3 } { 2,4,5,6 } { 1,3 }
0
③③
55 0
⑥
2
③③
66 0
{ 1,3,6 } { 2,4,5 },,( 3,6 )
0
③③
55 0 0
③③
66 0
{ 1,3,6,4 } { 2,5 },,( 6,4 )
0 0 0 0
②
3 0
{ 1,3,6,4,2 } {5},,( 3,2 )
0 0 0 0 0 0
{ 1,3,6,4,2,5 } {},,( 2,5 )
②
①
④
⑤
5
2
1
③
3 4
6
6
5 5
6
⑥
四、克鲁斯卡尔（ Kruskal） 最小生成树算法
Kruskal 算法是逐步给生成树 T中添加不和 T中的边构成回路的当前最小代价边。
特点,以最小代价边主。
设 N=（ V,{E}）是个连通网,算法步骤为：
1,置生成树 T的初始状态为 T=（ V,{Ф}）
2,当 T中边数 <n-1时,重复下列步骤,
从 E中选取代价最小的边（ v,u）,并删除之 ;
若（ v,u） 依附的顶点 v和 u落在 T中不同的连同分量上，
则将边（ v,u）并入到 T的边集中；
否则，舍去该边，选择下一条代价最小的边,
四、克鲁斯卡尔（ Kruskal） 最小生成树算法步骤 (v,u) E T
②
①
④
⑤
③
⑥
②
①
④
⑤
③
⑥
1 (1,3)
0 ②
①
④
⑤
5
2
③
3 4
6
6
5 5
6
⑥
②
①
④
⑤
5
③
3 4
6
6
5 5
6
⑥
2
1
四、克鲁斯卡尔（ Kruskal） 最小生成树算法
②
①
④
⑤
5
③
3 4
6
6
5 5
6
⑥
步骤 (v,u) E T
3 (2,5)
2 (4,6) ②
①
④
⑤
③
⑥
②
①
④
⑤
5
③
4
6
6
5 5
6
⑥
②
①
④
⑤
③
⑥
四、克鲁斯卡尔（ Kruskal） 最小生成树算法步骤 (v,u) E T
5 (1,4)
4 (3,6) ②
①
④
⑤
5
③
6
6
5 5
6
⑥
②
①
④
⑤
③
6
6
5 5
6
⑥
②
①
④
⑤
③
⑥
②
①
④
⑤
③
⑥
四、克鲁斯卡尔（ Kruskal） 最小生成树算法步骤 (v,u) E T
6 (2,3)
②
①
④
⑤
③
6
6
5
6
⑥
边数 =n-1=5
代价 =(1+2+3+4+5)=15
②
①
④
⑤
③
⑥
1
23 4
5
7.5 拓扑排序 (topological sort)
拓扑排序是一种对非线性结构的有向图进行线性化的重要手段一,AOV网 (Activity on vertex network)
一个有向图可用来表示一个施工流程图、一个产品生产流程图、
或一个程序框图等。如图：
a1
a5
a4
a6
a2
a3 a8
a7
a9
课程安排
Pascal
DS
Compiler
OS
C
施工从活动 a1,a2开始，到达活动 a8和 a9时，整个施工结束。
有向图中，顶点表示活动，弧 < ai,aj >表示活动 ai优先于活动 aj,
称这类有向图为顶点表示活动的网（ AOV网）。
7.5 拓扑排序 (topological sort)
AOV网可解决如下两个问题：
（ 1）判定工程的可行性。显然，有回路，整个工程就无法结束
（ 2）确定各项活动在整个工程执行中的先后顺序。
称这种先后顺序为 拓扑有序序列 。
如图有如下拓扑有序序列,a1 a2 a3a4 a6 a5 a7 a8 a9
a2 a6 a1 a3 a4 a5 a7 a9 a8
a1
a5
a4
a6
a2
a3 a8
a7
a9
二、拓扑排序算法
1,算法步骤
(1)在 AOV网中，选取一个没有前驱的顶点输出；
(2)删除该顶点和所有以它为弧尾的弧；
(3)重复以上两步，直到
AOV网中全部顶点都已输出（得到拓扑有序序列）
或者，图中再无没有前驱的顶点（ AOV网中有环）
二、拓扑排序算法如何实现算法中的 (1)和 (2)？
对于 (1)，没有前驱的顶点即入度为 0的顶点；
对于 (2)，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减 1。
由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，因此，在选取存储结构时，应考虑：
能容易得到各顶点的入度；
有利于寻找任一顶点的所有直接后继。
为此，采用邻接表作为 AOV网的存储结构，并在头结点中增加一个存放顶点入度的域（ indegree）
V1
V4
V6
V2
V3
V5
V1
V2
V3
V4
V5
V6
0
2
1
2
3
0
4 3 2
5 2
5
5 4
拓扑排序算法见书 P182.
原始 AOV网
AOV网的邻接表存储结构
（并在头结点中增加一个存放顶点入度的域）
V1
V4
V6
V2
V3
V5
V1
V2
V3
V4
V5
V6
0
2
1
2
3
0
4 3 2
5 2
5
5 4
步骤 0 1 2 3 4 5 6
输出 V6 V1 V3 V2 V4 V5
count 0 1 2 3 4 5 6=n
栈 S 61 1 34 424 5
入度域 0
2
1
2
3
0
1
2
0
1
2
0
0
1
0
0
2
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
7.6 关键路径一,AOE网（ activity on edge）
若有向图中，顶点表示事件，弧表示活动，弧上的权表示完成该活动所需的时间，则称这类有向图为边表示活动的网（ AOE网）
AOE网中仅有一个入度为 0的事件，称为 源点,它表示工程的开始；网中也仅有一个出度为 0的事件，称为 汇点,它表示工程的结束。
每一事件 V表示以它为弧头的所有活动已经完成，
同时，也表示以它为弧尾的所有活动可以开始。
7.6 关键路径
AOE网可解决如下问题：
估算工程的最短工期（从源点到 汇点至少需要多少时间）
找出哪些活动是影响整个工程进展的关键
①
②
③
⑤
a1=6 a4=1
a2=4 a5=1
有 4个事件,V1,V2,V3,V5
V1为源点,V5为汇点有 4个活动,a1,a2,a4,a5
V3表示,a2已完成,a5可以开始
7.6 关键路径二、几个术语
路径长度,路径上各活动持续时间的总和
（ 即：路径上所有弧的权值之和 ）
关键路径,从源点到汇点之间路径长度最长的路径，
（ 不一定唯一 ）
事件 V i的最早发生时间 ve(i),从源点到 V i的最长路径长度
活动 ai的最早开始时间 e(i),等于该活动的弧尾事件
V j的最早发生时间即若 <j,k>表示活动 ai,则有 e(i)=ve(j)
vj
vkai
7.6 关键路径
事件 vk 的最迟发生时间 vl(k),是在不推迟整个工期的前提下，该事件最迟必须发生的时间
活动 ai的最迟开始时间 l(i),是该活动的弧头事件的最迟发生时间与该活动的持续时间之差，
即 l(i)=vl(k)- ai 的持续时间
关键活动,l(i)=e(i)的活动由此可见：在 AOE网中找关键活动问题可转化为求 l(i)=e(i)，
而 e(i)=ve(j)
l(i)=vl(k) - ai 的持续时间因此，需先求出事件的最早、最迟发生时间
7.6 关键路径三、关键路径算法思想
1,从 ve(1)=0 开始利用下面递推公式，计算出各事件的最早发生时间
ve(j)=Max{ve(i)+dut(<i,j>)}，
j=2,……,n,<i,j> ∈T
其中,T是所有以 j为头的弧集合，
dut(<i,j>)表示活动的持续时间前例中,ve(5)=Max{ve(2)+dut(<2,5>)，
ve(3)+dut(<3,5>)}
=Max{6+1,4+1}=7
①
②
③
⑤
a1=6 a4=1
a2=4 a5=1
2,从 vl(n)=ve(n)开始，利用下面递推公式，
计算出各事件的最迟发生时间：
vl(i)=Min{vl(j)-dut(<i,j>)}
i=n-1,……,2,1,<i,j> ∈S
其中,S是所有以 i为尾的弧集合
7.6 关键路径
①
②
③
⑤
a1=6 a4=1
a2=4 a5=1
前例中,vl(5)=ve(5)=7 vl(2)=vl(5)-1=6
vl(3)=vl(5)-1=6
vl(1)=Min{vl(2)-dut(<1,2>),vl(3)-dut(<1,3>)}
=Min{6-6,6-4}=0
7.6 关键路径
3,设活动 ai由弧 <j,k>表示，其持续时间为 dut(<j,k>)，则利用下面公式，计算出各活动的最早、最迟开始时间：
e(i)=ve(j)
l(i)=vl(k)-dut(<j,k>)
4,找出 e(i)=l(i)的活动，即为关键活动，诸关键活动组成的从源点到汇点的路径即为 关键路径。
7.6 关键路径四、例子计算结果为：
顶点 Ve Vl 活动 弧 持续 T e l l-e 关键活动
V1 0 0 a1 <1,2> 3 0 1 1
V2 3 4 a2 <1,3> 2 0 0 0 a2
V3 2 2 a3 <2.4> 2 3 4 1
V4 6 6 a4 <2,5> 3 3 4 1
V5 6 7 a5 <3,4> 4 2 2 0 a5
V6 8 8 a6 <3,6> 3 2 5 3
a7 <4,6> 2 6 6 0 a7
Max + Min - a8 <5,6> 1 6 7 1
①
②
③
④
⑤
⑥
a4=3
a2=2
a1=3
a5=4
a6=3
a7=2
a8=1a3=2
7.6 关键路径
关键路径上的活动都是关键活动。
缩短非关键活动都不能缩短整个工期如 a6缩短为 1，则整个工期仍为 8。
又如 a6推迟 3天开始，或拖延 3天完成
（ a6=6）均不影响整个工期
分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期。
如 a7缩短为 1，则整个工期为 7。
此时，再缩短任一关键活动均不能缩短整个工期。
即在有多条关键路径时，缩短那些在所有关键路上的关键活动，
才能缩短整个工期关键路径的实现算法见书 P184－ 185.
①
②
③
④
⑤
⑥
a4=3
a2=2
a1=3
a5=4
a6=3
a7=2
a8=1a3=2
7.7 最短路径在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题一、某个源点到其余各顶点的最短路径算法迪杰特拉（ Dijkstra） 算法：
算法思想：按路径长度递增的次序产生到各顶点的最短路径
使用 DS：
利用带权邻接矩阵 cost
表示当前找到的从源点 V0到每个终点 Vi的最短路径长度的辅助向量 dist[i]
存储最短路径的向量 path[i]
表示已找到从 V0出发的最短路径的终点的集合 S
7.7 最短路径
算法步骤：
1,用 cost初始化 dist；置 S={V0}；
2,选择 Vj,使得,dist[j]=Min{dist[i]|Vi∈ V-S}
Vj 就是当前求得的从 V0出发的最短路径的终点，并将 Vj并入 S；
3,对 V-S上的所有顶点 Vk，修改：
dist[k]=Min{dist[j]+cost[j,k],dist[k]}
4,重复 2,3,n-1次。
算法实现见书 P189.
7.7 最短路径
例子
① ② ③
④
⑤
0
5
10
50
30
100 60
10 20
cost 0 1 2 3 4 5
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞ ∞
10
5
∞
∞
∞
∞
∞
∞
∞
50
20
30
∞
∞
∞
∞
100
10
60
∞
0
1
2
3
4
5
终点 从 v0 到各终点的 dist 值和最短路径
v1
v2
v4
v3
v5
vj
60(v0,v4,v3,v5)
v5
∞
50(v0,v4,v3)
90(v0,v4,v5)
v3
∞ ∞
10(v0,v2)
30(v0,v4)
100(v0,v5)
v2
∞
∞ 60(v0,v2,v3)
v4
∞
30(v0,v4)
100(v0,v5)
7.7 最短路径二、每一对顶点之间的最短路径两种方法：每次以一个顶点为源点，重复调用 Dijkstra算法 n次；
弗洛伊德算法 (Floyed)
1.弗洛伊德算法思想：以 A(0) [i,j]=cost[i,j] 递推出：
A(k)[i,j]=Min{A(k-1)[i,j],A(k-1)[i,k]+ A(k-1) [k,j]},1≤k≤n
其中,A[k][i,j] 表示从 vi到 vj 的中间顶点的序号不大于 k
的最短路径长度。最后得到的 A[n][i,j]就是从 vi到 vj 的最短路径长度。
算法实现见书 P191.
7.7 最短路径
2.例子
∞ 4 11
∞
∞∞
6 2
3
① ②
③
6
4
3 11
2
A B
C
1 2 3
A(0) A(1) A(2) A(3)A
4 11 6
∞
∞
6 2 5
3 7∞∞
1
2
3
1 2 3 1 2 3 1 2 3
∞
∞
∞3 7
4 6
2
1,设无向连通图 G=（ V,{E}），
其子图 G’=（ V,{T}） 满足：
① V(G’)=V(G) n个顶点
② G’是连通的
③ G’中无回路则 G’是 G的生成树
7.4 最小生成树具有 n个顶点的无向连通图 G
其任一生成 G’恰好含 n-1条边
生成树不一定唯一，如
4个顶点选择 3条边有如下 5种形状 (5× 4= 20种 ):
其中 16种为生成树,（保证了连通）
生成树代价对图中每条边赋于一个权值（代价），则构成一个网，
网的生成树 G’=(V,{T})的 代价 是 T中各边的权值之和，
最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。
最小生成树也不一定唯一。
7.4 最小生成树最小生成树的实用例子很多例 1,N台计算机之间建立通讯网顶点表示 computer
边表示通讯线权值表示通讯线的代价（通讯线长度,computer间距离等）
要求：
① n台计算机中的任何两台能通过网进行通讯；
② 使总的代价最小。 -------求最小生成树 [T]
7.4 最小生成树最小生成树的实用例子例 2,邮递员送信线路 [T]
顶点表示投递点边表示街道权值表示街道的长度要求：
① 完成 n个投递点的投递；
② 使总路径长度最短,即求最小生成树 [T]
7.4 最小生成树二、最小生成树性质 MST
设 N=（ V,{E}）是一个连通网，
U是顶点集 V的一个非空子集。
若（ u,v）是一条具有最小权值的边，其中 u∈U,v∈V -U,
即（ u,v） =Min{cost(x,y)|x∈U,y∈V -U}
则必存在一棵包含边（ u,v）的最小生成树。
u v-u
u v
u’ v’
含义：将顶点分为两个不相交的集合 U和 V-U，
若边（ u,v）是连接这两个顶点集的最小权值边，则边（ u,v）必然是某最小生成树的边。
三、普里姆（ Prim）最小生成树算法设 N=（ V,{E}）是一个连通网，
V=[1,2,…,n}是 N的顶点集合，
辅助集合 U，初值为 {Uo}，
用来存放当前所得到的最小生成树的顶点；
辅助集合 TE，初值为 {}，
用来存放当前所得到的最小生成树的边。
Prim算法步骤
1,TE=Ф,U={u0}
2,当 U≠V,重复下列步骤：
(1)选取（ u0,v0)=min{cost(u,v)|u∈U,v∈V -U},保证不形成回路
(2)TE=TE+（ u0,v0),边（ u0,v0)并入 TE
(3)U=U+{V0},顶点 V0 并入 U
初始化,①
②
①
④
⑤
5
2
1
③
3 4
6
6
5 5
6
⑥
①
1
③
第 1步：
6
①
1
③
4
第 2步：
④
6
①
1
③
4 2
第 3步：
5② ④
6
①
1
③
4 2
第 4步：
23
⑤
② 5 ④
6
①
1
③
4
第 5步：特点,以连通为主选代价最小的邻接边算法 minispantree_PRIM的几点说明,
1,G为 网 的邻接矩阵即 G.arcs[i,j]=wij 或 为无穷大
2,辅助数组 closedge[1..n] 有两个分量,
closedge[k].adjvex存放边 (k,j)依附的另一顶点 j( j∈ U)
closedge[k].lowcost存放边 (k,j)的权值，当值为 0时，表示顶点 k已加入到集合 U中。
区别顶点 ∈ U或 ∈ V-U，是根据,.lowcost=0 ∈ U
.lowcost 〉 0 ∈ V-U
closedge[k].adjvex ∈ U 而 k ∈ V-U
Prim算法实现,见书 P175.
算法 minispantree_PRIM的几点说明,
3,int minimum(closedge)
{ min=∞; h=1;
for ( k=1;k<= vtxnum ;k++)
if ((closedge[k].lowcost!=0)&&(closedge[k].lowcost<min))
{ min:=closedge[k].lowcost; h:=k;}
return h;
} //minimum
例子：
V
Closedge
1 2 3 4 5 6 U V-U TE
VEX
L O W C O S T 0
①
6
①①
11
①①
55
①①
∞
①①
∞
{ 1 }
{ 2,3,4,5,6 } {}
0
③③
55 0
①①
55
③③
66
③③
44
{ 1,3 } { 2,4,5,6 } { 1,3 }
0
③③
55 0
⑥
2
③③
66 0
{ 1,3,6 } { 2,4,5 },,( 3,6 )
0
③③
55 0 0
③③
66 0
{ 1,3,6,4 } { 2,5 },,( 6,4 )
0 0 0 0
②
3 0
{ 1,3,6,4,2 } {5},,( 3,2 )
0 0 0 0 0 0
{ 1,3,6,4,2,5 } {},,( 2,5 )
②
①
④
⑤
5
2
1
③
3 4
6
6
5 5
6
⑥
四、克鲁斯卡尔（ Kruskal） 最小生成树算法
Kruskal 算法是逐步给生成树 T中添加不和 T中的边构成回路的当前最小代价边。
特点,以最小代价边主。
设 N=（ V,{E}）是个连通网,算法步骤为：
1,置生成树 T的初始状态为 T=（ V,{Ф}）
2,当 T中边数 <n-1时,重复下列步骤,
从 E中选取代价最小的边（ v,u）,并删除之 ;
若（ v,u） 依附的顶点 v和 u落在 T中不同的连同分量上，
则将边（ v,u）并入到 T的边集中；
否则，舍去该边，选择下一条代价最小的边,
四、克鲁斯卡尔（ Kruskal） 最小生成树算法步骤 (v,u) E T
②
①
④
⑤
③
⑥
②
①
④
⑤
③
⑥
1 (1,3)
0 ②
①
④
⑤
5
2
③
3 4
6
6
5 5
6
⑥
②
①
④
⑤
5
③
3 4
6
6
5 5
6
⑥
2
1
四、克鲁斯卡尔（ Kruskal） 最小生成树算法
②
①
④
⑤
5
③
3 4
6
6
5 5
6
⑥
步骤 (v,u) E T
3 (2,5)
2 (4,6) ②
①
④
⑤
③
⑥
②
①
④
⑤
5
③
4
6
6
5 5
6
⑥
②
①
④
⑤
③
⑥
四、克鲁斯卡尔（ Kruskal） 最小生成树算法步骤 (v,u) E T
5 (1,4)
4 (3,6) ②
①
④
⑤
5
③
6
6
5 5
6
⑥
②
①
④
⑤
③
6
6
5 5
6
⑥
②
①
④
⑤
③
⑥
②
①
④
⑤
③
⑥
四、克鲁斯卡尔（ Kruskal） 最小生成树算法步骤 (v,u) E T
6 (2,3)
②
①
④
⑤
③
6
6
5
6
⑥
边数 =n-1=5
代价 =(1+2+3+4+5)=15
②
①
④
⑤
③
⑥
1
23 4
5
7.5 拓扑排序 (topological sort)
拓扑排序是一种对非线性结构的有向图进行线性化的重要手段一,AOV网 (Activity on vertex network)
一个有向图可用来表示一个施工流程图、一个产品生产流程图、
或一个程序框图等。如图：
a1
a5
a4
a6
a2
a3 a8
a7
a9
课程安排
Pascal
DS
Compiler
OS
C
施工从活动 a1,a2开始，到达活动 a8和 a9时，整个施工结束。
有向图中，顶点表示活动，弧 < ai,aj >表示活动 ai优先于活动 aj,
称这类有向图为顶点表示活动的网（ AOV网）。
7.5 拓扑排序 (topological sort)
AOV网可解决如下两个问题：
（ 1）判定工程的可行性。显然，有回路，整个工程就无法结束
（ 2）确定各项活动在整个工程执行中的先后顺序。
称这种先后顺序为 拓扑有序序列 。
如图有如下拓扑有序序列,a1 a2 a3a4 a6 a5 a7 a8 a9
a2 a6 a1 a3 a4 a5 a7 a9 a8
a1
a5
a4
a6
a2
a3 a8
a7
a9
二、拓扑排序算法
1,算法步骤
(1)在 AOV网中，选取一个没有前驱的顶点输出；
(2)删除该顶点和所有以它为弧尾的弧；
(3)重复以上两步，直到
AOV网中全部顶点都已输出（得到拓扑有序序列）
或者，图中再无没有前驱的顶点（ AOV网中有环）
二、拓扑排序算法如何实现算法中的 (1)和 (2)？
对于 (1)，没有前驱的顶点即入度为 0的顶点；
对于 (2)，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减 1。
由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，因此，在选取存储结构时，应考虑：
能容易得到各顶点的入度；
有利于寻找任一顶点的所有直接后继。
为此，采用邻接表作为 AOV网的存储结构，并在头结点中增加一个存放顶点入度的域（ indegree）
V1
V4
V6
V2
V3
V5
V1
V2
V3
V4
V5
V6
0
2
1
2
3
0
4 3 2
5 2
5
5 4
拓扑排序算法见书 P182.
原始 AOV网
AOV网的邻接表存储结构
（并在头结点中增加一个存放顶点入度的域）
V1
V4
V6
V2
V3
V5
V1
V2
V3
V4
V5
V6
0
2
1
2
3
0
4 3 2
5 2
5
5 4
步骤 0 1 2 3 4 5 6
输出 V6 V1 V3 V2 V4 V5
count 0 1 2 3 4 5 6=n
栈 S 61 1 34 424 5
入度域 0
2
1
2
3
0
1
2
0
1
2
0
0
1
0
0
2
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
7.6 关键路径一,AOE网（ activity on edge）
若有向图中，顶点表示事件，弧表示活动，弧上的权表示完成该活动所需的时间，则称这类有向图为边表示活动的网（ AOE网）
AOE网中仅有一个入度为 0的事件，称为 源点,它表示工程的开始；网中也仅有一个出度为 0的事件，称为 汇点,它表示工程的结束。
每一事件 V表示以它为弧头的所有活动已经完成，
同时，也表示以它为弧尾的所有活动可以开始。
7.6 关键路径
AOE网可解决如下问题：
估算工程的最短工期（从源点到 汇点至少需要多少时间）
找出哪些活动是影响整个工程进展的关键
①
②
③
⑤
a1=6 a4=1
a2=4 a5=1
有 4个事件,V1,V2,V3,V5
V1为源点,V5为汇点有 4个活动,a1,a2,a4,a5
V3表示,a2已完成,a5可以开始
7.6 关键路径二、几个术语
路径长度,路径上各活动持续时间的总和
（ 即：路径上所有弧的权值之和 ）
关键路径,从源点到汇点之间路径长度最长的路径，
（ 不一定唯一 ）
事件 V i的最早发生时间 ve(i),从源点到 V i的最长路径长度
活动 ai的最早开始时间 e(i),等于该活动的弧尾事件
V j的最早发生时间即若 <j,k>表示活动 ai,则有 e(i)=ve(j)
vj
vkai
7.6 关键路径
事件 vk 的最迟发生时间 vl(k),是在不推迟整个工期的前提下，该事件最迟必须发生的时间
活动 ai的最迟开始时间 l(i),是该活动的弧头事件的最迟发生时间与该活动的持续时间之差，
即 l(i)=vl(k)- ai 的持续时间
关键活动,l(i)=e(i)的活动由此可见：在 AOE网中找关键活动问题可转化为求 l(i)=e(i)，
而 e(i)=ve(j)
l(i)=vl(k) - ai 的持续时间因此，需先求出事件的最早、最迟发生时间
7.6 关键路径三、关键路径算法思想
1,从 ve(1)=0 开始利用下面递推公式，计算出各事件的最早发生时间
ve(j)=Max{ve(i)+dut(<i,j>)}，
j=2,……,n,<i,j> ∈T
其中,T是所有以 j为头的弧集合，
dut(<i,j>)表示活动的持续时间前例中,ve(5)=Max{ve(2)+dut(<2,5>)，
ve(3)+dut(<3,5>)}
=Max{6+1,4+1}=7
①
②
③
⑤
a1=6 a4=1
a2=4 a5=1
2,从 vl(n)=ve(n)开始，利用下面递推公式，
计算出各事件的最迟发生时间：
vl(i)=Min{vl(j)-dut(<i,j>)}
i=n-1,……,2,1,<i,j> ∈S
其中,S是所有以 i为尾的弧集合
7.6 关键路径
①
②
③
⑤
a1=6 a4=1
a2=4 a5=1
前例中,vl(5)=ve(5)=7 vl(2)=vl(5)-1=6
vl(3)=vl(5)-1=6
vl(1)=Min{vl(2)-dut(<1,2>),vl(3)-dut(<1,3>)}
=Min{6-6,6-4}=0
7.6 关键路径
3,设活动 ai由弧 <j,k>表示，其持续时间为 dut(<j,k>)，则利用下面公式，计算出各活动的最早、最迟开始时间：
e(i)=ve(j)
l(i)=vl(k)-dut(<j,k>)
4,找出 e(i)=l(i)的活动，即为关键活动，诸关键活动组成的从源点到汇点的路径即为 关键路径。
7.6 关键路径四、例子计算结果为：
顶点 Ve Vl 活动 弧 持续 T e l l-e 关键活动
V1 0 0 a1 <1,2> 3 0 1 1
V2 3 4 a2 <1,3> 2 0 0 0 a2
V3 2 2 a3 <2.4> 2 3 4 1
V4 6 6 a4 <2,5> 3 3 4 1
V5 6 7 a5 <3,4> 4 2 2 0 a5
V6 8 8 a6 <3,6> 3 2 5 3
a7 <4,6> 2 6 6 0 a7
Max + Min - a8 <5,6> 1 6 7 1
①
②
③
④
⑤
⑥
a4=3
a2=2
a1=3
a5=4
a6=3
a7=2
a8=1a3=2
7.6 关键路径
关键路径上的活动都是关键活动。
缩短非关键活动都不能缩短整个工期如 a6缩短为 1，则整个工期仍为 8。
又如 a6推迟 3天开始，或拖延 3天完成
（ a6=6）均不影响整个工期
分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期。
如 a7缩短为 1，则整个工期为 7。
此时，再缩短任一关键活动均不能缩短整个工期。
即在有多条关键路径时，缩短那些在所有关键路上的关键活动，
才能缩短整个工期关键路径的实现算法见书 P184－ 185.
①
②
③
④
⑤
⑥
a4=3
a2=2
a1=3
a5=4
a6=3
a7=2
a8=1a3=2
7.7 最短路径在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题一、某个源点到其余各顶点的最短路径算法迪杰特拉（ Dijkstra） 算法：
算法思想：按路径长度递增的次序产生到各顶点的最短路径
使用 DS：
利用带权邻接矩阵 cost
表示当前找到的从源点 V0到每个终点 Vi的最短路径长度的辅助向量 dist[i]
存储最短路径的向量 path[i]
表示已找到从 V0出发的最短路径的终点的集合 S
7.7 最短路径
算法步骤：
1,用 cost初始化 dist；置 S={V0}；
2,选择 Vj,使得,dist[j]=Min{dist[i]|Vi∈ V-S}
Vj 就是当前求得的从 V0出发的最短路径的终点，并将 Vj并入 S；
3,对 V-S上的所有顶点 Vk，修改：
dist[k]=Min{dist[j]+cost[j,k],dist[k]}
4,重复 2,3,n-1次。
算法实现见书 P189.
7.7 最短路径
例子
① ② ③
④
⑤
0
5
10
50
30
100 60
10 20
cost 0 1 2 3 4 5
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞ ∞
10
5
∞
∞
∞
∞
∞
∞
∞
50
20
30
∞
∞
∞
∞
100
10
60
∞
0
1
2
3
4
5
终点 从 v0 到各终点的 dist 值和最短路径
v1
v2
v4
v3
v5
vj
60(v0,v4,v3,v5)
v5
∞
50(v0,v4,v3)
90(v0,v4,v5)
v3
∞ ∞
10(v0,v2)
30(v0,v4)
100(v0,v5)
v2
∞
∞ 60(v0,v2,v3)
v4
∞
30(v0,v4)
100(v0,v5)
7.7 最短路径二、每一对顶点之间的最短路径两种方法：每次以一个顶点为源点，重复调用 Dijkstra算法 n次；
弗洛伊德算法 (Floyed)
1.弗洛伊德算法思想：以 A(0) [i,j]=cost[i,j] 递推出：
A(k)[i,j]=Min{A(k-1)[i,j],A(k-1)[i,k]+ A(k-1) [k,j]},1≤k≤n
其中,A[k][i,j] 表示从 vi到 vj 的中间顶点的序号不大于 k
的最短路径长度。最后得到的 A[n][i,j]就是从 vi到 vj 的最短路径长度。
算法实现见书 P191.
7.7 最短路径
2.例子
∞ 4 11
∞
∞∞
6 2
3
① ②
③
6
4
3 11
2
A B
C
1 2 3
A(0) A(1) A(2) A(3)A
4 11 6
∞
∞
6 2 5
3 7∞∞
1
2
3
1 2 3 1 2 3 1 2 3
∞
∞
∞3 7
4 6
2
