深度优先搜索DFS：不撞南墙不回头

深度优先搜索（Depth First Search，简称DFS）是一种常见的图遍历算法，就像你在一个大迷宫里，每次遇到岔路都选最右边的那条走，一直走到死胡同或者终点。如果走不通，就退回到上一个岔路，换另一条没走过的路继续走。用这种“一条路走到黑，不行再回头”的方式，你可以把迷宫里的每一条路都探索一遍。

在计算机里，DFS也这样工作：它会沿着一个分支尽可能深地探索，直到无法继续，然后回溯（退回去）尝试其他分支。它可以用来解决很多问题，比如：

在图中从某个点出发，找到另一个点（路径查找）
判断两个点之间是否连通
生成迷宫、解数独
在游戏地图中自动寻路

下面我们一步步拆解DFS的核心概念，并用代码来实现它。

一、核心思想：递归与回溯

DFS 依赖两个关键动作：

深入：每到一个新节点，就继续往它的第一个邻居走，再往那个邻居的第一个邻居走……像叠罗汉一样层层递归下去。
回溯：当走到死胡同（没有未访问的邻居）或者找到目标时，就一层层“退回来”，回到上一个岔路，换另一个方向继续。

生活中的例子

想象你在一座大房子里找钥匙，房子有好多房间，每个房间又有柜子、抽屉。你的策略是：走进一个房间，先打开柜子，如果柜子里有抽屉，就挨个打开抽屉找；如果找不到，就退出柜子，看看房间里的其他地方；如果整个房间都找完了，就退回到走廊，去下一个房间继续找。这个“退回来”的动作就是回溯。

为什么需要“回溯”？

如果不回溯，你只能沿着一条路走到黑，一旦走不通，你就停在那里了，没法换别的路。回溯让你能回到之前的决策点，尝试其他可能性。在代码中，回溯通常通过递归函数的自动返回或者栈的弹出来实现。

二、关键细节：visited 集合与路径记录

1. 避免绕圈的 `visited` 集合

在图中，节点之间可能有环路（比如 A→B→C→A）。如果不做记录，DFS 会在环里转圈，永远出不来。所以我们要用一个叫 visited 的集合，把访问过的节点记下来。每到一个新节点，先看看它是不是已经在 visited 里，如果是，就跳过，不再重复访问。

2. 记录行走路线的 `path` 列表

有时候我们不仅想知道有没有找到目标，还想知道具体是怎么走过来的。用一个列表 path 记录访问路径，每深入一步就把当前节点加进去，回溯时再把它移除（path.pop()）。

3. 邻居的选择顺序

DFS 探索邻居的顺序取决于你如何列出邻居列表。如果按邻居在列表中的顺序依次尝试，那么第一次找到的路径就是按照这个顺序的第一条可行路径。你可以通过改变邻居顺序来影响搜索结果。

三、代码实现：从节点1出发找节点5

下面我们用Python实现一个简单的DFS，在一个无向图中寻找从节点1到节点5的路径。图的结构用字典存储，每个节点记录它可以到达的邻居。

# 图：用字典表示，键是节点，值是该节点的邻居列表
graph = {
    1: [2, 3],      # 节点1的邻居是2和3
    2: [1, 4],      # 节点2的邻居是1和4
    3: [1, 4],      # 节点3的邻居是1和4
    4: [2, 3, 5],   # 节点4的邻居是2、3、5
    5: [4]          # 节点5的邻居只有4
}

visited = set()    # 记录已经访问过的节点，防止绕圈

def dfs(node, target, path):
    # node: 当前正在搜索的节点
    # target: 要找的目标节点
    # path: 从起点到当前节点的路径列表

    if node in visited:         # 如果这个节点已经访问过，就不重复处理
        return
    visited.add(node)           # 标记当前节点为已访问
    path.append(node)           # 把当前节点加入路径

    if node == target:          # 如果找到了目标
        print("找到路径:", path)
        # 注意：这里没有立即return，目的是展示所有可能的路径
        # 实际中可以用 return True 提前结束搜索（剪枝）

    for neighbor in graph[node]:   # 遍历当前节点的每一个邻居
        dfs(neighbor, target, path)  # 递归深入邻居

    # 回溯：从当前节点退回到上一层
    path.pop()                   # 把当前节点从路径中移除
    # 注意：我们不移除 visited 中的标记，否则又会重复访问相同节点

# 开始搜索：从节点1出发，目标节点5，初始路径为空列表
dfs(1, 5, [])

运行结果分析

运行这段代码，你会看到输出（可能因为邻居顺序不同而略有差异）：

找到路径: [1, 2, 4, 5]

为什么只输出了一条路径？因为一旦我们访问过节点，visited 就把它记住了，后面不再进入。所以实际上我们只找到了一条路径（第一次成功找到的那条），其他可能的路径（比如1→3→4→5）因为节点4在第一次已经被访问过，所以不会再走那条路。

如果你想要找出所有路径，需要在回溯时把 visited 中的标记也移除（但要小心，这样可能因为环路而无限循环，通常需要额外限制）。在大部分应用中，我们只需要找到一条路径就够了，所以这样处理是合理的。

四、新手容易犯的错误

1. 忘记标记 `visited`

def dfs(node, target, path):
    # 没有 visited.add(node)
    path.append(node)
    # ...

后果：在环状图中会无限递归，最终导致程序崩溃（递归深度过大）。

家 → 超市 → 学校 → 公园
↓                        ↑
医院 → 图书馆 → 电影院 → 公园

用DFS来搜索一条路径：

# 地图：每个地点能去的地方
map_graph = {
    '家':        ['超市', '医院'],
    '超市':      ['家', '学校'],
    '医院':      ['家', '图书馆'],
    '学校':      ['超市', '公园'],
    '图书馆':    ['医院', '电影院'],
    '电影院':    ['图书馆', '公园'],
    '公园':      ['学校', '电影院']
}

visited = set()  # 记录去过的地方

def find_key(place, target, path):
    if place in visited:
        return False
    visited.add(place)
    path.append(place)
    if place == target:
        print(f"找到钥匙！路线：{' → '.join(path)}")
        return True  # 找到目标后立即返回，不再搜索其他分支
    for next_place in map_graph[place]:
        if find_key(next_place, target, path):
            return True  # 如果下一层找到了，也直接返回
    path.pop()   # 回溯：这条路没找到，从路径中移除当前地点
    return False

print("开始找钥匙...")
find_key('家', '公园', [])

运行输出：

开始找钥匙...
找到钥匙！路线：家 → 超市 → 学校 → 公园

注意，这里的DFS在找到目标后就立即返回（return True），不会再尝试其他路线，这叫“剪枝”，能提高效率。

六、相关知识点指引

广度优先搜索（BFS）：DFS是“纵向”深入，BFS是“横向”一层层往外搜索。BFS适合找到最短路径（步数最少的路径），而DFS适合判断是否存在路径或需要深入探索时使用。
回溯算法：DFS是回溯算法的一种具体实现，很多经典问题如八皇后、数独、全排列都用到了DFS + 回溯。
递归与栈：DFS的递归本质上是系统自动维护了一个栈（函数调用栈）。你也可以手动用栈来实现DFS，避免递归深度限制。
图的表示：除了用字典（哈希表）表示邻接表，还可以用二维数组（邻接矩阵）来表示图。

现在你已经理解了DFS的核心思想，可以试着用它来解决更多有趣的问题，比如用DFS生成一个迷宫，或者在游戏里让角色自动寻路。动手试一试吧！

深度优先搜索DFS