首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
admin
2013-07-12
32
问题
对于下图G,按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
(1)假定它们均采用邻接矩阵表示;
(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
选项
答案
(1)采用邻接矩阵表示得到的顶点序列如下表所示: [*] (2)采用邻接表表示得到的顶点序列如下表所示: [*]
解析
导致对一个图进行遍历而得到的遍历序列不唯一的因素有许多。首先,遍历的出发顶点的选择不唯一,而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同,采用的遍历方法若不相同,得到的结果也是不相同的。另外,即使遍历的出发顶点相同,并且采用同一种遍历方法,若图的存储结构不相同,则得到的结果也可能是不相同的。例如,对于邻接表结构而言,建立邻接表时提供边的信息的先后次序不同,边结点的链接次序也不同,从而会建立不同的邻接表;同一个图的不同邻接表结构会导致不同的遍历结果。
本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来,那么遍历序列就唯一确定下来。
本题需要先建立图G的邻接矩阵和按顶点序号从大到小的次序链接的邻接表,然后再进行深度优先和广度优先遍历。
转载请注明原文地址:https://kaotiyun.com/show/Drxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
在王安石变法诸措施中,旨在限制高利贷盘剥以缓和社会矛盾的是()。
“时方镇缺守帅,稍命文臣权之……又置转运使、通判,为之条禁,文薄渐为精密,由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。
日本在《二十一条》中提出:“中国沿海岛屿不得租于他国。”其真实目的是()。
简述西欧经济一体化的原因、进程和意义。
最晚到汉武帝时期,出现了我国第一部算学著作(),它记载了用竿标测日影以求日高的方法,从而认识了勾股定理。
关于“尊王攘夷”运动,不正确的说法是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争。这一古老文件是()
试析第三次科学技术革命对人类社会和历史进程的影响。
—棵二叉树的后序遍历序列为DABEC,中序遍历序列为DFBAC,则先序遍历序列为()。
随机试题
_______年在布鲁塞尔召开有37国代表出席的外交会议上,通过了修订《海牙—维斯比规则》的议定书()
招聘计划应包括()。
下列关于“法治”与“法制”区别的表述,错误的是()。
《资治通鉴》是中国第一部编年体通史。()
求∫0x2(x—t)dt.
(7)不属于将入侵检测系统部署在DMZ中的优点。
From:ACAEventsTo:GregUnderwoodSubject:RegistrationfortheACABusinessManagementSeminarDearMr.Underwood,Youhav
Vibrationsinthegroundareapoorlyunderstoodbutprobablywidespreadmeansofcommunicationbetweenanimals.Itseemsun
Hewasfacingchargesonforgeryinacourtoflawbuthehiredagoodlawyerto_____.
ThepennameMarkTwaincamefrom_____
最新回复
(
0
)