图结构习题答案.doc

第6章 图
【例6-1】回答下列问题:
(1)具有n个顶点得连通图至少有多少条边?
(2)具有n个顶点得强连通图至少有多少条边?这样得图应该就是什么形状?
(3)具有n个顶点得有向无环图最多有多少条边?
解:
(1)具有n个顶点得连通图至少有n-1条边。
这就是一个与生成树相关得问题。生成树就是一个连通图,它具有能够连通图中任何两个顶点得最小边集,任何一个生成树都具有n-1边。因此,具有n个顶点得连通图至少有n-1条边。
(2)具有n个顶点得强连通图至少有n条边,这样得图就是一个由n个顶点构成得环。
强连通图就是相对于有向图而言得。由于强连通图要求图中任何两个顶点之间能够相互连通,因此每个顶点至少要有一条以该顶点为弧头得弧与一条以该顶点为弧尾得弧,每个顶点得入度与出度至少各为1,即顶点得度至少为2,这样根据图得顶点数、边数以及各项点得度三者之间得关系计算可得:边数=2×n/2=n。
(3)具有n个顶点得有向无环图最多有n×(n—1)/2条边。
这就是一个拓扑排序相关得问题。—个有向无环图至少可以排出一个拓扑序列,不妨设这n个顶点排成得拓扑序列为v1,v2,v3,…,vn,那么在这个序列中,每个顶点vi只可能与排在它后面得顶点之间存在着以vi为弧尾得弧,最多有n-i条,因此在整个图中最多有(n-1)+(n-2)+ … +2+1=n×(n-1)/2条边。
2图得存储结构
常用得存储结构有邻接矩阵与邻接表。
(1)邻接矩阵表示法
设G＝(V,E)就是有n(n≥1)个顶点得图。则G得邻接矩阵就是按如下定义得n阶方阵:
0　　其它

1　　当(Ｖi,Vj)∈E或<Ｖi,Vj >∈E时

cost[i,j]=

0 1 1 0
1 0 1 1
1 1 0 1
0 1 1 0

A2=

A1=

0 1 1
0 0 1
0 0 0

例如,图6-1中G1,Ｇ2得邻接矩阵分别表示为A1、A2,矩阵得行列号对应于图6-1中结点得序号。
由邻接矩阵得定义可知,无向图得邻接矩阵必定就是对称阵;有向图得邻接矩阵不一定就是对称得。
根据邻接矩阵,很容易判定任意两个顶点之间就是否有边相连。求各顶点得度也就是非常容易得。对于无向图,顶点Vi得度就就是邻接矩阵中第i行(或第j列)上非零元得个数,即。对于有向图,第i行中非零元得个数为顶点Vi得出度,而第i列上得非零元个数为顶点Vi得入度。
(2)邻接表表示法
图得邻接链表存储结构就是一种顺序分配与链式分配相结合得存储结构括两个部分:一部分就是向量,另一部分就是链表。
邻接链表中得表头部分就是向量,用来存储n个表头结点。向量得下标指示顶点得序号。
例如,对于图6-1中G1与G2,其邻接链表如图6-3所示
在无向图得邻接表中顶点vi得度就就是第i个链表中结点得个数。在有向图中,第i个链表得结点数仅就是vi得出度,求vi得入度,必须查遍n个链表才能得出。
(a) G1得邻接表

1

2

3

3

3

2

∧

∧

∧

(b) G2得邻接表

图6-3 邻接表

3

1

2

3

4

1

∧

2

∧

4

4

3

3

2

2

∧

1

∧

【例6-2】 图G＝(V,E),其中V={1,2,3,4,5,6},Ｅ＝{<1,2><1,3>,<1,4>,<2,5>,<3,2>,<3,5>,
<3,6>,<4,6>,<5,6>},请画出图G,并写出其邻接矩阵与邻接表表示。
解:图G如图6-4中得(a)所示,图G得邻接矩阵与邻接表表示分别如图(b)与(c)所示。
对于这类问题,只要掌握了图得概念与存储结构就可以做出正确得答案。通常情况下.对图得顶点排列顺序与各顶点得邻接点排列顺序并没有特定要求,因此,在写出邻接矩阵与邻接表表示时,只要按照某种排列顺序画出相应得结构图就可以了。但应该注意得就是,对于邻接矩阵表示,如果顶点结点得顺序不同,那么邻接矩阵就不相同;对于邻接表表示,如果顶点结点得顺序或者邻接点得顺序不同,那么邻接表就不相同。
0 1 1 1 0 0
0 0 0 0 1 0
0 1 0 0 1 1
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 0 0 0

