第64天：Python 深度优先搜索（DFS）在树上的堆栈式迭代遍历，实现无递归的深度探索

Source: Dev.to

第 64 天要点：迭代 DFS 函数

1. 函数设计：栈和已访问列表的初始化

dfs 函数接受一棵树的字典和起始节点，返回遍历顺序：

def dfs(tree: dict, start):
    """Perform DFS traversal starting from the given node."""
    visited = []          # store traversal order
    stack = [start]       # stack for DFS (LIFO)

2. 循环处理：弹出、访问、逆序压入子节点

核心 while 循环处理栈：

    while stack:
        node = stack.pop()               # take the top node from stack

        if node not in visited:
            visited.append(node)         # mark node as visited

            # push children in reverse order to maintain left‑to‑right traversal
            for child in reversed(tree.get(node, [])):
                stack.append(child)

    return visited

• 节点被弹出后，如果尚未出现则加入 visited（前序遍历）。
• 子节点逆序压入，以保证左侧子节点最先被处理。
• tree.get(node, []) 能安全处理叶子节点。

3. 示例用法：定义树并打印

使用基于字典的树进行演示：

tree = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": [],
    "F": []
}

start_node = "A"

print("Tree:", tree)
print(f"Starting DFS from node: {start_node}")

traversal = dfs(tree, start_node)
print(f"DFS Traversal Order: {traversal}")

运行脚本会打印树结构、从 A 开始进行 DFS，并输出遍历顺序 [A, B, D, E, C, F]【https://dev.topreorder/】。

总结与思考

• 栈模拟递归——对深层树安全。
• 逆序压栈在不额外工作情况下保持左到右的顺序。
• 在弹出时标记已访问实现前序遍历时机。

递归写法优雅，但在深度 > 1000 时可能失败。迭代方式更安全、可控。

后续步骤与资源

• 挑战 #64 的源码： scripts/dfs_tree.py
• 主仓库： 80-days-of-challenges
• 每日更新： Twitter/X (@Shahrouzlogs)