给定一个有向图,使用邻接表表示如下:0: ->1->2, 1: ->3->4, 2: ->5, 3:->6,4:->∅, 5:->∅, 6:->∅。从顶点0出发,使用广度优先搜索(BFS)遍历该图,以下哪一个序列是可能的遍历顺序?

答案解析

核心考点说明:本题考察使用邻接表表示的图的广度优先搜索(BFS)的遍历过程。解题思路分析:广度优先搜索(BFS)是一种逐层遍历的方式,首先访问起始节点,然后访问其所有邻居节点,然后访问这些邻居的邻居节点,以此类推。每个选项的详细分析:A选项错误。根据邻接表,应该先访问0的邻居1和2,再访问1的邻居3和4,再访问2的邻居5,再访问3的邻居6,因此,这个顺序不符合BFS。B选项正确。从0开始,先访问1和2,然后访问1的邻居3和4,然后访问2的邻居5,最后访问3的邻居6,此顺序符合BFS。C选项错误。应该先访问顶点1,再访问顶点2,而非反之。D选项错误。顶点2的邻居5应该在顶点3的邻居6之前访问。易错点提醒:注意BFS是逐层遍历,要先访问完一层的所有节点,再进入下一层。
正确答案:B
随机推荐
开始刷题