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

admin2014-07-18 86

问题对于下图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://kaotiyun.com/show/P4xi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

二战爆发前夕，英法对法西斯侵略实行绥靖政策的原因、表现。

我国第一部系统的史学理论著作是()。

以下不属于国民党控制金融的“四行”的是()。

标志着南京国民政府在全国范围内形式上完成统一的事件是()。

一战后，凡尔赛条约规定了国际联盟管理15年的德国地区是()

建立中国道教史上第一个成熟的神仙系统的是()。

下列对第三次科技革命推动了国际经济格局调整的叙述，不正确的是()。

下列关于配备32位微处理器的计算机说法正确的是()。

药学职业道德不具有()

客户经常使用的银行卡分为信用卡和借记卡，其区别有()。

下列技术主要击出下旋球的是()。

有的人“聪明早慧”，而有的人则“大器晚成”，这说明人的身心发展具有

Happyhoursarenotnecessarilyhappy,nordotheylastforanhour,buttheyhavebecomeapartoftheritualoftheofficewor

计算其中D={(x，y)|x≥0，y≥0}．

设窗体文件中有下面的事件过程：PfivteSubCommand1_Click()Dimsa％=100PrintaEndSub其中变量a和s的数据类型分别是()。

Ifound,whilethinkingaboutthefar-reachingworldofthecreativeblackwoman,thatoftenthetruestanswertoaquestiontha

A、Doingpotentialharmtohumanbodies.B、Increasingmoistintheusers’eyes.C、Reducingtheworkinghourstothreehoursaday