图结构习题答案

第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阶方阵：例如，图6-1中G1，Ｇ2的邻接矩阵分别表示为A1、A2，矩阵的行列号对应于图6-1中结点的序号。由邻接矩阵的定义可知，无向图的邻接矩阵必定是对称阵；有向图的邻接矩阵不一定是对称的。根据邻接矩阵，很容易判定任意两个顶点之间是否有边相连。求各顶点的度也是非常容易的。对于无向图，顶点Vi的度就是邻接矩阵中第i行(或第j列)上非零元的个数，即0其它1当（Ｖi,Vj）∈E或Ｖi,Vj∈E时cost[i,j]=0110101111010110A2=A1=011001000niijitd1],[cos。对于有向图，第i行中非零元的个数为顶点Vi的出度，而第i列上的非零元个数为顶点Vi的入度。（2）邻接表表示法图的邻接链表存储结构是一种顺序分配和链式分配相结合的存储结构括两个部分：一部分是向量，另一部分是链表。邻接链表中的表头部分是向量，用来存储n个表头结点。向量的下标指示顶点的序号。例如，对于图6-1中G1和G2，其邻接链表如图6-3所示。在无向图的邻接表中顶点vi的度就是第i个链表中结点的个数。在有向图中，第i个链表的结点数仅是vi的出度，求vi的入度，必须查遍n个链表才能得出。【例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)所示。对于这类问题，只要掌握了图的概念和存储结构就可以做出正确的答案。通常情况下．对图的顶点排列顺序和各顶点的邻接点排列顺序并没有特定要求，因此，在写出邻接矩阵和邻接表表示时，只要按照某种排列顺序画出相应的结构图就可以了。但应该注意的是，对于邻接矩阵表示，如果顶点结点的顺序不同，那么邻接矩阵就不相同；对于邻接表表示，如果顶点结点的顺序或者邻接点的顺序不同，那么邻接表就不相同。(a)G1的邻接表123332∧∧∧(b)G2的邻接表图6-3邻接表312341∧2∧443322∧1∧011100000010010011000001000011000000(b)图6-4图及其存储结构1(a)34256(c)12645322354∧5∧6∧∧6∧6∧【例6-3】已知一个无向图的邻接表如图6-5所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。解：（1）该无向图如图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开始构造最小生成树的过程；（2）利用Kruskal算法构造最小生成树的过程；v0v1v2v3v4v6v5图6-6无向图图6-5图的邻接表存储V6V0V1V5V3V4V223056043611∧2∧1∧210250∧6∧3∧4∧3e1fdcbag97946218548图6-8带权无向图解：（1）利用Prim算法从顶点a开始构造最小生成树的过程如图6-9所示。（2）利用Kruskal算法构造最小生成树的过程如图6-10所示。aefdcbg初始状态aefdcbg连通e2aefdcbg连通g21aefdcbg连通d2133aefdcbg连通f2143aefdcbg连通b2146图6-9用Prim算法构造最小生成树的过程3aefdcbg连通c21461aefdcbg初始状态aefdcbg增加第2条边11aefdcbg增加第1条边1【例6-5】一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？解：一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。习题6一、单项选择题1.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为(1.A)。A.sB.s-1C.s+1D.n2.在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为(2.D)。A.sB.s-1C.s+1D.2s3.在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为(3.D)。A.nB.eC.n+eD.2e4.在一个具有n个顶点的无向完全图中，所含的边数为(4.C)。3aefdcbg增加第5条边21413aefdcbg增加第4条边211aefdcbg增加第3条边211图6-10用Kruskal算法构造最小生成树的过程3aefdcbg增加第6条边21461A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/25.在一个具有n个顶点的有向完全图中，所含的边数为(5.B)。A.nB.n(n-1)C.n(n-1)/2D.n(n+1)/26.在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为(6.B)。A.kB.k+1C.k+2D.2k7.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为(7.B)。A.0B.1C.nD.n+18.若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用(8.A)次深度优先搜索遍历的算法。A.kB.1C.k-1D.k+19.若要把n个顶点连接为一个连通图，则至少需要(9.C)条边。A.nB.n+1C.n-1D.2n10.在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为(10.D)。A.nB.neC.eD.2e11.在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为(11.C)。A.nB.neC.eD.2e12.在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为(12.D)。A.nB.neC.eD.2e13.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为(13.A)。A.nB.2nC.eD.2e14.在一个无权图的邻接表表示中，每个边结点至少包含(14.B)域。A.1B.2C.3D.415.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为(15.B)。A.k1B.k2C.k1-k2D.k1+k216.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为(16.C)。A.k1B.k2C.k1-k2D.k1+k217.对于一个无向图，下面(17.A)种说法是正确的。A.每个顶点的入度等于出度B.每个顶点的度等于其入度与出度之和C.每个顶点的入度为0D.每个顶点的出度为018.在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的(18.A)。A.出边数B.入边数C.度数D.度数减119.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为(19.B)。A.A,B,C,F,D,EB.A,C,F,D,E,BC.A,B,D,C,F,ED.A,B,D,F,E,C20.若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为(20.D)。A.A,B,C,D,E,FB.A,B,C,F,D,EC.A,B,D,C,E,FD.A,C,B,F,D,E21.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为(21.A)。A.1,2,5,4,3B.1,2,3,4,5C.1,2,5,3,4D.1,4,3,2,522.若一个图的边集为{1,2,1,4,2,5,3,1,3,5,4,3}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为(22.C)。A.1,2,3,4,5B.1,2,4,3,5C.1,2,4,5,3D.1,4,2,5,323.由一个具有n个顶点的连通图生成的最小生成树中，具有(23.B)条边。A.nB.n-1C.n+1D.2n24.已知一个有向图的边集为{a,b,a,c,a,d,b,d,b,e,d,e}，则由该图产生的一种可能的拓扑序列为(24.A)。A.a,b,c,d,eB.a,b,d,e,bC.a,c,b,e,dD.a,c,d,b,e二、填空题1.在一个图中，所有顶点的度数之和等于所有边数的________倍。1.22.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。2.n(n-1)/2，n(n-1)3.假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{a,c,a,e,c,f,d,c,e,b,e,d}，则出度为0的顶点个数为________，入度为1的顶点个数为________。3.2，44.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。4.n-15.表示图的两种存储结构为__________和__________。5.邻接矩阵，邻接表6.在一个连通图中存在着________个连通分量。6.17.图中的一条路径长度为k，该路径所含的顶点数为________。7.k+18.若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。8.39.对于一个具有n个顶点的