图结构习题答案

1、选定的文档第6章图示例6-1回答以下问题：(1)有n个顶点的连通图中有多少条边？(2)有n个顶点的强连通图有多少条边？这幅画应该是什么形状？(3)有n个顶点的有向无环图有几条边？解决方案：(1)一个有N个顶点的连通图至少有n-1条边。这是一个与生成树相关的问题。生成树是一个连通图，它有连接图中任意两个顶点的最小边集，并且任何生成树都有n-1条边。因此，一个有n个顶点的连通图至少有n-1条边。(2)有n个顶点的强连通图至少有n条边。这样的图是由n个顶点组成的环。强连通图是相对于有向图的。由于强连通图要求图中的任意两个顶点可以相互连接，因此每个顶点必须至少有一条以顶点为弧首的弧和一条以顶点为弧尾的

2、弧，并且每个顶点的进出度必须至少为1，即顶点的度数必须至少为2，因此边数=2n/2=n可以根据顶点数、边数和图中每个点的度数之间的关系来计算。(3)具有n个顶点的有向无环图最多有n (n-1)/2条边。这是一个拓扑排序相关的问题。一个有向无环图可以释放至少一个拓扑序列。假设n个顶点排列的拓扑序列是v1，v2，v3，vn。那么在这个序列中，每个顶点vi只能有一个以vi为弧尾的弧，其最大值为N-1，所以最多有(N-1) (N-2).21=整个图中的N (N-1)/2条边。2.图的存储结构常见的存储结构包括邻接矩阵和邻接表。(1)邻接矩阵表示设g=(v，e)是一个有n(n1)个顶点的图。那么g的邻接

3、矩阵是如下定义的n阶方阵：0其他1当(vi，vj) e或vi，vj e成本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和G2的邻接矩阵分别表示为A1和A2，矩阵的行数和列数对应于图6-1中节点的序列号。根据邻接矩阵的定义，无向图的邻接矩阵必须是对称矩阵。有向图的邻接矩阵不一定是对称的。根据邻接矩阵，很容易确定任意两个顶点之间是否有边连接。也很容易找到每个顶点的度数。对于无向图，顶点Vi的度数是邻接矩阵的第一行(或j列)上非零元素的数量，即对于有向图，第一行中非零元素的数量是顶点Vi的度数，而第一列中非零元素的数量

4、是顶点Vi的度数。(2)邻接表表示图的邻接链表存储结构是顺序分配和链式分配相结合的存储结构，包括两部分：一部分是向量，另一部分是链表。相邻链表的头部分是一个向量，用来存储n个头节点。向量的下标表示顶点的序号。例如，对于图6-1中的G1和G2，它们的相邻链表在图6-3中示出。无向图的邻接表中顶点vi的度是第I个链表中的节点数。在有向图中，第I个链表中的节点数只有vi度。要找到vi的程度，必须在n个链表中搜索才能得到。G1邻接表123332(二)G2邻接表图6-3邻接表31234124433221示例6-2图G=(V，E)，其中V=1，2，3，4，5，6，E=1，2，1，3，1，4，2，5，3，2

5、，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

6、0(b)图6-4及其存储结构1(a)34256(c)126453223545666例6-3众所周知，无向图的邻接表如图6-5所示，它要求：(1)绘制无向图；(2)根据邻接表，从顶点V0开始遍历图后，分别写出深度优先搜索算法和宽度优先搜索算法得到的遍历序列。图6-5邻接表存储V6V0第五颅神经的眼支V5V3V4V22305604361121210250634解决方案：(1)无向图如图6-6所示。v0第五颅神经的眼支v2v3v4v6v5图6-6无向图(2)根据无向图的邻接表表示，从顶点V0开始的深度优先遍历序列为：V0、V2、V3、V1、V4、V6、V5。广度优先遍历序列是V0、V2、V5、V6、

