迭代DFS的陷阱与正解：避免非预期图遍历

深度优先搜索（DFS）在图（包括二叉树或其他图）上的实现，通常采用递归方式。然而，当面临调用栈溢出的风险时，迭代方法成为一个可行的替代方案。此时，利用自定义栈而非程序隐式调用栈来实现DFS是明智之举。但若操作不当，极易陷入误区，导致搜索并非真正的DFS。

在图S出发的DFS中，若先访问A，则后续应访问B或D；若先访问C，则后续应访问D或F。但错误的栈实现可能导致S先访问A，再访问C，这违背了DFS的特性。核心问题在于，在栈实现中，高层节点过早地将其邻居推入栈中，而真正的DFS应将它们作为更深层的后代节点来发现。

一个有效的迭代DFS实现，可以采用栈管理邻居迭代器的方式，这与递归DFS的行为和空间复杂度一致。另一种方法是，在弹出节点后再检查其访问状态，并先将所有邻居压栈。此方法虽然会增加栈的副本，但能保证DFS的正确性。若要最大程度模拟递归DFS的顺序，需反向压入邻居节点。

无论是栈管理迭代器还是延迟检查访问状态，这些方法在将栈替换为队列时，都能实现广度优先搜索（BFS），尽管方式略有不同。这些精确的DFS实现对于算法设计至关重要，因为它们提供了对图结构的特定视角，而错误的栈遍历则可能在依赖严格DFS特性的算法（如强连通分量计算）中导致失败。

Iterative DFS with stack-based graph traversal | Software Engineering Handbook

This post explores how to effectively implement an iterative depth-first search (DFS) traversal on a graph with a stack, addressing a common pitfall along the way.

Software Engineering HandbookDaniel Farlow