(b)

图6-4 图及其存储结构

1

(a)

3

4

2

5

6

(c)

1

2

6

4

5

3

2

2

3

5

4

∧

5

∧

6

∧

∧

6

∧

6

∧

【例6-3】已知一个无向图得邻接表如图6-5所示,要求:
(1)画出该无向图;
(2)根据邻接表,分别写出用DFS(深度优先搜索)与BFS(广度优先搜索)算法从顶点V0开始遍历该图后所得到得遍历序列。
图6-5 图得邻接表存储

V6

V0

V1

V5

V3

V4

V2

2

3

0

5

6

0

4

3

6

1

1

∧

2

∧

1

∧

2

1

0

2

5

0

∧

6

∧

3

∧

4

∧

解:
(1)该无向图如图6-6所示。
v0

v1

v2

v3

v4

v6

v5

图6-6 无向图

(2)根据该无向图得邻接表表示,从顶点V0开始得深度优先遍历序列为:V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列为V0、V2、V5、V6、V1、V3、V4。
从图得逻辑结构上来讲,从图中某个顶点开始得深度(或广度)优先遍历序列不一定就是唯一得。这就是因为在逻辑结构中,并没有对每个顶点得所有邻接点规定它们之间得先后顺序,这样在搜索算法中选取第—个邻接点与下一个邻接点时可能会有不同得结果。但就是在存储结构中,明确地给出了邻接点得先后顺序,这时深度优先与广度优先遍历序列就就是唯一得。
【例6-4】对于如图6-8所示得带权无向图,用图示说明:
(1)利用Prim算法从顶点a开始构造最小生成树得过程;
3

e

1

f

d

c

b

a

g

9

7

9

4

6

2

1

8

5

4

8

图6-8 带权无向图

(2)利用Kruskal算法构造最小生成树得过程;
解:
(1)利用Prim算法从顶点a开始构造最小生成树得过程如图6-9所示。
a

e

f

d

c

b

g

初始状态

a

e

f

d

c

b

g

连通e

2

a

e

f

d

c

b

g

连通g

2

1

a

e

f

d

c

b

g

连通d

2

1

3

3

a

e

f

d

c

b

g

连通f

2

1

4

3

a

e

f

d

c

b

g

连通b

2

1

4

6

图6-9 用Prim算法构造最小生成树得过程

3

a

e

f

d

c

b

g

连通c

2

1

4

6

1

(2)利用Kruskal算法构造最小生成树得过程如图6-10所示。
a

e

f

d

c

b

g

初始状态

a

e

f

d

c

b

g

增加第2条边

1

1

a

e

f

d

c

b

g

增加第1条边

1

3

a

e

f

d

c

b

g

增加第5条边

2

1

4

1

3

a

e

f

d

c

b

g

增加第4条边

2

1

1

a

e

f

d

c

b

g

增加第3条边

2

1

1

图6-10 用Kruskal算法构造最小生成树得过程

3

a

e

f

d

c

b

g

增加第6条边

2

1

4

6

1