7、V1、V3、V4。从图的逻辑结构来看，从图中一个顶点开始的深度(或宽度)优先遍历序列不一定是唯一的。这是因为在逻辑结构中，每个顶点的所有相邻点没有顺序，因此当在搜索算法中选择第一个和下一个相邻点时，可以获得不同的结果。然而，在存储结构中，相邻点的序列被清楚地给出，然后深度优先和宽度优先遍历序列是唯一的。示例6-4对于图6-8所示的加权无向图，使用了以下图示：(1)用Prim算法从顶点A构造最小生成树；3e1fdcbag97946218548图6-8加权无向图(2)用Kruskal算法构造最小生成树的过程；解决方案：(1)使用Prim算法从顶点A构造最小生成树的过程如图6-9所示。aefdcbg

8、初态aefdcbg连通e2aefdcbg连通g21aefdcbg连通d2133aefdcbg连接f2143aefdcbg连接b2146图6-9用Prim算法构造最小生成树的过程3aefdcbg连接c21461(2)用Kruskal算法构造最小生成树的过程如图6-10所示。aefdcbg初态aefdcbg添加第二条边11aefdcbg添加第一条边13aefdcbg添加第五条边21413aefdcbg添加第四条边211aefdcbg添加第三条边211图6-10用Kruskal算法构造最小生成树的过程3aefdcbg添加第六条边21461例6-5加权无向图的最小生成树一定是唯一的吗？在什么情况下构造

9、的最小生成树可能不是唯一的？解决方案：加权无向图的最小生成树不一定是唯一的。从用Kruskal算法构造最小生成树的过程中可以看出，当从图中选择具有最低当前权重的边时，如果有多个这样的边，并且这些边与已经选择的边形成循环，那么这些边不能同时出现在最小生成树中，并且这些边的不同选择结果可能产生不同的最小生成树。练习6I .选择题1.在具有N个顶点的有向图中，如果所有顶点的度数之和为S，则所有顶点的度数之和为(1。a)。A.某人s-1C。1D南部。n2.在具有N个顶点的有向图中，如果所有顶点的度数之和为S，则所有顶点的度数之和为(2。d)。A.s B. s-1C。1D南部。2s3.在有n个顶点的无向

10、图中，如果有e条边，所有顶点的度数之和是(3。d)。A.注意欧共体。n eD .2e4.在有n个顶点的无向完全图中，包含的边数是(4。c)。A.nB。北(北-1)北(北-1)/2D。n(n 1)/25.在有n个顶点的有向完全图中，包含的边数是(5。b)。A.注：n . b .(n-1)c . n(n-1)/2d . n(n-1)/26.在无向图中，如果两个顶点之间的路径长度为k，则路径上的顶点数为(6。b)。A.公元前1世纪至公元2世纪7.对于有n个顶点的无向连通图，它包含的连通分量数是(7。b)。A.公元前0年1月1日8.如果一个图包含k个连通分量，要根据深度优先搜索方法访问所有顶点，则(8

11、。a)必须调用深度优先搜索遍历算法。A.公元前1世纪至公元1世纪9.要将N个顶点连接成一个连通图，至少需要(9。c)需要边缘。A.n . b . n . 1 c . n-1d . 2n10.在具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素(也称为有效元素)的数量是(10)。d)。A.东北偏东211.在具有N个顶点和E条边的有向图的邻接矩阵中，表示边的元素数是(11)。c)。A.东北偏东212.在有n个顶点和e条边的无向图的邻接表中，边节点的数量是(12。d)。A.东北偏东213.在具有N个顶点和E条边的有向图的邻接表中，保持顶点的单个链表的头部中的指针向量的大小至少为(13。a)。A.公元前2世纪至公元2世纪14.在未授权图的邻接表表示中，每个边节点至少包含(14。b)字段。A.1生于公元前2，3生于公元415.对于有向图，如果顶点的度数为k1，输出的度数为k2，则对应于邻