题5
题目
图的广度优先遍历算法中使用队列作为其辅助数据结构, 那么在算法执行过程中, 每个顶点的入队次数最多为 ( ) .
A. 1
B. 2
C. 3
D. 4
分析
BFS实际上是层序遍历，我觉得应该是只入队一次
解
A
在图的广度优先遍历算法中, 每个顶点被访问后立即做访问标记并入队。
若队列不空, 则队首顶点出队, 若该顶点的邻接顶点未被访问, 则访问之, 做访问标记并入队;
若被访问过, 则跳过, 如此反复, 直至队空。因此, 在广度优先遍历过程中, 每个顶点最多入队一次。