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

admin2012-06-26 112

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

选项

答案(1)采用邻接矩阵表示得到的顶点序列如下表所示： [*] (2)采用邻接表表示得到的顶点序列如下表所示： [*]

解析导致对一个图进行遍历而得到的遍历序列不唯一的因素有许多。首先，遍历的出发顶点的选择不唯一，而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同，采用的遍历方法若不相同，得到的结果也是不相同的。另外，即使遍历的出发顶点相同，并且采用同一种遍历方法，若图的存储结构不相同，则得到的结果也可能是不相同的。例如，对于邻接表结构而言，建立邻接表时提供边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表结构会导致不同的遍历结果。
本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来，那么遍历序列就唯一确定下来。
本题需要先建立图G的邻接矩阵和按顶点序号从大到小的次序链接的邻接表，然后再进行深度优先和广度优先遍历。

转载请注明原文地址:https://kaotiyun.com/show/hfxi777K

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

共产国际“七大”号召建立的反法西斯统一战线中不包括()

西汉诸侯国的政权机构和中央基本上相同，其中需要中央直接任命的有()

导致俄国革命去和平发展可能的事件是()。

随着对外开放的进一步扩大，中共中央和国务院在1988年决定建立的经济特区是()。

德国法西斯能够通过合法方式夺取政权，主要原因有()。①垄断资产阶级要求建立极权统治②纳粹党利用了人民对现状的不满③骗人的宣传欺骗了社会的信任④通过国会纵火案打击了共产党

马克思第一次明确论述无产阶级历史使命和无产阶级必须与科学理论相结合思想的著作是()。

魏晋南北朝时期道家得到了迅速发展，援儒入道，在道教官方化过程中有重大贡献的北朝人物是()。

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

()的设置是清王朝实行满汉联合、以汉制汉统治方式在军事上的具体体现

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

乳房自我检查时，观察乳房应采取的站立姿势有【】

销售人员对消费者的心理影响主要表现在()。

一个全空气一次回风空调系统，服务四个空调房间，按最小新风量计算方法计算后得出四个房间的最小新风比分别为12%、16%、18%、20%，则设计该空调系统时最小新风比应取()。

信用证的到期日为12月31日，最迟装运期为12月16日，最迟交单日期为运输单据出单后15天，出口人备妥货物安排出运的时间是12月10日，则出口人最迟应于()向银行交单议付。

设函数f(x)在[0,3]上连续,在(0,3)内可导,且f(0)+f(1)+f(2)=3,f(3)=1.试证必存在ξ∈(0,3).使f’(ξ)=0.

要在Access数据库中建立“学生成绩表”，包括字段(学号，平时成绩，期末成绩，总成绩)，其中平时成绩为0～20分，期末成绩和总成绩均为0～100分，总成绩为平时成绩+期末成绩×80％。则在创建表时，错误的操作是

Thephrase"theworld"inthefirstlineofthepassagereferstoWhichofthefollowingstatements,accordingtothepassage,

Hedoesn’tfeellike______apicnicintheparkthisweekend,andhesuggestedwatchingthefootballmatchinstead.