2. 计算机
  3. 以下关于图的遍历的叙述中，正确的是( )。

以下关于图的遍历的叙述中，正确的是( )。

admin2019-04-22  36
问题 以下关于图的遍历的叙述中，正确的是(    )。
选项 A、图的遍历是从给定的源点出发对每一个顶点仅访问一次的过程
B、图的深度优先遍历方法不适用于无向图
C、使用队列对图进行广度优先遍历
D、图中有回路时则无法进行遍历
答案C
解析 本题考查数据结构基础知识。
图的遍历是指对图中所有顶点进行访问且只访问一次的过程。因为图的任一个结点都可能与其余顶点相邻接，所以在访问了某个顶点之后，可能沿着某路径又回到该结点上。因此为了避免顶点的重复访问，在图的遍历过程中，必须对已访问过的顶点进行标记。深度优先遍历和广度优先遍历是两种遍历图的基本方法。
    图的广度优先遍历方法为：从图中某个顶点1，出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点"被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时还有未被访问的顶点，则另选图中的一个未被访问的顶点作为起点，重复上述过程，直至图中所有的顶点都被访问到为止。
  广度优先遍历图的特点是尽可能先进行横向搜索，即最先访问的顶点的邻接点也先被访问。为此，引入队列来保存已访问过的顶点序列，即每当一个顶点被访问后，就将其放入队中，当队头顶点出队时，就访问其未被访问的邻接点并令这些邻接顶点入队。
转载请注明原文地址:https://kaotiyun.com/show/1YRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

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