图结构习题答案.doc

《图结构习题答案.doc》由会员分享，可在线阅读，更多相关《图结构习题答案.doc（17页珍藏版）》请在三一文库上搜索。

1、图结构习题答案第6章图【例-】回答下列问题：(1)具有n个顶点的连通图至少有多少条边?(2）具有个顶点的强连通图至少有多少条边？这样的图应该是什么形状?()具有个顶点的有向无环图最多有多少条边?解: (1）具有个顶点的连通图至少有n-1条边。这是一个与生成树相关的问题。生成树是一个连通图，它具有能够连通图中任何两个顶点的最小边集,任何一个生成树都具有n-1边。因此,具有n个顶点的连通图至少有n-1条边。（2）具有个顶点的强连通图至少有n条边,这样的图是一个由n个顶点构成的环。强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通,因此每个顶点至少要有一条以该顶点为弧头的

2、弧和一条以该顶点为弧尾的弧,每个顶点的入度和出度至少各为1,即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数2n/2n。(3）具有n个顶点的有向无环图最多有n（1)/条边。这是一个拓扑排序相关的问题。个有向无环图至少可以排出一个拓扑序列,不妨设这个顶点排成的拓扑序列为v1,v2，v3,，vn,那么在这个序列中,每个顶点i只可能与排在它后面的顶点之间存在着以v为弧尾的弧，最多有ni条,因此在整个图中最多有(n-1)+(n-）+ +2+=n(n-1)/2条边。2.图的存储结构常用的存储结构有邻接矩阵和邻接表。（1)邻接矩阵表示法设=(V，E)是有(1）个顶点的

3、图。则G的邻接矩阵是按如下定义的n阶方阵：0其它1当（i,Vj）E或E时costi,j=0 1 1 01 0 1 11 1 0 10 1 1 0A2=A1=0 1 10 0 10 0 0 例如，图-1中G1，2的邻接矩阵分别表示为1、2,矩阵的行列号对应于图6中结点的序号。由邻接矩阵的定义可知,无向图的邻接矩阵必定是对称阵;有向图的邻接矩阵不一定是对称的。 根据邻接矩阵，很容易判定任意两个顶点之间是否有边相连。求各顶点的度也是非常容易的。对于无向图,顶点Vi的度就是邻接矩阵中第行(或第j列)上非零元的个数，即。对于有向图，第行中非零元的个数为顶点Vi的出度,而第i列上的非零元个数为顶点Vi的入

4、度。（2）邻接表表示法图的邻接链表存储结构是一种顺序分配和链式分配相结合的存储结构括两个部分:一部分是向量,另一部分是链表。邻接链表中的表头部分是向量,用来存储n个表头结点。向量的下标指示顶点的序号。例如,对于图-中G和,其邻接链表如图6-3所示。在无向图的邻接表中顶点v的度就是第i个链表中结点的个数。在有向图中，第i个链表的结点数仅是vi的出度，求vi的入度,必须查遍n个链表才能得出。(a) G1的邻接表123332(b) G2的邻接表图6-3 邻接表31234124433221【例-】 图G(V,E),其中V=1,2,3,4,5,6，,1，4，,2,请画出图G，并写出其邻接矩阵和邻接表表示

5、。解：图G如图6-4中的(a)所示,图G的邻接矩阵和邻接表表示分别如图（)和(c）所示。对于这类问题，只要掌握了图的概念和存储结构就可以做出正确的答案。通常情况下对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求,因此,在写出邻接矩阵和邻接表表示时,只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是，对于邻接矩阵表示,如果顶点结点的顺序不同，那么邻接矩阵就不相同；对于邻接表表示,如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不相同。0 1 1 1 0 00 0 0 0 1 00 1 0 0 1 10 0 0 0 0 10 0 0 0 1 10 0 0 0 0 0(b)图6

6、-4 图及其存储结构1(a)34256(c)126453223545666【例-3】已知一个无向图的邻接表如图6-所示,要求:（1）画出该无向图；(2）根据邻接表，分别写出用DS(深度优先搜索)和BFS(广度优先搜索)算法从顶点V0开始遍历该图后所得到的遍历序列。图6-5 图的邻接表存储V6V0V1V5V3V4V22305604361121210250634解：（1)该无向图如图6所示。v0v1v2v3v4v6v5图6-6 无向图（2）根据该无向图的邻接表表示，从顶点V开始的深度优先遍历序列为:V0、2、V、V1、V6、V。广度优先遍历序列为0、2、V5、V6、V、V3、4。从图的逻辑结构上来

7、讲，从图中某个顶点开始的深度(或广度)优先遍历序列不一定是唯一的。这是因为在逻辑结构中,并没有对每个顶点的所有邻接点规定它们之间的先后顺序,这样在搜索算法中选取第个邻接点和下一个邻接点时可能会有不同的结果。但是在存储结构中，明确地给出了邻接点的先后顺序,这时深度优先和广度优先遍历序列就是唯一的。【例6-】对于如图-8所示的带权无向图,用图示说明:（1）利用Prim算法从顶点a开始构造最小生成树的过程；3e1fdcbag97946218548图6-8 带权无向图(2）利用Krusal算法构造最小生成树的过程;解：(1）利用Prim算法从顶点开始构造最小生成树的过程如图6-9所示。aefdcbg初

8、始状态aefdcbg连通e2aefdcbg连通g21aefdcbg连通d2133aefdcbg连通f2143aefdcbg连通b2146图6-9 用Prim算法构造最小生成树的过程3aefdcbg连通c21461(2)利用Kukl算法构造最小生成树的过程如图10所示。aefdcbg初始状态aefdcbg增加第2条边11aefdcbg增加第1条边13aefdcbg增加第5条边21413aefdcbg增加第4条边211aefdcbg增加第3条边211图6-10 用Kruskal算法构造最小生成树的过程3aefdcbg增加第6条边21461【例6-5】一个带权无向图的最小生成树是否一定唯一?在什么情

9、况下构造出的最小生成树可能不唯一?解:一个带权无向图的最小生成树不一定是唯一的。从Kuskal算法构造最小生成树的过程可以看出,当从图中选择当前权值最小的边时,如果存在多条这样的边,并且这些边与已经选取的边构成回路,此时这些边就不可能同时出现在一棵最小生成树中,对这些边的不同选择结果可能会产生不同的最小生成树。习题6一、单项选择题 1 在一个具有n个顶点的有向图中,若所有顶点的出度数之和为s，则所有顶点的入度数之和为(1. )。. sB. s-C.s. . 在一个具有个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为( . D)。A.sB. -C. s+D2s .在一个具有n

10、个顶点的无向图中,若具有e条边，则所有顶点的度数之和为(3. )。AnB. eC. n+eD. 2e 4. 在一个具有n个顶点的无向完全图中,所含的边数为(. C)。A nB. (n-1)C. n()/2D. n（n+1)2 5. 在一个具有n个顶点的有向完全图中,所含的边数为( 5B )。A. n B. n(n-1) C. n(n-1)/ D. n(n+）/2 .在一个无向图中,若两顶点之间的路径长度为，则该路径上的顶点数为( 6. )。 B. k1 C. k+2 . 2 7. 对于一个具有n个顶点的无向连通图,它包含的连通分量的个数为(7. B)。A. 0 B. 1 C. n .n1 8.

11、 若一个图中包含有k个连通分量,若要按照深度优先搜索的方法访问所有顶点,则必须调用(8. A )次深度优先搜索遍历的算法。A. k B. 1 C. k-1 D. k+1 9.若要把n个顶点连接为一个连通图，则至少需要（. C )条边。A. n n+1 C. n1 D 2 10在一个具有个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素(又称为有效元素)的个数为（ 10. D)。A.n ne C. e D.e 11. 在一个具有n个顶点和条边的有向图的邻接矩阵中,表示边存在的元素个数为(11 C )。. n B. e C. e D. 2 12 在一个具有n个顶点和e条边的无向图的邻接表中，边结

12、点的个数为(1 ）。A n C.e D. 13. 在一个具有n个顶点和e条边的有向图的邻接表中,保存顶点单链表的表头指针向量的大小至少为(13. A ）。A. n . 2n C. e D. 2e 4.在一个无权图的邻接表表示中，每个边结点至少包含(14. B ）域。A 1 . C.3 D.4 5. 对于一个有向图,若一个顶点的度为k1,出度为k2,则对应邻接表中该顶点单链表中的边结点数为(5.B）。A. 1 B. k2 C. 1-k D.k1+2 16. 对于一个有向图，若一个顶点的度为k1，出度为2，则对应逆邻接表中该顶点单链表中的边结点数为(16 C )。A. k1 B. k2 C.k-

13、D k1k 17. 对于一个无向图,下面(1 A )种说法是正确的。. 每个顶点的入度等于出度 B每个顶点的度等于其入度与出度之和C. 每个顶点的入度为0 D. 每个顶点的出度为0 18. 在一个有向图的邻接表中,每个顶点单链表中结点的个数等于该顶点的(18.A)。A. 出边数 入边数 C. 度数 D.度数减1 1 若一个图的边集为(,B)，（A，C)，(B,D)，（,F),(,E）,（D,)，则从顶点开始对该图进行深度优先搜索,得到的顶点序列可能为（ 19 B )。A. A，B,D，E B.A，C，F,E，C A,F, A，B,D，F,，C 0. 若一个图的边集为(,B),(A,C),(,）

14、,(C,F）,(,E),(D,F)，则从顶点A开始对该图进行广度优先搜索,得到的顶点序列可能为(20. D ）。A.A,D，E,F A，B,C,F，D,EC A,B，D, . A，C,，F，D, 21 若一个图的边集为,2,2,，,3,5，4，3，则从顶点1开始对该图进行深度优先搜索,得到的顶点序列可能为(2. A )。. ，2,5,，3 B. 1，2,3,5C. ,2,5,3,4 D. 1,4，3,2，5 2.若一个图的边集为，,3，则从顶点开始对该图进行广度优先搜索,得到的顶点序列可能为( 2 C)。A1,，3，4，5 B. 1,2,4,3，C. 1,2，4,5，3 D. ，2,3 23.

15、 由一个具有n个顶点的连通图生成的最小生成树中,具有(2. B )条边。A Bn-1 C. n+ D. 2n 24 已知一个有向图的边集为，a，c,d，,，则由该图产生的一种可能的拓扑序列为(24.A）。 a,c,e . ，b,d,e, C a,c，b,e, D a,c,d,b，e二、填空题1. 在一个图中，所有顶点的度数之和等于所有边数的_倍。.2 .在一个具有n个顶点的无向完全图中，包含有_条边,在一个具有n个顶点的有向完全图中,包含有_条边。 2. n(-1）/2,n(n-1) . 假定一个有向图的顶点集为a,，c,f,边集为, a，e，, , ,则出度为的顶点个数为_,入度为1的顶点个

16、数为_。3. 2,4 4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要_条边。4.n-1 5 表示图的两种存储结构为_和_。5 邻接矩阵,邻接表 . 在一个连通图中存在着_个连通分量。6. 1 . 图中的一条路径长度为，该路径所含的顶点数为_。7. k1 . 若一个图的顶点集为a，b,c,d,f,边集为(,b），(,),(b，c),(d，e），则该图含有_个连通分量。 . 3 9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为_。9 n，n . 对于具有个顶点和e条边的有向图和无向图,在它们对应的邻接表中，所含边结点的个数分别为_和_。10 2e， 11. 在有向

17、图的邻接表和逆邻接表表示中,每个顶点邻接表分别链接着该顶点的所有_和_结点。11. 出边，入边 12. 对于一个具有个顶点和条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为_和_。1. O(n),O(/） 13. 假定一个图具有n个顶点和条边，则采用邻接矩阵和邻接表表示时,其相应的空间复杂度分别为_和_。13.O（2），O（n+e） 14. 一个图的边集为(a，c),（,e),(b,)，(c，d),(,e)，从顶点出发进行深度优先搜索遍历得到的顶点序列为_，从顶点a出发进行广度优先搜索遍历得到的顶点序列为_。 14. acdeb，aedb （答案不唯一) 5.

18、一个图的边集为a，c，,e,d,从顶点a出发进行深度优先搜索遍历得到的顶点序列为_,从顶点出发进行广度优先搜索遍历得到的顶点序列为_。5.afbd，acefb （答案不唯一) 1 图的_优先搜索遍历算法是一种递归算法,图的_优先搜索遍历算法需要使用队列。16. 深度，广度 17. 对于一个具有个顶点和条边的连通图,其生成树中的顶点数和边数分别为_和_。17 ，n- . 若一个连通图中每个边上的权值均不同，则得到的最小生成树是_(唯一/不唯一）的。18 唯一 9. 根据图的存储结构进行某种次序的遍历,得到的顶点序列是_（唯一/不唯一）的。1. 唯一 2.假定一个有向图的边集为，a,e，,d，c,

19、e,b,对该图进行拓扑排序得到的顶点序列为_。 20. aebdc(答案不唯一）三、应用题1. 对于一个无向图611()，假定采用邻接矩阵表示,试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。注:每一种序列都是唯一的，因为都是在存储结构上得到的。1. 深度优先搜索序列：0,1,2,3，4，5,6,9 广度优先搜索序列:0,1，4,，7,8,6,5，9 .对于一个有向图611(b),假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的,试分别写出从顶点出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点

20、序列。 注：每一种序列都是唯一的，因为都是在存储结构上得到的。 图6-110165948372(a)603451278(b)2. 深度优先搜索序列:0,7,5,8,1,2 广度优先搜索序列:，,，7,，2，83 已知一个无向图的邻接矩阵如图6-12()所示,试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。3. 深度优先搜索序列：,2,3,5,，1,4 广度优先搜索序列:0，3,5，6，1,4 4已知一个无向图的邻接表如图6-2()所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。(a) (b)图6-124. 深度优先搜索序列:,3,6，4,2 广度优

21、先搜索序列:0,3,2,5,，5 已知图6-13所示的一个网，按照Pim方法,从顶点出发，求该网的最小生成树的产生过程。 (a)V1V2V3V4V5V6V760506540457050524230V1V2V3V4V5V6V750(c)V1V2V3V4V5V6V7(b). 过程如图6-所示V1V2V3V4V5V6V7504045504230(h)图6-16V1V2V3V4V5V6V75040504230(g)V1V2V3V4V5V6V750405030(f)V1V2V3V4V5V6V75040(d)V1V2V3V4V5V6V7504050(e)6. 已知图6-1所示的一个网,按照Krsk方法,求

22、该网的最小生成树的产生过程。图6-13V1V2V3V4V5V6V760506540457050524230. 求解过程如图61所示。V1V2V3V4V5V6V7(a)30V1V2V3V4V5V6V7(b)3040V1V2V3V4V5V6V7(c)304042图6-17V1V2V3V4V5V6V7(e)3040424550V1V2V3V4V5V6V7(f)304042455050V1V2V3V4V5V6V7(d)304042457. 图4所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dikstra算法,求从0 到其余各顶点的最短路径。(a) 有向带权图 V1V0V5V4V3V2510603

23、0100502010 10 30 100 5 50 10 20 60 (b) 带权邻接矩阵图6-14 有向带权图及其邻接矩阵.求解过程如下表所示。终点 从v到各终点的值和最短路径的求解过程 i= 2 =3 i=4 i=5 V 无 V2 10 (v,v2)V3 60 (v0,v2,v3) 50 (v0,v4，3）V4 0(v0，v4） 30 (v0,v） V5 10 (v0,v5) 10 （v0,v5) 90 (0,v4，v) 6 (v0,v4，v，v5)Vj V 4 V3 V S v0,v2v0,2,vv,v2,3,v0,v2，v3，4,v58. 图6-1给出了一个具有15个活动、11个事件的

24、工程的AOE网，求关键路径。v1v5v3v8v11v9v1001a2=4a5=3a9=4a13=10a14=1a15=6v6v7v4v2图6-15a1=3a3=2a4=1a7=6a8=8a11=7a12=4a6=5a10=28. 求解过程如下：事件的最早发生时间vek。 v (1)= e ()3 v （3)4 v (4)=ve(2）+25 ve (5）mve(2)+1,e（)+= v (6)=ve()+59 e (7）=xve（4)+6,ve(5）8=15 ve (8)=ve（5)4=11 ve (）axe（8）+10,ve(6)+221 ve （1)mave(8)+4，ve(）+=22 ve

25、 （1）=mve（7）+,ve(10)+6=28事件的最迟发生时间vl。 vl （11）=ve (1)=28 vl（10）= vl (1)-6= l (9)= vl （10)-1=2 ()=min l (10)-, vl (9）-1011 v (7)= vl (11)7=21 vl (6) vl()-=19 v (5)mi vl (7)-8,v （)4=7 v（4)= vl (7)-6=15 vl (）=minl(5)3, v （)5= vl（2）=min vl (4)-2， l (）-=6 vl (1)=min(2)-3， l (3)-4=0活动i的最早开始时间ei和最晚开始时间l。 活动1

26、 e （1)=ve ()= l(1)=v(2) -3 =3 活动a2 e（2)=ve (1)0 l (2)=vl （3）- 4= 活动3 e (3)=e ()= l (）=vl () - 213 活动a4 (4)=ve ()= l (4）=vl (5) - 1=6 活动a5 e()=ve(3)=4 l (5)=v () 4 活动6 （6)=ve (3)=4 ()=l(6)- = 活动a7 e （7）v (4）5 l(7)=vl (7） - 6=1 活动a8 e（8)ve (5)7 l（8)=vl（)8=13 活动a9 e (9)=v（5)=7 l （)vl(8）- 47 活动a10 (10）=

27、v (6)= l(10)(9) - 2=19 活动a11 e ()= (7）=15 l(11)=vl （1) =21 活动a2 e （2)e (8）=11 l （12）vl(10)- 4= 活动a13 e (13)=ve （8)=11 l (13)= （9) - 10=11 活动a1 e ()= （)=21 (4)=vl (1)-1=21 活动a15 e(15)=v(10)= (5)vl (1) 6 22最后,比较ei和li的值可判断出a2，5，a9,，a1,15是关键活动,关键路径如图18所示。v1v5v3v8v11v9v1001a2=4a5=3a9=4a13=10a14=1a15=6图6-

28、18四、算法设计题1. 编写一个算法,求出邻接矩阵表示的无向图中序号为numb的顶点的度数。int degre1(raph&ga, int nub）1. n degee1(Graph &g，in umb） /根据无向图的邻接矩阵求出序号为nmb的顶点的度数 int j，d0; or(=0；ga.vexnum; j+)i (a.cstuj!=0 &ga.cstubj!=MANT)d+; return(d)；2.编写一个算法,求出邻接矩阵表示的有向图中序号为nmb的顶点的度数。int degre2（Gra & ga， int numb）. nt degree（Grah & ga, nt ub)/根据有向图的邻接矩阵求出序号为nmb的顶点的度数 it i,0； /求出顶点u的出度 or(=0;jga.exnum; j+) f(a.numbj!= & .costnmbj！=MXNT) d+; /求出顶点nmb的入度 or(i=0;inext; rern (d); 编写一个算法,求出邻接表表示的有向图中序号为numb的顶点的度数。in dree(ap &g,intnumb)4. n egee4(GraphL & l, it nm）/根据有向图的邻接表求出序号为numb的顶点的度数 nt d=0,；vexnode * pgl.adjlstnu