一个无向图的邻接矩阵如下,其中1表示存在边,0表示不存在边。该图的顶点编号为1到5。 1 2 3 4 5 1 [0 1 1 0 0] 2 [1 0 1 1 0] 3 [1 1 0 1 1] 4 [0 1 1 0 1] 5 [0 0 1 1 0] 若从顶点3开始进行广度优先搜索(BFS),以下哪个顶点序列是正确的访问顺序?

答案解析

核心考点说明:本题考察图的广度优先搜索(BFS)算法,重点是理解BFS的访问顺序,即按层访问。 解题思路分析:广度优先搜索从一个起始顶点开始,首先访问该顶点,然后访问其所有未被访问过的邻居顶点,再按顺序访问这些邻居顶点的邻居顶点,直到所有可达顶点都被访问。使用队列来实现。 从顶点3开始,初始队列为|3| 1. 出队3,访问3,访问3的邻居1,2,4,5,入队1,2,4,5,队列变为|1|2|4|5| 2. 出队1,访问1,1的邻居中2,3已被访问,入队0,队列变为|2|4|5| 3. 出队2,访问2,2的邻居中1,3,4已被访问,队列变为|4|5| 4. 出队4,访问4,4的邻居中2,3,5已被访问,队列变为|5| 5. 出队5,访问5,5的邻居中3,4已被访问,队列变为空。 因此,访问顺序为:3, 1, 2, 4, 5。 每个选项的详细分析: - A. 选项A:3, 1, 2, 4, 5 符合广度优先搜索的访问顺序。故A正确 - B. 选项B:3, 1, 2, 5, 4 访问顺序错误,BFS应先访问完所有邻居再往下层,而不是随意访问。故B错误 - C. 选项C:3, 1, 4, 2, 5 访问顺序错误,不符合BFS的访问规则。故C错误 - D. 选项D:3, 1, 2, 4 遗漏了顶点5,不符合BFS。故D错误 易错点提醒:容易将广度优先搜索和深度优先搜索混淆,需要理解BFS按层遍历的特点。此外,要注意入队时未访问的邻居,避免重复访问。
正确答案:A
随机推荐
开始刷题