一个无向图的邻接矩阵如下,其中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