【例6-5】 一个带权无向图得最小生成树就是否一定唯一？在什么情况下构造出得最小生成树可能不唯一？
解:一个带权无向图得最小生成树不一定就是唯一得。从Kruskal算法构造最小生成树得过程可以瞧出,当从图中选择当前权值最小得边时,如果存在多条这样得边,并且这些边与已经选取得边构成回路,此时这些边就不可能同时出现在一棵最小生成树中,对这些边得不同选择结果可能会产生不同得最小生成树。
习题6
一、单项选择题
1、 在一个具有n个顶点得有向图中,若所有顶点得出度数之与为s,则所有顶点得入度数之与为(1、 A 　)。
A、 s B、 s-1 C、 s+1 D、 n
2、 在一个具有n个顶点得有向图中,若所有顶点得出度数之与为s,则所有顶点得度数之与为(　2、 D　)。
A、 s B、 s-1 C、 s+1 D、 2s
3、 在一个具有n个顶点得无向图中,若具有e条边,则所有顶点得度数之与为(3、 D )。
A、 n B、 e C、 n+e D、 2e
4、 在一个具有n个顶点得无向完全图中,所含得边数为(4、 C)。
A、 n B、 n(n-1) C、 n(n-1)/2 D、 n(n+1)/2
5、 在一个具有n个顶点得有向完全图中,所含得边数为( 5、 B )。
A、 n B、 n(n-1) C、 n(n-1)/2 D、 n(n+1)/2
6、 在一个无向图中,若两顶点之间得路径长度为k,则该路径上得顶点数为( 6、 B )。
A、 k B、 k+1 C、 k+2 D、 2k
7、 对于一个具有n个顶点得无向连通图,它包含得连通分量得个数为(7、 B)。
A、 0 B、 1 C、 n D、 n+1
8、 若一个图中包含有k个连通分量,若要按照深度优先搜索得方法访问所有顶点,则必须调用(8、 A )次深度优先搜索遍历得算法。
A、 k B、 1 C、 k-1 D、 k+1
9、 若要把n个顶点连接为一个连通图,则至少需要(9、 C )条边。
A、 n B、 n+1 C、 n-1 D、 2n
10、 在一个具有n个顶点与e条边得无向图得邻接矩阵中,表示边存在得元素(又称为有效元素)得个数为( 10、 D )。
A、 n B、 n´e C、 e D、 2´e
11、 在一个具有n个顶点与e条边得有向图得邻接矩阵中,表示边存在得元素个数为( 11、 C )。
A、 n B、 n´e C、 e D、 2´e
12、 在一个具有n个顶点与e条边得无向图得邻接表中,边结点得个数为(12、 D )。
A、 n B、 n´e C、 e D、 2´e
13、 在一个具有n个顶点与e条边得有向图得邻接表中,保存顶点单链表得表头指针向量得大小至少为(13、 A )。
A、 n B、 2n C、 e D、 2e
14、 在一个无权图得邻接表表示中,每个边结点至少包含(14、 B )域。
A、 1 B、 2 C、 3 D、 4
15、 对于一个有向图,若一个顶点得度为k1,出度为k2,则对应邻接表中该顶点单链表中得边结点数为(15、 B )。
A、 k1 B、 k2 C、 k1-k2 D、 k1+k2
16、 对于一个有向图,若一个顶点得度为k1,出度为k2,则对应逆邻接表中该顶点单链表中得边结点数为(16、 C )。
A、 k1 B、 k2 C、 k1-k2 D、 k1+k2
17、 对于一个无向图,下面(17、 A )种说法就是正确得。
A、 每个顶点得入度等于出度 B、 每个顶点得度等于其入度与出度之与
C、 每个顶点得入度为0 D、 每个顶点得出度为0
18、 在一个有向图得邻接表中,每个顶点单链表中结点得个数等于该顶点得(18、 A)。
A、 出边数 B、 入边数 C、 度数 D、 度数减1
19、 若一个图得边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行深度优先搜索,得到得顶点序列可能为( 19、 B )。
A、 A,B,C,F,D,E B、 A,C,F,D,E,B
C、 A,B,D,C,F,E D、 A,B,D,F,E,C
20、 若一个图得边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行广度优先搜索,得到得顶点序列可能为(20、 D )。
A、 A,B,C,D,E,F B、 A,B,C,F,D,E
C、 A,B,D,C,E,F D、 A,C,B,F,D,E
21、 若一个图得边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索,得到得顶点序列可能为(21、 A　 )。
A、 1,2,5,4,3 B、 1,2,3,4,5
C、 1,2,5,3,4 D、 1,4,3,2,5
22、 若一个图得边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行广度优先搜索,得到得顶点序列可能为( 22、 C )。
A、 1,2,3,4,5 B、 1,2,4,3,5
C、 1,2,4,5,3 D、 1,4,2,5,3
23、 由一个具有n个顶点得连通图生成得最小生成树中,具有(23、 B )条边。
A、 n B、 n-1 C、 n+1 D、 2´n
24、 已知一个有向图得边集为{,,,,,},则由该图产生得一种可能得拓扑序列为(24、 A )。
A、 a,b,c,d,e B、 a,bd,e,b C、 a,c,b,e,d D、 a,c,d,b,e
二、填空题
1、 在一个图中,所有顶点得度数之与等于所有边数得________倍。1、 2
2、 在一个具有n个顶点得无向完全图中,包含有________条边,在一个具有n个顶点得有向完全图中,包含有________条边。 2、 n(n-1)/2,n(n-1)
3、 假定一个有向图得顶点集为{a,b,c,d,e,f},边集为{, , , , , },则出度为0得顶点个数为________,入度为1得顶点个数为______3、 2,4
4、 在一个具有n个顶点得无向图中,要连通所有顶点则至少需要________条边。4、 n-1
5、 表示图得两种存储结构为__________与__________。5、 邻接矩阵,邻接表
6、 在一个连通图中存在着________个连通分量。6、 1
7、 图中得一条路径长度为k,该路径所含得顶点数为________。7、 k+1
8、 若一个图得顶点集为{a,b,c,d,e,f},边集为{(a,b),(a,c),(b,c),(d,e)},则该图含有________个连通分量。 8、 3
9、 对于一个具有n个顶点得图,若采用邻接矩阵表示,则矩阵大小至少为________´________。9、 n,n
10、 对于具有n个顶点与e条边得有向图与无向图,在它们对应得邻接表中,所含边结点得个数分别为________与________。10、 2e,e
11、 在有向图得邻接表与逆邻接表表示中,每个顶点邻接表分别链接着该顶点得所有________与________结点。11、 出边,入边
12、 对于一个具有n个顶点与e条边得无向图,当分别采用邻接矩阵与邻接表表示时,求任一顶点度数得时间复杂度分别为________与________。 12、 On),O(e/n)
13、 假定一个图具有n个顶点与e条边,则采用邻接矩阵与邻接表表示时,其相应得空间复杂度分别为________与________。13、O(n2),O(n+e)
14、 一个图得边集为{(a,c),(a,e),(b,e),(c,d),(d,e)},从顶点a出发进行深度优先搜索遍历得到得顶点序列为____________,从顶点a出发进行广度优先搜索遍历得到得顶点序列为____________。 14、 acdeb,acedb (答案不唯一)
15、 一个图得边集为{,,,,,},从顶点a出发进行深度优先搜索遍历得到得顶点序列为____________,从顶点a出发进行广度优先搜索遍历得到得顶点序列为____________。15、 acfebd,acefbd (答案不唯一)
16、 图得________优先搜索遍历算法就是一种递归算法,图得________优先搜索遍历算法需要使用队列。 16、 深度,广度
17、 对于一个具有n个顶点与e条边得连通图,其生成树中得顶点数与边数分别为________与________。17、 n,n-1
18、 若一个连通图中每个边上得权值均不同,则得到得最小生成树就是________(唯一/不唯一)得。 18、 唯一
19、 根据图得存储结构进行某种次序得遍历,得到得顶点序列就是__(唯一/不唯一)得。19、 唯一
20、 假定一个有向图得边集为{,,,,,},对该图进行拓扑排序得到得顶点序列为________。 20、 aebdcf(答案不唯一)
三、应用题
1、 对于一个无向图6-11(a),假定采用邻接矩阵表示,试分别写出从顶点0出发按深度优先搜索遍历得到得顶点序列与按广度优先搜索遍历得到得顶点序列。
注:每一种序列都就是唯一得,因为都就是在存储结构上得到得。
1、 深度优先搜索序列:0,1,2,8,3,4,5,6,7,9
广度优先搜索序列:0,1,4,2,7,3,8,6,5,9
2、 对于一个有向图6-11(b),假定采用邻接表表示,并且假定每个顶点单链表中得边结点就是按出边邻接点序号从大到小得次序链接得,试分别写出从顶点0出发按深度优先搜索遍历得到得顶点序列与按广度优先搜索遍历得到得顶点序列。
注:每一种序列都就是唯一得,因为都就是在存储结构上得到得。
图6-11

