CC++ & Algorithm

深度优先搜索（DFS）——像走迷宫一样探索

中等8
语言版本：C++Python
概述：深度优先搜索是一种沿着一条路走到底再回头找别的路的方法，适合在树或图中寻找特定目标。

深度优先搜索（DFS）——像走迷宫一样一条路走到底

你有没有玩过走迷宫？从入口进去，遇到岔路先随便选一条，一直往前走，如果碰到死胡同就掉头，回到刚才的岔路口换一条路继续试。这种“一条路走到底，走不通就回头”的策略，就是深度优先搜索（Depth First Search，简称DFS）。

在编程里，DFS是用来在树或图这样的结构中，系统地探索每一个节点的。它适合用来解决“有没有这样的路径？”“能不能找到某个目标？”之类的问题，比如：

  • 从文件夹中找到隐藏的图片文件（先点开一个文件夹，再点开它的子文件夹……直到没得点，再退回上一级）
  • 判断从一个城市坐火车能不能到达另一个城市（沿着一条铁路线一站一站往下走，走不通就换线）
  • 在游戏地图里寻找宝藏（先走一条路，直到尽头，再回来换方向）

下面我们来拆解DFS的核心思想，并学习怎么用Python写出来。

1. DFS是什么？两条腿走路：深入 + 回溯

想象你在教室里找一位戴红色帽子的同学。你可以从第一组第一排开始，顺着这一排一直看到最后一排。如果这一排没有，你就回到第二组第一排继续看，直到把所有座位都检查完。这种“看完一整排再换下一排”的方式，本质上就是DFS在二维空间中的体现——先沿着一个方向走到尽头，然后退回来换方向。

在电脑里，DFS通常用两种方式实现：

  • 递归：把问题一层层拆下去，让函数自己调用自己深入，返回时自动回溯。
  • 栈：用后进先出的数据结构，自己控制“走过的路”和“待选的路”。

无论哪种方式，核心思想都一样：标记已经走过的节点，避免重复走，然后不断深入下一个未走过的邻居，直到走完全部。

2. 用递归实现DFS：像贪吃蛇一样不断深入

先来看最简单的情况——树（没有环，不会走回头路）。我们可以用递归函数，访问当前节点，然后对每个子节点依次调用自身。

下面这段代码定义了一个简单的树节点，并实现DFS搜索：

# 定义树的节点
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []  # 子节点列表

# 深度优先搜索（递归实现）
def dfs(node, target):
    if node is None:
        return False
    print(f"访问节点: {node.value}")  # 模拟访问过程（方便观察）
    if node.value == target:
        print(f"找到了目标: {target}")
        return True
    # 依次深入每个子节点
    for child in node.children:
        if dfs(child, target):  # 递归调用，继续往深处走
            return True  # 一旦在某个子树中找到，立即返回
    return False  # 所有子节点都找完都没找到

# 构建一棵树：根节点A，子节点B、C，B又有子节点D
root = TreeNode("A")
child_b = TreeNode("B")
child_c = TreeNode("C")
child_d = TreeNode("D")
root.children = [child_b, child_c]
child_b.children = [child_d]

# 执行搜索，目标为"D"
dfs(root, "D")

运行时会打印：

访问节点: A
访问节点: B
访问节点: D
找到了目标: D

可以看到，程序先访问A，然后进入第一个子节点B，继续深入B的子节点D，找到了目标。如果目标不存在，它会退回B，然后退回A，再去访问C。

用生活中的例子理解递归DFS：假设你要在图书馆一个书架里找一本《哈利波特》。你会先看第一格（根节点），如果没有，就看向下一格（子节点）。如果这一格里面还有夹层，你会先翻开夹层继续看（递归深入）。直到这一格所有夹层都翻完，才会回到上一格，继续看旁边的格子。

3. 用栈模拟DFS：自己管理“待探索的路口”

