深度优先搜索（DFS）：从递归到回溯，我这样理解

DFS 这东西，说白了就是「一条路走到黑，撞了南墙再回头」。我刚开始学算法时，总觉得它和递归是一回事——后来踩过坑才明白，递归只是实现手段，DFS 是一种遍历或搜索策略。

你想想看，生活中找东西是不是也这样？进一个房间，先翻抽屉最里面，翻到底了再退出来翻下一个抽屉。这就是 DFS 的直觉。

DFS 的核心模板

我个人习惯把 DFS 模板分成两类：二叉树上的 DFS 和 图上的 DFS。前者是后者的特例，但面试中图上的 DFS 更常考。

先给一个最通用的模板，我用了五年了，几乎没改过：

def dfs(当前状态,  visited集合):
    # 1. 终止条件
    if 当前状态不合法:
        return
    
    # 2. 标记已访问（防止死循环）
    visited.add(当前状态)
    
    # 3. 处理当前节点
    处理逻辑()
    
    # 4. 遍历所有邻居
    for 邻居 in 当前状态的邻居们:
        if 邻居 not in visited:
            dfs(邻居, visited)
    
    # 5. 可选：回溯（撤销标记）
    # visited.remove(当前状态)  # 看场景是否需要

嗯，这里要注意：第 5 步的回溯不是必须的。什么时候要？当你需要枚举所有路径时。什么时候不要？当你只需要遍历所有节点时。我曾经在「岛屿数量」这道题上搞混过，结果死循环了半小时。

邻接表 vs 邻接矩阵：我选哪个？

做图相关的 DFS，第一步就是选数据结构。我直接给结论：

对比维度	邻接表	邻接矩阵
空间复杂度	O(V+E)，稀疏图省空间	O(V²)，稠密图才划算
判断两点是否相连	O(degree)，需要遍历链表	O(1)，直接查矩阵
遍历所有邻居	O(degree)，直接拿到列表	O(V)，要扫一整行
代码实现难度	稍复杂，但灵活	简单，二维数组搞定
我推荐场景	90% 的面试题	节点少（<100）且稠密

我在项目中遇到过一个问题：社交网络的好友关系用邻接矩阵存，结果 10 万用户直接内存爆炸。后来改成邻接表，不仅省了 90% 内存，遍历速度还快了。说白了，面试里 90% 的情况用邻接表就够了。

邻接表的 Python 实现长这样：

# 构建邻接表
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# 或者用列表存（节点编号从0开始）
n = 4
graph = [[] for _ in range(n)]
edges = [(0,1), (0,2), (1,3), (2,3)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)  # 无向图要加双向

经典例题一：岛屿数量

这道题我面过不下 5 次，每次都能看到有人卡在「怎么标记已访问」上。

题目很简单：给你一个二维网格，'1' 是陆地，'0' 是水，问有多少个岛屿（连在一起的 '1' 算一个）。

DFS 的思路：每遇到一个 '1'，就把它和它所有的邻居 '1' 都淹成 '0'。淹完一个，岛屿数加一。

def numIslands(grid):
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    count = 0
    
    def dfs(r, c):
        # 越界或遇到水，直接返回
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        # 淹掉当前陆地
        grid[r][c] = '0'
        # 四个方向继续淹
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    
    return count

这里有个小技巧：直接在原数组上改值，省去了 visited 集合。我曾经在面试时用 visited 集合，被面试官问「能不能省点空间？」——嗯，从此我就记住了这个「原地标记法」。

经典例题二：课程表（拓扑排序的 DFS 版）

这道题是 DFS 的进阶应用。题目说：有 n 门课，给你一些先修关系，比如 [1,0] 表示上 1 之前必须先上 0。问能不能上完所有课？

说白了，就是检测有向图里有没有环。有环就上不完，没环就能上完。

DFS 检测环的思路：给每个节点三种状态——0 未访问、1 正在访问、2 已访问完。如果在 DFS 过程中遇到了「正在访问」的节点，说明有环。

def canFinish(numCourses, prerequisites):
    # 构建邻接表
    graph = [[] for _ in range(numCourses)]
    for course, pre in prerequisites:
        graph[pre].append(course)
    
    # 0=未访问, 1=正在访问, 2=已访问完
    visited = [0] * numCourses
    
    def dfs(course):
        if visited[course] == 1:  # 遇到正在访问的节点，有环
            return False
        if visited[course] == 2:  # 已经处理过，不用重复
            return True
        
        visited[course] = 1  # 标记为正在访问
        for neighbor in graph[course]:
            if not dfs(neighbor):
                return False
        visited[course] = 2  # 标记为已访问完
        return True
    
    for i in range(numCourses):
        if not dfs(i):
            return False
    return True

DFS 的时间复杂度分析

这个其实很简单：每个节点访问一次，每条边也访问一次。所以：

• 邻接表实现：O(V + E)，V 是节点数，E 是边数
• 邻接矩阵实现：O(V²)，因为每行都要扫一遍

空间复杂度主要看递归深度：最坏情况 O(V)，比如一条链。如果图特别深，递归可能栈溢出——我遇到过，后来改成显式栈（迭代 DFS）解决了。

DFS 的避坑指南

• 死循环：忘记标记已访问，或者标记了但回溯时又撤销了。我刚开始学的时候，经常在「需要回溯」和「不需要回溯」之间搞混。
• 栈溢出：递归深度太大。Python 默认递归深度约 1000，超过就崩。解决方案：调大递归限制（sys.setrecursionlimit）或者改成迭代。
• 方向搞错：二维网格的 DFS，四个方向还是八个方向？看清楚题目。岛屿数量是四个方向，但有些题是八个方向。
• 状态重置：如果 DFS 是用于「路径搜索」（比如迷宫找所有路径），记得回溯时把状态改回来。如果是「遍历所有节点」（比如岛屿数量），不需要回溯。

本章知识体系

下面这张图总结了 DFS 的核心要点，我每次讲课时都会画一遍：

这张图把 DFS 拆成了三个维度：模板怎么写、数据结构怎么选、例题怎么套。每次做题前，先想清楚这三个问题，代码基本不会跑偏。

---

DFS 是算法面试的「基本功」，也是很多难题的起点。我个人觉得，把 DFS 练熟了，后面学回溯、剪枝、记忆化搜索都会轻松很多。嗯，下一章我们聊 BFS，到时候你会发现 DFS 和 BFS 其实是一体两面。