0

1

6

5

9

4

8

3

7

2

(a)

6

0

3

4

5

1

2

7

8

(b)

2、 深度优先搜索序列:0,4,7,5,8,3,6,1,2
广度优先搜索序列:0,4,3,1,7,5,6,2,8
3、 已知一个无向图得邻接矩阵如图6-12(a)所示,试写出从顶点0出发分别进行深度优先与广度优先搜索遍历得到得顶点序列。
3、 深度优先搜索序列:0,2,3,5,6,1,4
广度优先搜索序列:0,2,3,5,6,1,4
4、 已知一个无向图得邻接表如图6-12(b)所示,试写出从顶点0出发分别进行深度优先与广度优先搜索遍历得到得顶点序列。

(a) (b)

图6-12

4、 深度优先搜索序列:0,3,6,4,1,5,2
广度优先搜索序列:0,3,2,6,5,4,1
5、 已知图6-13所示得一个网,按照Prim方法,从顶点1 出发,求该网得最小生成树得产生过程。
(a)

V1

V2

V3

V4

V5

V6

V7

60

50

65

40

45

70

50

52

42

30

V1

V2

V3

V4

V5

V6

V7

50

(c)

V1

V2

V3

V4

V5

V6

V7

(b)

5、 过程如图6-16所示
V1

