-第6章图【例6-1】答复以下问题：1具有n个顶点的连通图至少有多少条边?2具有n个顶点的强连通图至少有多少条边?这样的图应该是什么形状?3具有n个顶点的有向无环图最多有多少条边?解：1具有n个顶点的连通图至少有n-1条边。这是一个与生成树相关的问题。生成树是一个连通图，它具有能够连通图中任何两个顶点的最小边集，任何一个生成树都具有n-1边。因此，具有n个顶点的连通图至少有n-1条边。2具有n个顶点的强连通图至少有n条边，这样的图是一个由n个顶点构成的环。强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通，因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧，每个顶点的入度和出度至少各为1，即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数=2n/2=n。3具有n个顶点的有向无环图最多有n(n1)/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(n1)个顶点的图。则G的邻接矩阵是按如下定义的n阶方阵：0其它1当i,VjE或E时costi,j=0 1 1 01 0 1 11 1 0 10 1 1 0A2=A1=0 1 10 0 10 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的邻接表123332(b) G2的邻接表图6-3 邻接表31234124433221【例6-2】图G(V，E)，其中V=1,2,3,4,5,6，,，请画出图G，并写出其邻接矩阵和邻接表表示。解：图G如图6-4中的(a)所示，图G的邻接矩阵和邻接表表示分别如图(b)和(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-4 图及其存储构造1(a)34256(c)126453223545666【例6-3】一个无向图的邻接表如图6-5所示，要求：1画出该无向图；2根据邻接表，分别写出用DFS(深度优先搜索)和BFS广度优先搜索算法从顶点V0开场遍历该图后所得到的遍历序列。图6-5 图的邻接表存储V6V0V1V5V3V4V22305604361121210250634解：1该无向图如图6-6所示。v0v1v2v3v4v6v5图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开场构造最小生成树的过程；3e1fdcbag97946218548图6-8 带权无向图2利用Kruskal算法构造最小生成树的过程；解：1利用Prim算法从顶点a开场构造最小生成树的过程如图6-9所示。aefdcbg初始状态aefdcbg连通e2aefdcbg连通g21aefdcbg连通d2133aefdcbg连通f2143aefdcbg连通b2146图6-9 用Prim算法构造最小生成树的过程3aefdcbg连通c214612利用Kruskal算法构造最小生成树的过程如图6-10所示。aefdcbg初始状态aefdcbg增加第2条边11aefdcbg增加第1条边13aefdcbg增加第5条边21413aefdcbg增加第4条边211aefdcbg增加第3条边211图6-10 用Kruskal算法构造最小生成树的过程3aefdcbg增加第6条边21461【例6-5】一个带权无向图的最小生成树是否一定唯一.在什么情况下构造出的最小生成树可能不唯一.解：一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。习题6一、单项选择题1. 在一个具有n个顶点的有向图中，假设所有顶点的出度数之和为s，则所有顶点的入度数之和为(1. A )。A. sB. s-1C. s+1D. n2. 在一个具有n个顶点的有向图中，假设所有顶点的出度数之和为s，则所有顶点的度数之和为(2. D)。A. s B. s-1C. s+1D. 2s3. 在一个具有n个顶点的无向图中，假设具有e条边，则所有顶点的度数之和为(3. D )。A. n B. eC. n+eD. 2e4. 在一个具有n个顶点的无向完全图中，所含的边数为(4. C)。A. nB. n(n-1)C. n(n-1)/2D. n(n+1)/2 5. 在一个具有n个顶点的有向完全图中，所含的边数为( 5. B )。A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/26. 在一个无向图中，假设两顶点之间的路径长度为k，则该路径上的顶点数为( 6. B )。A. k B. k+1 C. k+2 D. 2k7. 对于一个具有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+19. 假设要把n个顶点连接为一个连通图，则至少需要(9. C )条边。A. n B. n+1 C. n-1 D. 2n 10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素又称为有效元素的个数为