第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=n3）具有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 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 邻接表312341∧2∧443322∧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 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)12645322354∧5∧6∧∧6∧6∧【例6-3】已知一个无向图的邻接表如图6-5所示，要求：（1）画出该无向图；（2）根据邻接表，分别写出用DFS(深度优先搜索)和BFS（广度优先搜索）算法从顶点V0开始遍历该图后所得到的遍历序列。
图6-5 图的邻接表存储V6V0V1V5V3V4V223056043611∧2∧1∧210250∧6∧3∧4∧解：（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连通c21461（2）利用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. 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 。