深度优先搜索 高频追问 Q&A

深度优先搜索 高频追问 Q&A

1. Q: DFS 和 BFS 本质区别？

A: DFS 深入后回溯，BFS 按层扩展。（深入阅读：深度优先搜索基础知识速览、广度优先搜索基础知识速览）

2. Q: DFS 为什么容易爆栈？

A: 递归深度过深。可改显式栈迭代实现。（深入阅读：深度优先搜索基础知识速览）

3. Q: 图 DFS 为什么必须 visited？

A: 防止回路导致重复遍历甚至死循环。（深入阅读：图的连通性与 DFS 遍历）

4. Q: 回溯和 DFS 什么关系？

A: 回溯是带“撤销选择”的 DFS。（深入阅读：回溯搜索：排列组合子集、回溯基础知识速览）

5. Q: 什么时候用递归，什么时候用迭代？

A: 规模小/结构清晰可递归；深度大或线上稳定性优先迭代。（深入阅读：深度优先搜索基础知识速览、树的递归与迭代遍历）

6. Q: 复杂度怎么估？

A: 图遍历通常 O(V+E)，回溯按搜索树分支数与深度估计。（深入阅读：深度优先搜索基础知识速览、复杂度分析方法与陷阱）