数据结构教程李春葆课后答案第8章图.pdf

《数据结构教程李春葆课后答案第8章图.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第8章图教材中练习题及参考答案1.图G是一个非连通图，共有28条边，则该图至少有多少个顶点？答：由于G是一个非连通图，在边数固定时，顶点数最少的情况是该图由两个连通分量构成，且其中之一只含一个顶点（没有边），另一个为完全无向图。设该完全无向图的顶点数为n，其边数为n(n-1)/2，即n(n-1)/2=28，得n=8。所以，这样的非连通图至少有1+8=9个顶点。2.有一个如图8.2（a）所示的有向图，给出其所有的强连通分量。答：图中顶点0、1、2构成一个环，这个环一定是某个强连通分量的一部分。再考察顶点3、4，它们到这个环中的顶点都有双向路径，所以将

2、顶点3、4加入。考察顶点5、6，它们各自构成一个强连通分量。该有向图的强连通分量有3个，如图8.2（b）所示。00124512456363(a)一个有向图(b)3个强连通分量图8.2一个有向图及其强连通分量3.对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？答：邻接矩阵适合于稠密图，因为邻接矩阵占用的存储空间与边数无关。邻接表适合于稀疏图，因为邻接表占用的存储空间与边数有关。4.对n个顶点的无向图和有向图（均为不带权图），采用邻接矩阵和邻接表表示时，如何求解以下问题：（1）图中有多少条边？（2）任意两个顶点i和j是否有边相连？（3）任意一个顶点

3、的度是多少？答：（1）对于邻接矩阵表示的无向图，图的边数等于邻接矩阵数组中为1的元素个数除以2；对于邻接表表示的无向图，图中的边数等于边结点的个数除以2。对于邻接矩阵表示的有向图，图中的边数等于邻接矩阵数组中为1的元素个数；对于邻2数据结构教程学习指导接表表示的有向图，图中的边数等于边结点的个数。（2）对于邻接矩阵g表示的无向图，邻接矩阵数组元素g.edges[i][j]为1表示它们有边相连，否则为无边相连。对于邻接矩阵g表示的有向图，邻接矩阵数组元素g.edges[i][j]为1表示从顶点i到顶点j有边，g.edges[j][i]为1表示从顶点j

4、到顶点i有边。对于邻接表G表示的无向图，若从头结点G->adjlist[i]的单链表中找到编号为j的边表结点，表示它们有边相连；否则为无边相连。对于邻接表G表示的有向图，若从头结点G->adjlist[i]的单链表中找到编号为j的边表结点，表示从顶点i到顶点j有边。若从头结点G->adjlist[j]的单链表中找到编号为i的边表结点，表示从顶点j到顶点i有边。（3）对于邻接矩阵表示的无向图，顶点i的度等于第i行中元素为1的个数；对于邻接矩阵表示的有向图，顶点i的出度等于第i行中元素为1的个数，入度等于第i列中元素为1的个数，顶点i度等于它们之和。对

5、于邻接表G表示的无向图，顶点i的度等于G->adjlist[i]为头结点的单链表中边表结点个数。对于邻接表G表示的有向图，顶点i的出度等于G->adjlist[i]为头结点的单链表中边表结点的个数；入度需要遍历所有的边结点，若G->adjlist[j]为头结点的单链表中存在编号为i的边结点，则顶点i的入度增1，顶点i的度等于入度和出度之和。5.对于如图8.3所示的一个无向图G，给出以顶点0作为初始点的所有的深度优先遍历序列和广度优先遍历序列。012345图8.3一个无向图G答：无向图G的所有的深度优先遍历序列如下：01452301542301453

6、2015432021453021543023145023154031452031542032145032154无向图G所有的广度优先遍历序列如下：012345第8章图30123540132450132540213450213540231450231540312450312540321450321546.对于如图8.4所示的带权无向图，给出利用Prim算法（从顶点0开始构造）和Kruskal算法构造出的最小生成树的结果，要求结果按构造边的顺序列出。答：利用普里姆算法从顶点0出发构造的最小生成树为：{(0，1)，(0，3)，(1，2)，(2，5)，(5

7、，4)}。利用克鲁斯卡尔算法构造出的最小生成树为：{(0，1)，(0，3)，(1，2)，(5，4)，(2，5)}。17134502645238图8.4一个带权无向图7.对于一个顶点个数大于4的带权无向图，回答以下问题：（1）该图的最小生成树一定是唯一的吗？如何所有边的权都不相同，那么其最小生成树一定是唯一的吗？（2）如果该图的最小生成树不是唯一的，那么调用Prim算法和Kruskal算法构造出的最小生成树一定相同吗？（3）如果图中有且仅有两条权最小的边，它们一定出现在该图的所有的最小生成树中吗？简要说明回答的理由。（4）如果图中有且仅有3条权最小的

8、边，它们一定出现在该图的所有的最小生成树中吗？简要说明回答的理由。答：（1）该图的最小生成树不一定是唯一的。如何所有边的权