算法选择题：图遍历与搜索（5 题）
046 BFS 遍历图时，visited 标记应该在什么时候进行？
难度： 基础
- A. 必须在出队时标记，否则结果不正确
- B. 通常在节点入队时立即标记；出队时才标记可能让同一节点重复入队，增加复杂度
- C. 只要最终所有节点都被标记，何时标记都不影响开销
- D. visited 只用于有环图，无环图不需要标记
查看答案与解析
正确答案B
正确原因： BFS 通常在节点入队时立即标记访问；出队时才标记可能让同一节点重复进入队列。
错误选项辨析： A 项：入队时标记同样正确，且是避免重复入队的常规做法；C 项：出队时标记会让同一节点多次入队，队列膨胀影响复杂度；D 项：无环图也可能通过不同路径再次到达同一节点，仍需标记。
047 在无权图中求最短路径，为什么选择 BFS 而不是 DFS？
难度： 进阶
- A. 只要图是无向的，任意遍历都能得到最短路径
- B. DFS 第一次到达目标也保证路径最短
- C. BFS 按边数分层，第一次到达节点即得到无权最短距离；存在不同边权时需要 Dijkstra 等算法
- D. DFS 与 BFS 在无权图中得到的结果完全相同
查看答案与解析
正确答案C
正确原因： BFS 按边数分层，第一次到达节点即得到无权最短距离；存在不同边权时需要 Dijkstra 等算法。
错误选项辨析： A 项：最短路径与遍历方式无关是错误前提，BFS 按层扩展才是关键；B 项：DFS 不按层扩展，第一次到达的路径不一定最短；D 项：DFS 可能先走一条长路径，无法保证最短。
048 在深图（长链）上使用递归 DFS 的主要风险是什么？
难度： 进阶
- A. 递归 DFS 比迭代 DFS 更省空间，因为不分配栈
- B. 递归 DFS 不需要额外空间，深图也没有风险
- C. 深图只能用 BFS，DFS 无论如何都会超时
- D. 调用栈深度可达顶点数量，可能栈溢出；深图或长链应考虑使用显式栈迭代实现
查看答案与解析
正确答案D
正确原因： 递归 DFS 的调用栈深度可达到顶点数量；深图或长链应考虑显式栈。
错误选项辨析： A 项：递归隐式使用调用栈，空间并不比显式栈少；B 项：递归调用栈随深度增长，深图可能栈溢出；C 项：DFS 用显式栈同样可以处理深图，超时不是必然。
049 对邻接表表示的图完整遍历一次，时间复杂度是多少？
难度： 进阶
- A. 每个顶点与每条边各访问常数次，复杂度为 O(V+E)；无向图每条边存储两次但数量级不变
- B. 邻接表遍历是 O(E)，与顶点数无关
- C. 图遍历一律是 O(V²)
- D. 无向图每条边存两次，因此复杂度是 O(E²)
查看答案与解析
正确答案A
正确原因： 邻接表完整遍历会访问每个顶点和每条边常数次；无向图通常把每条边存储两次但数量级不变。
错误选项辨析： B 项：每个顶点都要访问一次，复杂度与 V 也相关；C 项：邻接表下每条边只遍历常数次，复杂度是 O(V+E) 而非 O(V²)；D 项：存储两次只是常数倍，O(2E) 仍是 O(E)，不是 O(E²)。
050 用 Kahn 算法做拓扑排序时，如何判断图中存在环？
难度： 进阶
- A. 出现入度为 0 的顶点就说明图一定有环
- B. Kahn 算法处理的顶点数少于总数时图中存在环；拓扑顺序只适用于有向无环图
- C. Kahn 算法总能输出完整拓扑序列，与环无关
- D. 任意有向图都至少存在一种拓扑顺序
查看答案与解析
正确答案B
正确原因： Kahn 算法处理的顶点数少于总数时图中存在环；拓扑顺序只适用于有向无环图。
错误选项辨析： A 项：入度为 0 的顶点可以正常入队，与是否存在环无直接关系；C 项：存在环时剩余顶点入度无法降为零，序列不完整；D 项：含环的有向图不存在拓扑顺序。