对于下图G，按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示； (2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链

admin2012-06-26 66

问题对于下图G，按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
(1)假定它们均采用邻接矩阵表示；
(2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。

选项

答案(1)采用邻接矩阵表示得到的顶点序列如下表所示： [*] (2)采用邻接表表示得到的顶点序列如下表所示： [*]

解析导致对一个图进行遍历而得到的遍历序列不唯一的因素有许多。首先，遍历的出发顶点的选择不唯一，而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同，采用的遍历方法若不相同，得到的结果也是不相同的。另外，即使遍历的出发顶点相同，并且采用同一种遍历方法，若图的存储结构不相同，则得到的结果也可能是不相同的。例如，对于邻接表结构而言，建立邻接表时提供边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表结构会导致不同的遍历结果。
本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来，那么遍历序列就唯一确定下来。
本题需要先建立图G的邻接矩阵和按顶点序号从大到小的次序链接的邻接表，然后再进行深度优先和广度优先遍历。

转载请注明原文地址:https://kaotiyun.com/show/hfxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

罗马帝国分为东西两部的时间是()。

属于唐朝后期“南衙北司之争”的事件是()

规定了电流、电动势、电阻等概念的物理学家是()。

下列不是在北伐战争中发生的是()

简述蒙古西征的具体过程及其对中亚等地区的影响。(东北师范大学1999年世界中古史真题；南京大学2001年综合卷真题；东北师范大学2002年世界中古史真题)

波兰三次被瓜分的时间是()

对苏联高度集中的体制的客观评价是()。①基本上适应苏联当时的生产力发展水平②这种体制有严重缺点和弊端③后来这种体制阻碍了苏联国民经济的发展④这种体制在历史上起过积极的作用

最晚到汉武帝时期，出现了我国第一部算学著作()，它记载了用竿标测日影以求日高的方法，从而认识了勾股定理。

高度为4的4阶B树最多可容纳()个关键字(根是第1层)。

系统总线中地址线的功能是用于选择()。

互感电动势的大小正比于穿过本线圈磁通的变化率，或()另一线圈中电流的变化率。

患者，女，65岁，因腹胀、进行性腹部增大2周，并腹痛3天就诊。饮食和大小便无异常，既往无特殊病史。体检：腹隆起，软，下腹部压痛(+)，无反跳痛，移动性浊音(+)，肠鸣音正常。可能性最大的疾病和最佳检查方法应选择

控制项目目标的主要措施包括组织措施、管理措施、经济措施和技术措施，其中()是最重要的措施。

下列个人所得项目中，属于来源于中国境内所得的有()。

下列关于合同管理控制的说法中，错误的是()。

个案工作技巧中的建立关系是社会工作者与服务对象初次接触建立相互信任的()。

提出能力的两因素说的是()。

有多种方案可以在一台服务器中安装Windows和Linux两种网络操作系统，其中可以同时运行、Windows和Linux两种网络操作系统的方案是__________。(2013年上半年试题)

AccordingtoKellyGrant,giftforpurchaseisacceptableonlywhen