递归虽然简洁，但有时候我们希望自己控制回溯过程，或者避免递归过深导致栈溢出。这时可以用栈（后进先出）来模拟。

思路是：先把起点放进栈，然后循环：

  1. 从栈中取出一个节点（栈顶元素）
  2. 如果它是目标，返回成功
  3. 否则，把它的所有子节点（或未访问的邻居）都压入栈

注意：因为栈是后进先出，所以我们压入节点的顺序会影响搜索顺序。如果要和递归顺序一致，通常按逆序压入（或者按你想优先探索的顺序）。

下面是把前面的树用栈实现的DFS：

# 用栈实现树的DFS
def dfs_stack(root, target):
    if root is None:
        return False
    stack = [root]  # 栈，初始放入根节点
    while stack:
        node = stack.pop()  # 取出栈顶节点（后进先出）
        print(f"访问节点: {node.value}")
        if node.value == target:
            print(f"找到了目标: {target}")
            return True
        # 把子节点压入栈，注意顺序：我们想让先添加的子节点优先被访问，
        # 由于栈是后进先出，我们需要反转顺序压入
        # 或者你可以简单地把children直接反转后再扩展
        for child in reversed(node.children):  # 反转使左边的子节点先被访问
            stack.append(child)
    return False

# 使用上面建好的树
dfs_stack(root, "D")

结果和递归版本一样。栈的好处是不会因为递归层数太多而报错（只要内存够大），而且更容易理解“回溯”是如何发生的——每次从栈中弹出节点，相当于“退回到上一个岔路口”。

4. 当有环时：别忘了标记已访问的节点

如果是在图中搜索（可能含有环），事情就有点不一样了。比如你在一座迷宫里有循环通道，如果不做标记，可能会一直在同一个圈里打转，永远出不来。

解决办法很简单：用集合（set）记录已经访问过的节点，每次遇到一个节点先检查是否访问过，如果访问过就跳过。

下面是一个用邻接表表示的无向图，我们从起点"A"出发，用DFS搜索目标"F"：

# 图用字典表示：键是节点，值是邻居列表
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

# 深度优先搜索（带visited集合，防止死循环）
def dfs_graph(node, target, visited):
    if node == target:
        print(f"找到了目标: {target}")
        return True
    visited.add(node)  # 标记当前节点已访问
    print(f"访问节点: {node}")
    for neighbor in graph[node]:
        if neighbor not in visited:  # 只去没去过的地方
            if dfs_graph(neighbor, target, visited):
                return True
    return False

# 执行搜索
visited_set = set()  # 记录已访问节点
result = dfs_graph("A", "F", visited_set)
print("搜索结果:", result)

输出会类似：

访问节点: A
访问节点: B
访问节点: D
访问节点: E
访问节点: F
找到了目标: F

可以看到DFS从A出发，先往B走，然后B→D（到底了），退回B→E，再从E→F，成功。如果没标记已访问，那么在从E走到F时，F的邻居又有E和C，其中E已经去过，但因为没有标记，程序可能又会走回E，形成死循环。有了visited集合，就不会重复走。

5. 新手容易踩的坑

  1. 忘记标记已访问节点：尤其在图中，这是最常见的错误，会导致程序无限递归或栈溢出。记住：每进入一个新节点，先把它加入visited集合。

  2. 递归没有设置终止条件：比如在树中，如果节点是None，必须立即返回。否则会报AttributeError或死循环。

  3. 返回值处理错误：递归函数内部，找到目标后要return True，并且每一层调用都要把这个True传导回去（如前面代码中的if dfs(child, target): return True）。新手容易忘记传递返回值，导致找到目标后仍然返回False。

  4. 栈的顺序搞反：用栈实现时，由于后进先出的特性，压入邻居的顺序会影响搜索路径。希望你优先搜索左边的节点，那就要将邻居反转后压栈（或者用deque中的appendleft）。如果不理解，可以先print观察访问顺序。

  5. 递归深度超限（RecursionError）：Python默认递归深度约1000层。如果图或树很深（比如10000层），递归会报错。此时应该改用栈实现，或者增大递归深度（不推荐，容易内存溢出）。实际应用更推荐栈版本。

