首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
admin
2014-07-18
66
问题
对于下图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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
凯末尔主义中不属于民主主义内容的是()。
在《资政新篇》中,洪仁轩提出的政治主张实际是要()。
被马克思称颂为“古代无产阶级的真正代表”的是()。
1965年美国总统经济报告中宣布:“一个不受衰退威胁的繁荣时期,使我们能够防止经济活动下降的时期到来了,我们相信衰退是不可避免的……国家的措施基本上不能够在衰退开始之前予以防止。”下列能够证明报告观点错误的是()
斯蒂文逊负责勘测和修建的世界上的第一条公共交通铁路通车于()。
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
苏俄实施新经济政策的根本目的是()。
近现代以来,国际关系中先后出现了维也纳体系、凡尔赛一华盛顿体系和雅尔塔体系。关于这三个体系共同点的表述不正确的是()。
下列选项中,()不是福建人民革命政府的政治、经济主张所代表的受益阶级。
在微程序控制方式中,以下说法中正确的是()。Ⅰ.采用微程序控制器的处理器称为微处理器Ⅱ.每一条机器指令由一个微程序来解释执行Ⅲ.在微指令的编码中,执行效率最低的是直接编码方式Ⅳ.水平型微指令能充分利用数据通路的并行结构
随机试题
利用电力来分离非均相物系可以彻底将非均相物系分离干净。()
肝癌术前护理,错误的是
【背景资料】某公司承建一火电厂油站扩建工程,是该厂的法定重点防火单位,为此在施工组织设计中对防火措施方案进行了详尽策划,经批准后实施。施工室外管网需要停水和接通,都办理了相应手续。该工程从开工至结束,虽然动火作业繁多,未发生任何火警事件,受当地公安消防监
根据企业所得税法律制度的规定,下列关于收入确认的表述中,正确的有()。(2011年)
在通过编制“银行存款余额调节表”调节未达账项后,如果银行存款日记账与银行对账单余额相等,说明双方记账没有错误。()
以下能正确定义一维数组的选项是
Childrenlivingwithsingleparentsencountermanyproblems.Theyaremore【C1】______stressfulexperiencesthanarechildrenlivi
TheBritishEmpirewasoncehometothirdofthe【M1】______world’spopulation.But,withthereturnofHon
Therelationshipbetween"right"and"write"is
Thefinalexaminationiscomingupsoon.It’stimeforusto_______ourstudies.
最新回复
(
0
)