递归dfs直观但易栈溢出，适合小图；迭代dfs用栈更可控，需逆序压栈保证顺序；邻接表优于邻接矩阵；dfs不自动遍历全图，需外层循环处理多连通分量。
DFS递归写法最直观，但要注意栈溢出风险
Python默认递归深度只有1000层，图节点多或深度大时，RecursionError: maximum recursion depth exceeded几乎必现。这不是代码写错了，是语言限制。
递归DFS适合小图、教学演示或已知结构浅的场景（比如二叉树）。核心就是「访问当前节点 → 遍历未访问邻居 → 递归处理每个邻居」。
- 用
visited集合记录已访问节点，避免环导致死循环 - 邻接表用
dict或list都行，但查邻居必须O(1)，别在循环里反复.index() - 如果需要路径回溯（比如找两点间路径），递归参数要带
path列表，但注意别直接传path.append(x)——那会改原列表，得传path + [x]
def dfs_recursive(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start) # 或存入结果
for neighbor in graph.get(start, []):
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited用栈模拟DFS更可控，适合真实项目
显式用list当栈（append/pop()）能完全避开递归限制，逻辑也更贴近算法本质：后进先出，优先深入最新发现的分支。
关键不是“能不能写”，而是「顺序是否符合预期」——Python的list.pop()弹尾，所以压栈顺序得反着来，否则遍历顺序和递归版不一致（比如想按字母序访问邻居，就得先压'z'再压'a'）。
立即学习“Python免费学习笔记（深入）”；
- 栈里存的是待处理节点，不是边或状态；每次
pop()一个，立刻标记visited - 不要在
for循环里动态修改正在遍历的graph[start]，容易漏节点 - 如果图用
defaultdict(list)，记得处理graph[node]可能为空的情况，避免KeyError
def dfs_iterative(graph, start):
stack, visited = [start], set()
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
# 注意：逆序压栈才能保持和递归相同的访问顺序
for neighbor in reversed(graph.get(node, [])):
if neighbor not in visited:
stack.append(neighbor)
return visited邻接矩阵下DFS性能差，别硬套
用list of list存图时，查一个节点的所有邻居要O(V)扫整行，而邻接表是O(degree)。V=1000时，单次遍历邻居就多999次无效判断。
除非图非常稠密（边数接近V²）且内存极宽裕，否则别用矩阵存图再跑DFS。更糟的是，很多人写成for j in range(len(matrix)):然后if matrix[i][j]: ...，这比用enumerate还慢。
- 真要用矩阵，至少预处理每行的非零索引：
neighbors[i] = [j for j, v in enumerate(matrix[i]) if v]，只做一次 - 但更推荐直接转邻接表：
graph = {i: [] for i in range(n)}; for i in range(n): for j in range(n): if matrix[i][j]: graph[i].append(j) - 稀疏图下，邻接表内存占用也小得多——10k节点、100条边，矩阵要100MB，邻接表不到1MB
遇到环、孤立点、不连通图时的典型表现
DFS本身不保证访问全部节点，它只从起点出发。常见错误是调用一次dfs(graph, 0)就以为全图遍历完了，结果孤立点或另一连通分量里的节点根本没进visited。
真正健壮的实现得外层套个循环：for node in all_nodes:，跳过已访问的。但这不是DFS的问题，是使用者没理解「DFS是遍历策略，不是图算法全貌」。
-
visited必须是全局集合，不能每次递归都新建；栈版本同理，visited要在while外初始化 - 无向图边存两份（
a→b和b→a），但visited检查到位的话，不会重复递归——这点常被怀疑“为什么没死循环”，其实是机制在起作用 - 有向图中，从A出发搜不到B，不代表B不可达，只是方向反了；这时候需要考虑
reverse_graph或换起点
实际写的时候，递归看着清爽，但生产环境一律用栈；图结构不确定时，先打印len(graph)和max(len(v) for v in graph.values())看规模，再决定要不要加sys.setrecursionlimit()——加了也可能OOM，不如一开始就选对路。