6. 完整可运行示例：在图中找到路径并打印路径

有时候我们不仅想知道能不能到，还想知道具体路线。下面的代码用DFS找从起点到终点的路径，并保存下来：

# 图：字典形式，键是节点，值是邻居列表
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

# 深度优先搜索寻找路径（返回路径列表，若找不到返回None）
def dfs_path(node, target, visited, path):
    # 将当前节点加入路径
    path.append(node)
    # 如果找到目标，返回路径
    if node == target:
        return path[:]  # 返回路径的副本
    visited.add(node)  # 标记已访问
    # 遍历所有邻居
    for neighbor in graph[node]:
        if neighbor not in visited:
            result_path = dfs_path(neighbor, target, visited, path)
            if result_path is not None:
                return result_path
    # 回溯：从路径中移除当前节点（因为这条路走不通）
    path.pop()
    return None

# 执行搜索
visited = set()  # 已访问节点集合
path = []        # 当前路径
found_path = dfs_path("A", "F", visited, path)
if found_path:
    print("找到路径:", " -> ".join(found_path))
else:
    print("没有到达目标的路径")

输出：

找到路径: A -> B -> E -> F

这个代码的关键在于回溯：当从一个节点出发探索完所有邻居都没有找到目标时，需要把这个节点从路径中移除（path.pop()），然后返回None让上一层继续尝试其他分支。这就是DFS中“退回去”的编程实现。

7. 学完DFS后，下一步可以学什么？

  • 广度优先搜索（BFS）：和DFS“一条路走到底”不同，BFS是一层一层扫描。适合找最短路径（比如你从A到地铁站的最少换乘方案）。
  • 回溯算法：DFS是回溯的基础。当需要找出所有可能的解（比如8皇后、数独、排列组合）时，就是在DFS的过程中加上剪枝。
  • 递归与栈的转换：任何递归都可以用栈改写，反过来也成立。理解这种等价关系能让你写出更灵活的代码。
  • 图的遍历：DFS和BFS是图论中最基本的两个遍历算法，后面还会学到更复杂的如拓扑排序、强连通分量等。

如果你觉得递归的思路有点绕，可以先从栈模拟入手，画纸上的“栈”来模拟几遍流程，很快就能上手。DFS就像走迷宫，多走几次，你也就能在代码里自如地“一条路走到底，走不通就回头”了。

例题精讲

1单选题

给定一个无向图，从节点A开始进行深度优先搜索，以下哪种访问顺序是正确的？

AA→B→D→C→E
BA→B→C→D→E
CA→C→E→B→D
DA→D→E→C→B
2判断题

深度优先搜索可以使用栈（Stack）数据结构来实现非递归版本。

3填空题
以下Python代码使用递归实现图的深度优先搜索，请补全缺失部分。
def dfs(graph, node, visited):
    visited.add(node)
    print(node, end=' ')
    for neighbor in graph[node]:
        if neighbor ___ visited:
            dfs(graph, neighbor, visited)
4单选题

在一棵二叉树中，使用深度优先搜索的“前序遍历”访问节点。已知二叉树的前序遍历序列为A、B、D、E、C、F，则以下哪项不可能是树的结构？

AA的左孩子是B，B的左孩子是D，B的右孩子是E，A的右孩子是C，C的左孩子是F
BA的左孩子是B，B的右孩子是D，D的左孩子是E，A的右孩子是C，C的右孩子是F
CA的左孩子是B，B的左孩子是D，A的右孩子是C，C的左孩子是E，E的右孩子是F
DA的左孩子是B，B的左孩子是D，B的右孩子是E，A的右孩子是C，C的右孩子是F
5判断题

在无向图中，使用深度优先搜索可以检测是否存在环。