首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 (1)假定它们均采用邻接矩阵表示; (2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
admin
2012-06-26
108
问题
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
(1)假定它们均采用邻接矩阵表示;
(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
选项
答案
(1)采用邻接矩阵表示得到的顶点序列如下表所示: [*] (2)采用邻接表表示得到的顶点序列如下表所示: [*]
解析
导致对一个图进行遍历而得到的遍历序列不唯一的因素有许多。首先,遍历的出发顶点的选择不唯一,而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同,采用的遍历方法若不相同,得到的结果也是不相同的。另外,即使遍历的出发顶点相同,并且采用同一种遍历方法,若图的存储结构不相同,则得到的结果也可能是不相同的。例如,对于邻接表结构而言,建立邻接表时提供边的信息的先后次序不同,边结点的链接次序也不同,从而会建立不同的邻接表;同一个图的不同邻接表结构会导致不同的遍历结果。
本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来,那么遍历序列就唯一确定下来。
本题需要先建立图G的邻接矩阵和按顶点序号从大到小的次序链接的邻接表,然后再进行深度优先和广度优先遍历。
转载请注明原文地址:https://kaotiyun.com/show/hfxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
“如今有个趋势,人们怀念她的民主制度,并将其视为所有现代民主制度的源头。”(英国历史学家约翰.索利语)这里的“她”是指()
我国古代文献中记载了许多有关部落和部落联盟之问发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
论述彼得一世改革的背景、措施及影响
论述西晋占田制的实行及其意义。(兰州大学2001年中国古代史真题;北京师范大学2004年历史学综合真题)
略论中国近现代历史上的“军阀”问题。(北京大学2003年中国通史真题)
下面条约没有涉及德国的赔款问题的是()。
在阿拉伯()统治时期,阿拉伯军队曾与当时中国的唐朝军队发生冲突。
下列选项中,不是由晁错提出的是()
某图像显示器的分辨率为1024×768,共可显示256种灰度,则显示存储器的容量为()。
随机试题
下列关于注册会计师利用内部审计人员提供直接协助的表述中,正确的是()。
胃癌最常见的发生部位是
霍奇金病患者,横膈上下均有淋巴结肿大,脏器和骨髓均无侵犯,无临床症状,治疗方法首先选择是
关于宪法的表述,下列说法不正确的是:
阅读材料,并回答问题。思想品德课学习形成性评价用表问题:结合上表,说明思想品德课开展形成性评价的意义。
齐白石的中国画《蛙声十里出山泉》描写的是()。
在教学《谁是最可爱的人》时,老师问:“谁是最可爱的人呢?”一个学生站起来说:“老师,我是不是最可爱的人呢?”老师说:“你热爱劳动,乐于助人,你是可爱的人。如果你能按时完成作业,认真听讲,上课积极发言,那么你也是最可爱的人。”该教师运用了哪些德育原则(
蝴蝶效应原本是一个气象学名词,说的是南美的蝴蝶扇动一下翅膀,最终将会在北美引起一场龙卷风。听起来这事似乎有些荒唐,但实际情况就是这样。一件微乎其微的细节,却可能造成一个谁都意想不到的结果。聪明的人,就应该从蝴蝶效应中及时看出日后的风暴。可以印证这段话论点
生物电是指生物的器官、组织和细胞在生命活动过程中发生的电位和极性变化。它是生命活动过程中的一类物理、物理一化学变化,是正常生理活动的表现,也是生物活组织的一个基本特征。根据上述定义,下列不属于生物电的一项是:
A、Toteachthemhowtoliveandstudyinapublicschool.B、Topreparethemtobefamousanddistinguishedpeople.C、Totrainth
最新回复
(
0
)