能用非递归DFS就别用递归，因其可避免Python递归深度限制（默认约1000）、防止栈溢出、提升深层嵌套结构处理鲁棒性；核心是用list模拟栈，pop()取节点、访问前检查visited、再压入未访问邻居。
标题里有个明显混淆：BFS 是广度优先搜索，不是深度优先。你真正想问的，很可能是：
如何用非递归方式实现深度优先搜索（DFS），来避免 Python 递归栈溢出、提升对深层嵌套结构的处理鲁棒性？
结论很直接：能不用递归 DFS 就别用，尤其当数据深度不可控（如解析嵌套 JSON、AST、DOM、多层继承链、图中长链路径）时，非递归 DFS 是更安全的选择。
为什么递归 DFS 在 Python 中容易崩
Python 默认递归限制是 sys.getrecursionlimit()（通常 1000），超过就抛 RecursionError。这不是算法问题，是语言限制。
- 深度为 1001 的树/链表 → 直接崩溃
- 无法通过
sys.setrecursionlimit()安全地大幅提高（可能触发 C 栈溢出或内存耗尽） - 递归调用开销大：每次调用要压栈帧、保存局部变量、返回地址
所以，只要结构深度 > 几百，就该切到非递归版本。
非递归 DFS 的核心：用 list 当栈，手动管理“下一步”
关键不是“去掉递归”，而是把隐式调用栈显式化。Python 的 list 做栈足够快（.append() 和 .pop() 均摊 O(1)）。
常见写法有两类，区别在「访问时机」和「是否重复入栈」：
先压后访（推荐）：节点入栈时不立即处理，出栈时再访问
→ 更贴近递归逻辑，天然支持回溯标记（如路径还原）边压边访：一拿到节点就处理，再把子节点压栈
→ 代码短，但若需记录状态（如父节点、深度），得额外存元组
示例（邻接表图的非递归 DFS）：
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop() # LIFO：取最后进的
if node in visited:
continue
visited.add(node)
print(node) # 访问动作
for neighbor in graph.get(node, []):
if neighbor not in visited:
stack.append(neighbor)
注意：stack.append(neighbor) 顺序影响遍历次序（比如想按字母序访问，得先倒序 append）。
非递归 BFS 和 DFS 别混用，它们数据结构和语义完全不同
这是最常踩的坑：看到“非递归”，下意识套用队列（collections.deque），结果写出了 BFS —— 但你要的是 DFS。
| 特征 | 非递归 DFS | 非递归 BFS |
|---|---|---|
| 核心容器 |
list 或 deque（用 .pop()） |
deque（必须用 .popleft()） |
| 访问顺序 | 深度优先（一条路走到黑） | 广度优先（一圈一圈往外扩） |
| 时间复杂度 | O(V + E) | O(V + E) |
| 空间复杂度 | O(h)，h 是最大深度（栈高） | O(w)，w 是最大层宽（队列长） |
错误示范（误把 DFS 写成 BFS）：
# ❌ 这是 BFS，不是 DFS
from collections import deque
q = deque([start])
while q:
node = q.popleft() # ← 关键：popleft ≠ pop！
...
正确 DFS 必须是 .pop()（或 .pop(-1)），哪怕你用 deque。
处理真实嵌套结构时，栈里得存更多上下文
纯节点名不够用。比如遍历嵌套字典并记录路径，或解析 AST 时需要知道当前深度、父节点、是否已处理子节点。
这时栈元素应为元组或字典：
# 示例：带路径的嵌套 dict 深度优先遍历
def dfs_dict_with_path(data, path=""):
stack = [(data, path)]
while stack:
obj, curr_path = stack.pop()
if isinstance(obj, dict) and obj:
for k, v in obj.items():
new_path = f"{curr_path}.{k}" if curr_path else k
stack.append((v, new_path))
else:
print(f"Leaf at {curr_path}: {obj}")
这种模式比递归更灵活：你可以随时中断、跳过分支、动态修改栈内容，而递归一旦进函数就只能靠 return 控制。
非递归 DFS 的难点不在写法，而在思维切换：你要主动维护状态，而不是依赖函数调用自然堆叠。最容易被忽略的是「重复访问检查的时机」——必须在 pop() 后、处理前做 if node not in visited，否则同一节点可能被多次压栈、多次处理。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
