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

admin2014-07-18 48

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

选项

答案对一个图进行遍历而得到的遍历序列不唯一的因素有许多：首先，遍历的出发顶点的选择不唯一，而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同，采用的遍历方法若不相同，得到的结果也是不相同的。其次，即使遍历的出发顶点相同，并且采用同一种遍历方法，若图的存储结构不相同，则得到的结果也可能是不相同的。例如，对于邻接表结构而言，建立邻接表时提供边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表结构会导致不同的遍历结果。本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来，那么遍历序列就唯一确定下来。 (1)采用邻接矩阵表示得到的顶点序列，邻接矩阵如下所示： [*] ①采用邻接矩阵进行深度优先遍历，在一个结点连接多个结点时，优先选择序号较小的结点；然后按深度优先遍历算法完成遍历。 ②在本题给出的图G中，深度优先遍历的顺序为：0→1→2→8→3→4→5→6→7→9。采用邻接矩阵进行广度优先遍历，在一个节点连接多个结点时，优先选择序号较小的结点；然后按广度优先遍历算法完成遍历。在本题给出的图G中，深度优先遍历的顺序为：0→1→4→2→7→3→8→6→5→9。 (2)采用邻接表表示得到的顶点如下所示： [*] ①采用邻接表进行深度优先遍历，在一个结点连接多个结点时，优先选择序号较大的结点；然后按深度优先遍历算法完成遍历。在本题给出的图G中，深度优先遍历的顺序为：0→4→3→8→9→5→6→7→1→2。 ②采用邻接表进行广度优先遍历，在一个结点连接多个结点时，优先选择序号较大的结点；然后按广度优先遍历算法完成遍历。在本题给出的图G中，深度优先遍历的顺序为：O→4→1→3→7→2→8→6→9→5。

解析

转载请注明原文地址:https://jikaoti.com/ti/BRajFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

第一国际开展了哪些活动?其内部经历了哪些主要斗争?

下列关于胡司战争的叙述错误的一项是()。

下列不属于苏联高度集中的经济政治体制产生的条件的是()。

下列选项中，不是由晁错提出的是()

下列事件中，不是发生在上海的是()

洪秀全以宗教手段组织起义，主要利用的是()。

西南军阀跟随孙中山拥护护法运动的目的是()。

最早测量子午线的长度，并主持修订了当时最先进历法《大衍历》的是僧人()。

魏晋南北朝的手工业技术有所进步，下列各项能反映这一特点的是()。①培育出“三熟之稻”②“灌钢”技术的发明③吴培育出八辈之蚕④纸成为最主要的书写材料

支持多道程序的操作系统，区别于其他操作系统的主要特征为()。

简述教师应如何提高学生的知识概括水平。

SLE累及器官发生率最高者为

IPV6采用的IP地址为()位地址。

中国工程咨询协会是由从事工程咨询及其相关业务的单位、咨询工程师以及在工程技术经济领域富有咨询和()的专家、学者自愿组成的非营利性社会组织，是具有法人资格的全国性社会团体，是代表中国工程咨询业的行业协会。

某船运公司2016年拥有机动船4艘，每艘净吨位为3000吨；拖船1艘，发动机功率为1500千瓦。机动船舶车船税年基准税额为：净吨位201吨至2000吨的，每吨4元；净吨位2001吨至10000吨的，每吨5元，该船运公司2016年应缴纳车船税()元

分布距离大约在1000公里可能属于()。

课程目标是教学目标的载体和具体化。()

计算dxdy，其中D为单位圆x2＋y2＝1所围成的位于第一象限的部分．

Clothesplayacriticalpartintheconclusionswereachbyprovidingcluestowhopeopleare,whotheyarenot,andwhotheywo

Comedy’slegendaryMontyPythonmembers—youknow,"I’malumberjack(伐木工人)andI’mOK,"theKillerRabbit,theDeadParrot—wereti