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

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

admin2013-07-12  54
问题 对于下图G，按下列条件试分别写出从顶点O出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
(1)假定它们均采用邻接矩阵表示；
(2)假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
选项
答案(1)采用邻接矩阵表示得到的顶点序列如下表所示： [*] (2)采用邻接表表示得到的顶点序列如下表所示： [*]
解析 导致对一个图进行遍历而得到的遍历序列不唯一的因素有许多。首先，遍历的出发顶点的选择不唯一，而得到的遍历序列显然也不是唯一的。即使遍历的出发顶点相同，采用的遍历方法若不相同，得到的结果也是不相同的。另外，即使遍历的出发顶点相同，并且采用同一种遍历方法，若图的存储结构不相同，则得到的结果也可能是不相同的。例如，对于邻接表结构而言，建立邻接表时提供边的信息的先后次序不同，边结点的链接次序也不同，从而会建立不同的邻接表；同一个图的不同邻接表结构会导致不同的遍历结果。
本题中导致对一个图进行遍历而得到的遍历序列不唯一的因素都确定下来，那么遍历序列就唯一确定下来。
本题需要先建立图G的邻接矩阵和按顶点序号从大到小的次序链接的邻接表，然后再进行深度优先和广度优先遍历。
转载请注明原文地址:https://www.kaotiyun.com/show/Drxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)