栈实现DFS非递归搜索详解

本文深入解析了如何利用栈（Stack.push() 和 pop()）手动模拟递归调用过程，实现深度优先搜索（DFS）的非递归版本——核心在于精准把握栈的“后进先出”特性：将待访问节点压入栈中，出栈时才标记访问并处理，邻接节点需逆序入栈以严格复现递归DFS的遍历顺序，同时配合visited集合防止重复访问与死循环；无论是图的遍历还是二叉树的前序遍历，该方法均简洁高效、逻辑清晰，是理解DFS本质与提升算法实现能力的关键实践。

用 Stack.push() 和 pop() 实现 DFS 的非递归版本，核心是**手动模拟递归调用栈的行为**：把待访问的节点按“后进先出”顺序压入栈，每次取出栈顶节点处理，并将其未访问的邻接节点依次压入——这样就能保证沿着一条路径尽可能深入，回溯时自然弹出上层节点。

明确栈中存什么

栈里一般存的是待探索的节点（如图的顶点编号、树的节点引用等）。有时需额外信息，比如：

• 只遍历：存节点本身即可（如 stack.push(node)）
• 需要路径或深度：可存对象，如 { node: n, depth: d }
• 避免重复访问：配合 visited 数组/集合使用，入栈前检查，或出栈时检查

基本流程（以无向图邻接表为例）

假设图用 graph[node] 返回邻居列表，起点为 start：

• 初始化空栈，将 start 压入
• 维护 visited 集合，记录已访问节点
• 当栈非空：
    – 弹出栈顶节点 cur
    – 若未访问，标记为已访问，处理它（如打印、收集）
    – 遍历 cur 的所有邻居，对每个未访问邻居调用 stack.push(neighbor)

注意：若希望与递归 DFS 的访问顺序完全一致（比如按邻接表索引升序深入），应**逆序压入邻居**（例如邻居是 [2,5,3]，就按 [3,5,2] 顺序 push），否则栈的 LIFO 特性会使最先 push 的最后处理。

树的前序遍历（非递归）示例

二叉树 DFS 前序（根→左→右）可直接用栈：

• 栈初始存根节点
• 循环中：
    – pop 得到当前节点
    – 访问该节点（如加入结果数组）
    – 先 push 右子节点（若存在），再 push 左子节点（若存在）
  （这样左子节点在栈顶，下一轮优先处理）

关键细节提醒

不要在入栈时标记 visited——因为节点可能被多次压入（尤其在图中多路径可达时），应在 出栈并准备处理时才标记和访问，避免遗漏；
避免无限循环：图中必须用 visited 控制，树则天然无环；
栈为空即搜索结束，无需额外终止条件。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~