Question

已知图的邻接表如下所示,根据算法,则从顶点0出发按广度优先遍历的结点序列是

A．0 3 2 1 B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2

Answer 1

A。

首先，认识下广度优先遍历，相当于树的层序遍历，通常借助队列(先进先出)实现算法。题中从0出发，即0入队，邻接表访问顺序为3，2，1，则入队顺序也为3，2，1所以答案A。

例如：

深度：FCBDEA或者FCADEB

广度：FCABDE或者FCBADE

扩展资料 ：

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

（1）访问结点本身(N)，

（2）遍历该结点的左子树(L)，

（3）遍历该结点的右子树(R)。

以上三种操作有六种执行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。

参考资料来源；百度百科-遍历序列

Answer 2

答案是A
首先访问自己，也就是0，接着访问其邻接未访问顶点
由于邻接表的结点顺序为3、2、1，因为顺序依次访问这几个顶点

追问

bcd为啥不行？

追答

因为邻接表是链表啊，只能顺序访问，最上面那个v0的链后面不就是->3->2->1

Answer 3

首先，认识下广度优先遍历，相当于树的层序遍历，通常借助队列(先进先出)实现算法。
题中从0出发，即0入队，邻接表访问顺序为3.2.1，则入队顺序也为3.2.1
所以,答案A.