V2

V3

V4

V5

V6

V7

50

40

45

50

42

30

(h)

图6-16

V1

V2

V3

V4

V5

V6

V7

50

40

50

42

30

(g)

V1

V2

V3

V4

V5

V6

V7

50

40

50

30

(f)

V1

V2

V3

V4

V5

V6

V7

50

40

(d)

V1

V2

V3

V4

V5

V6

V7

50

40

50

(e)

6、 已知图6-13所示得一个网,按照Kruskal方法,求该网得最小生成树得产生过程。
图6-13

V1

V2

V3

V4

V5

V6

V7

60

50

65

40

45

70

50

52

42

30

6、 求解过程如图6-17所示。
V1

V2

V3

V4

V5

V6

V7

(a)

30

V1

V2

V3

V4

V5

V6

V7

(b)

30

40

V1

V2

V3

V4

V5

V6

V7

(c)

30

40

42

图6-17

V1

V2

V3

V4

V5

V6

V7

(e)

30

40

42

45

50

V1

V2

V3

V4

V5

V6

V7

(f)

30

40

42

45

50

50

V1

V2

V3

V4

V5

V6

V7

(d)

30

40

42

45

7、 图6-14所示为一个有向网图及其带权邻接矩阵,要求对有向图采用Dijkstra算法,求从V0 到其余各顶点得最短路径。
(a) 有向带权图

V1

V0

V5

V4

V3

V2

5

10

60

30

100

50

20

10

∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞

(b) 带权邻接矩阵

图6-14 有向带权图及其邻接矩阵

7、 求解过程如下表所示。
终点
从v0到各终点得D值与最短路径得求解过程

i=1
i=2
i=3
i=4
i=5

V1
∞
∞
∞
∞
∞
无

V2
10 (v0,v2)

V3
∞
60 (v0,v2,v3)
50
(v0,v4,v3)

V4
30
(v0,v4)
30
(v0,v4)

V5
100
(v0,v5)
100
(v0,v5)
90
(v0,v4,v5)
60 (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、 图6-15给出了一个具有15个活动、11个事件得工程得AOE网,求关键路径。
v1

v5

v3

v8

v11

v9

v1001

a2=4

a5=3

a9=4

a13=10

a14=1

a15=6

v6

v7

v4

v2

图6-15

a1=3

a3=2

a4=1

a7=6

a8=8

a11=7

a12=4

a6=5

a10=2

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
活动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所示。
v1

v5

v3

v8

v11

v9

v1001

a2=4

a5=3

a9=4

a13=10

a14=1

a15=6

图6-18

四、算法设计题
1、 编写一个算法,求出邻接矩阵表示得无向图中序号为numb得顶点得度数。
int degree1(Graph & ga, int numb)
1、 int degree1(Graph & ga, int numb)
{ //根据无向图得邻接矩阵求出序号为numb得顶点得度数
int j,d=0;
for(j=0; jmb][j]!=MAXINT)
d++;
return (d);
}
2、 编写一个算法,求出邻接矩阵表示得有向图中序号为numb得顶点得度数。
int degree2(Graph & ga, int numb)
2、 int degree2(Graph & ga, int numb)
//根据有向图得邻接矩阵求出序号为numb得顶点得度数
{ int i,j,d=0;
//求出顶点numb得出度
for(j=0; j[j]!=MAXINT)
d++;
//求出顶点numb得入度
for(i=0; i得邻接表求出序号为numb得顶点得度数
{ int d=0;
vexnode * p=gl、adjlist[numb];
while(p!=NULL)
{ d++;
p=p->next;
}
return (d);
}
4、 编写一个算法,求出邻接表表示得有向图中序号为numb得顶点得度数。
int degree4(GraphL & gl, int numb)
4、 int degree4(GraphL & gl, int numb)
//根据有向图得邻接表求出序号为numb得顶点得度数
{ int d=0, i;