7. 图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点的最短路径。
四、算法设计题
int degree1(Graph & ga, int numb)
2. 编写一个算法，求出邻接矩阵表示的有向图中序号为numb的顶点的度数。 int degree2(Graph & ga, int numb)
图6-15
1. 编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。
a1=3 a3=2 100 V0 30 V5 60 V4 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ ∞ ∞ ∞ 50 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 10 ∞ ∞ ∞ 20 ∞ 60 ∞ ∞ ∞ ∞ ∞ ∞ (b) 带权邻接矩阵 10 V1 5 V2 10 20 50 V3 (a) 有向带权图
8. 图6-15给出了一个具有15个活动、个事件的工程的AOE网，求关键路径。 图6-14 11有向带权图及其邻接矩阵
v4 v2 v1 a2=4 a7=6 a4=1 v7 a8=8 a11=7 v5 a5=3 a9=4 v3 a6=5 a13=10 v8 a12=4 v1001 a14=1v11 a15=6 v6 a10=2 v9 -31-
3. 编写一个算法，求出邻接表表示的无向图中序号为numb的顶点的度数。 int degree3(GraphL & gl, int numb)
4. 编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的度数。 int degree4(GraphL & gl, int numb)
习题6参考答案
一、单项选择题
1. A 2. D 3. D 4. C 5. B 6. B 7. B 8. A 9. C 10. D 11. C 12. D 13. A 14. B 15. B 17. A 18. A 19. B 20. D 21. A 22. C 23. B 24. A 二、填空题
1. 2 2. n(n-1)/2，n(n-1) 3. 2，4 4. n-1 5. 邻接矩阵，邻接表 6. 1 7. k+1 8. 3
9. n，n 10. 2e，e 11. 出边，入边 12. O（n），O（e/n）
13.O（n2
），O（n+e） 14. acdeb，acedb （答案不唯一） 15. acfebd，acefbd （答案不唯一） 16. 深度，广度 17. n，n-1
18. 唯一
19. 唯一 20. aebdcf（答案不唯一） 三、应用题
1. 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9 广度优先搜索序列：0,1,4,2,7,3,8,6,5,9 2. 深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,8 3. 深度优先搜索序列：0,2,3,5,6,1,4 广度优先搜索序列：0,2,3,5,6,1,4 4. 深度优先搜索序列：0,3,6,4,1,5,2 广度优先搜索序列：0,3,2,6,5,4,1 5. 过程如图6-16所示 60 50 V1 52 V3 45 V1 V3 50 V1 V3 V2 65 50 V4 42 V7 V2 V4 V7 V2 V4 V7 30 40 V5 V6 V5 V6 V5 V6 70 (a)
(b)
(c)
-32-
16. C 50 V1 V3 50 V1 V3 50 V1 V3 V2 V4 V7 V7 V2 V4 V7 V2 V4 50 30 40 V5 V6 40 50 V5 V6 40 V5 V6 (d)
(e)
(f)
V3 50 V1 V3 50 V1 45 V2 V4 42 V7 V2 V4 42 40 50 30 V7 50 30 V5 V6 40 V5 V6 (g)
(h)
图6-16
6. 求解过程如图6-17所示。 V1 V3 V1 V3 V1 V3 V2 V4 V7 V2 V4 V7 V2 V4 42 V7 V5 30 V6 40 V5 30 V6 40 V5 30 V6 (a)
(b)
(c)
V1 V3 V1 V3 V1 V3 V2 V4 42 45 50 45 V7 V2 V4 42 45 50 V7 V2 42 40 V5 30 40 50 V4 V7 V6 V5 30 V6 40 V5 30 V6 (d)
(e)
(f)
图6-17
7. 求解过程如下表所示。 终点 从v0到各终点的D值和最短路径的求解过程 i=1 i=2 i=3 i=4 i=5 V1 ∞ ∞ ∞ ∞ ∞ 无 V2 10 (v0,v2) -33-
V3 ∞ 60 50 (v0,v2,v3) (v0,v4,v3)
V4 30 30 (v0,v4) (v0,v4) V5 100 100 90 60 (v0,v5) (v0,v5) (v0,v4,v5) (v0,v4,v3,v5) Vj V2 V4 V3 V5 S {v0,v2} {v0,v2,v4} {v0,v2,v3,v4} {v0,v2,v3,v4,v5}
8. 求解过程如下： ①事件的最早发生时间ve[k]。
ve (1)=0 ve (2)=3 ve (3)=4 ve (4)=ve(2)+2=5
ve (5)=max{ve(2)+1,ve(3)+3}=7 ve (6)=ve(3)+5=9
ve (7)=max{ve(4)+6,ve(5)+8}=15 ve (8)=ve(5)+4=11
ve (9)=max{ve(8)+10,ve(6)+2}=21 ve (10)=max{ve(8)+4,ve(9)+1}=22 ve (11)=max{ve(7)+7,ve(10)+6}=28
②事件的最迟发生时间vl[k]。 vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21
vl (8)=min{ vl (10)-4, vl (9)-10}=11 vl (7)= vl (11)-7=21 vl (6)= vl (9)-2=19
vl (5)=min{ vl (7)-8,vl (8)-4}=7 vl (4)= vl (7)-6=15
vl (3)=min{ vl (5)-3, vl (6)-5}=4 vl (2)=min{ vl (4)-2, vl (5)-1}=6 vl (1)=min{vl (2)-3, vl (3)-4}=0
③活动ai的最早开始时间e[i]和最晚开始时间l[i]。
活动a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活动a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活动a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活动a4 e (4)=ve (2)=3 l (4)=vl (5) - 1=6
-34-
活动a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活动a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活动a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活动a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活动a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活动a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活动a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活动a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活动a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活动a14 e (14)=ve (9)=21 l (14)=vl (10) -1=21 活动a15 e (15)=ve (10)=22 l (15)=vl (11) -6 =22
④最后，比较e[i]和l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动，关键路径如图6-18所示。
a9=4 v1 a2=4 v5 v3 a5=3 v11 a15=6 v8 a13=10 v9
四、算法设计题
图6-18
01 a14=1 v101. int degree1(Graph & ga, int numb)
{ //根据无向图的邻接矩阵求出序号为numb的顶点的度数 int j,d=0;
for(j=0; j if (ga.cost[numb][j]!=0 && ga.cost[numb][j]!=MAXINT) d++; return (d); } 2. int degree2(Graph & ga, int numb) //根据有向图的邻接矩阵求出序号为numb的顶点的度数 { int i,j,d=0; //求出顶点numb的出度 for(j=0; j if(ga.cost[numb][j]!=0 && ga.cost[numb][j]!=MAXINT) -35-