首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
admin
2014-07-18
37
问题
对于下图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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
建设有中国特色的社会主义理论主要包括哪些内容?
系统阐明社会主义初级阶段理论是在()。
清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏
科举是一种读书、应考、任官三位一体的选官方法,其中的进士科始创于()。
以北宋三大发明为例简述北宋科学技术的特征。
简述第二国际建立的社会历史条件。
《道威斯计划》的实施所产生的直接结果是()。
明朝灭亡后,以下南明小朝廷存在的先后顺序是()。①绍武政权②永历政权③隆武政权④弘光政权
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
支持多道程序的操作系统,区别于其他操作系统的主要特征为()。
随机试题
Graves病时的代谢,下列哪项不正确
减压干燥法测定水分适合于
项目信息管理的目的是通过对项目信息传输的有效组织和控制,为项目的()提供服务。
下列哪种方法不利于缓解或调控幼儿激动的情绪?()
函的重要功能之一是()。
哪一因素与收益曲线(利率)平直无相关?()
2013年6月,习近平就坚定不移走两岸关系和平发展道路发表的重要意见中强调,从中华民族整体利益把握两岸关系大局,最根本的、最核心的是()
[*]
Therearemanymedicalproblemsinthemodernsociety.Oneofthemostalarmingmedicalproblemsintheworldisa【C1】diseasena
Childrenwhosemindswandermighthavesharperbrains,researchsuggests.Astudyhasfoundthatpeoplewhoappeartobecon
最新回复
(
0
)