图结构习题答案

1、第六章图示例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个2.图的存储结构常用的存储结构是邻接矩阵和邻接表。(1)邻接矩阵表示设g=(v，e)是一个有n个顶点(n 1)的图。g的邻接矩阵是一个n阶方

3、阵，定义如下：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的度数是邻接矩阵第I行(或第j列)中非零元素的数目，即对于有向图，第I行中非零元素的数目是顶点Vi的度数，而第I列中非零元素的数目是顶点Vi的

4、度数。(2)邻接表表示图的邻接链表存储结构是一种结合顺序分配和链式分配的存储结构，它包括两部分：一部分是向量，另一部分是链表。邻接链表中的头部分是一个向量，用于存储N个头节点。向量的下标表示顶点的序号。例如，对于图6-1中的G1和G2，它们的邻接链表如图6-3所示。在无向图的邻接表中，顶点vi的度数是第I个链表中的节点数。在有向图中，第I个链表中的节点数只有vi的度数。要找到vi的程度，我们必须搜索N个链表。(a)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，

5、3，2，3，5，3，6，4，6，5，6，请画一个图G，并写出它的邻接矩阵和邻接表表示。解决方案：图G如图6-4 (a)所示，图G的邻接矩阵和邻接表分别如图(b)和(c)所示。只要我们掌握了图形的概念和存储结构，我们就能对这些问题给出正确的答案。通常，对顶点排列顺序和每个顶点的邻接点排列顺序没有具体要求。因此，在编写邻接矩阵和邻接表表示时，只需按照一定的排列顺序画出相应的结构图。但是，应该注意的是，对于邻接矩阵表示，如果顶点节点的顺序不同，那么邻接矩阵也不同；对于邻接表表示，如果顶点节点的顺序或o0 0 0 0 1 00 1 0 0 1 10 0 0 0 0 10 0 0 0 1 10 0 0

6、0 0 0(b)图6-4及其存储结构1(a)34256(c)126453223545666例6-3无向图的邻接表如图6-5所示，它要求：(1)画无向图；(2)根据邻接表，分别编写了深度优先搜索算法和BFS宽度优先搜索算法从顶点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、V1、V

7、3和V4。从图的逻辑结构来看，从图中的一个顶点开始的深度(或宽度)第一遍历序列不一定是唯一的。这是因为，在逻辑结构中，没有指定每个顶点的所有相邻点的顺序，所以在搜索算法中选择第一个相邻点和下一个相邻点时可能会有不同的结果。然而，在存储结构中，相邻点的顺序是明确给出的，然后深度优先和宽度优先遍历序列是唯一的。示例6-4说明如图6-8所示的加权无向图：(1)利用Prim算法从顶点a构造最小生成树；3e1fdcbag97946218548图6-8加权无向图(2)用克鲁斯卡尔算法构造最小生成树的过程；解决方案：(1)图6-9示出了利用Prim算法从顶点a构造最小生成树的过程。aefdcbg初态aefd

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

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

10、的度数之和为(3)。d)。A.n B. eC .n eD。2e4.在有n个顶点的无向图中，边的数目是(4。c)。A.nB。(n-1)C. n(n-1)/2D。n(n 1)/25.在有n个顶点的有向完全图中，边的数目是(5。b)。A.n b . n(n-1)c . n(n-1)/2d . 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 . 18.如果一个图包含k个连通分量，如果你想根据深度优先搜索

11、方法访问所有顶点，你必须调用(8)的算法。a)深度优先搜索遍历。A.k b . 1 c . k-1d . k-19.要将N个顶点连接成一个连通图，至少需要(9。c)需要边缘。A.n B. n 1 C. n-1 D. 2n10.在具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素(也称为有效元素)的个数是(10)。d)。A.n . b . ne c . e . d . 2e11.在具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素数是(11)。c)。A.n . b . ne c . e . d . 2e12.在具有n个顶点和e条边的无向图的邻接表中，边节点的数目是(12。d)。A.n . b . ne c . e . d . 2e13.在具有n个顶点和e条边的有向图的邻接表中，单个顶点链表的头指针向量的大小至少为(13。a)。A.n . b . 2n c . e . d . 2e14.在未授权图的邻接表表示中，每个边节点至少包含(14。b)域。A.1 B. 2 C. 3 D. 415.对于有向图，如果顶点的度是k1，顶点的度是