深度优先搜索（DFS） - 数据结构与算法-学习笔记-上海佼艾

一、DFS 核心思想

深度优先搜索（Depth-First Search, DFS）是图论和树结构中最基本的遍历算法之一。其核心思想可以用一句话概括：从一个起点出发，沿着一条路径走到黑，走不通了再回头尝试其他路径。这种"不撞南墙不回头"的策略体现了穷举搜索的本质——系统地遍历状态空间中的所有可能路径，直到找到目标解或者确认无解为止。

1.1 递归实现

递归是实现 DFS 最直观的方式。递归函数天然具备"深入-返回"的语义：每次递归调用都代表向更深层探索一步，函数返回则代表回溯到上一层。递归实现的 DFS 通常包含三个核心组成部分：终止条件（base case）、当前状态处理、以及递归调用下一步。

def dfs(self, node, visited):
    # 1. 终止条件：如果节点已被访问，则返回
    if node in visited:
        return

    # 2. 访问当前节点
    visited.add(node)
    print(f"正在访问节点: {node}")

    # 3. 递归访问所有邻居节点
    for neighbor in self.graph[node]:
        self.dfs(neighbor, visited)

上述代码展示了 DFS 最简洁的形式。visited 集合用于防止重复访问和环路死循环，这在有环图中至关重要。每次递归调用都在栈上开辟新的栈帧，记录当前函数的局部变量和执行位置——这正是递归能够自动回溯的根本原因。

1.2 显式栈实现

除了递归，DFS 也可以使用显式的栈数据结构来实现。显式栈的好处在于避免了递归调用的栈溢出风险（Python 默认递归深度限制约 1000 层），同时也让搜索过程更加可控。栈的 LIFO（后进先出）特性天然契合深度优先的探索顺序：最后一个加入的节点会被最先处理。

def dfs_stack(start_node):
    visited = set()
    stack = [start_node]

    while stack:
        node = stack.pop()

        if node in visited:
            continue

        visited.add(node)
        print(f"正在访问节点: {node}")

        # 逆序加入栈，维持与递归一致的访问顺序
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)

在显式栈版本中，需要注意邻居节点的入栈顺序。因为栈是后进先出，如果我们按照原始顺序将邻居压入栈中，那么最后一个邻居就会被最先访问，这可能与递归版本的访问顺序不同。通过 reversed 逆序入栈，可以保持与递归版本一致的访问顺序。此外，显式栈还有另一个优势：我们可以通过在栈中存储额外信息（如当前路径深度、已累积的代价等）来实现更复杂的搜索策略。

1.3 回溯机制

回溯是 DFS 的核心机制，但回溯和 DFS 并非完全等同的概念。更准确地说：回溯法是一种通过 DFS 遍历解空间树并在遇到不符合约束条件的分支时提前返回（剪枝）的算法设计方法。DFS 提供了遍历的框架，而回溯则是在这个框架上增加了"状态重置"和"约束检查"两个关键操作。

def backtrack(path, choices, result):
    # 终止条件：路径满足要求
    if len(path) == target_len:
        result.append(path[:])  # 深拷贝，避免后续修改影响
        return

    # 遍历所有选择
    for choice in choices:
        # 剪枝：跳过不符合约束的选择
        if not is_valid(choice, path):
            continue

        # 做选择
        path.append(choice)

        # 递归探索下一步
        backtrack(path, choices, result)

        # 撤销选择（回溯的核心操作）
        path.pop()

回溯的关键模式是"选择-探索-撤销"这个三段式结构。每次递归调用前，我们将一个选择加入路径；递归返回后，我们撤销这个选择，使状态恢复到调用之前的样子。这种状态重置（也称为"恢复现场"）使得同一个路径列表可以在整个搜索过程中被重复利用，避免了大量的内存拷贝开销。

核心理解：DFS 和回溯的关系可以类比为"遍历框架"和"问题求解策略"。DFS 是遍历图或树的所有节点的通用方法，而回溯则是在 DFS 遍历解空间树的基础上，增加了约束判断和状态重置的机制，专门用于解决约束满足问题和组合优化问题。

二、DFS 在树与图中的应用

DFS 在树结构和图结构中有着广泛的应用。虽然树的 DFS 和图的 DFS 在核心思想上一致，但在具体实现和关注点上存在重要差异：树是连通无环图，因此不需要 visited 集合来防止环路；而图可能包含环，必须使用 visited 或更精细的标记机制来避免无限循环。

2.1 树的 DFS：前序、中序、后序遍历

在二叉树中，DFS 有三种经典的遍历顺序，每种顺序对应着不同的"访问根节点"时机。这三种遍历方式在表达式求值、序列化/反序列化、以及构建平衡树等场景中各有用途。

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 前序遍历：根-左-右（用于复制树、前缀表达式）
def preorder(root):
    if not root:
        return
    print(root.val)     # 访问根节点
    preorder(root.left)   # 遍历左子树
    preorder(root.right)  # 遍历右子树

# 中序遍历：左-根-右（用于BST排序输出、中缀表达式）
def inorder(root):
    if not root:
        return
    inorder(root.left)    # 遍历左子树
    print(root.val)       # 访问根节点
    inorder(root.right)   # 遍历右子树

# 后序遍历：左-右-根（用于删除树、计算目录大小、后缀表达式）
def postorder(root):
    if not root:
        return
    postorder(root.left)  # 遍历左子树
    postorder(root.right) # 遍历右子树
    print(root.val)       # 访问根节点

理解三种遍历顺序的关键在于：递归函数调用的顺序决定了当前节点值被处理的时机。在前序遍历中，我们在探索子节点之前就处理当前节点；中序遍历则在左子树处理完毕之后、右子树处理之前处理当前节点；后序遍历在左右子树都处理完毕之后才处理当前节点。这种微妙的时序差异使得同一棵树在不同遍历顺序下产生的序列截然不同。

实用技巧：在二叉搜索树（BST）中，中序遍历的结果是升序序列；后序遍历的结果可以用于自底向上的动态规划（如树形DP）；前序遍历则常用于序列化树结构。掌握这三种遍历对理解递归和 DFS 至关重要。

2.2 图的 DFS：连通分量与拓扑排序

在图中，DFS 的一个基本应用是查找连通分量。无向图的一个连通分量是指图中最大的连通子图，其中任意两个顶点之间都存在路径。通过 DFS 标注每个顶点所属的连通分量编号，可以在 O(V+E) 时间内完成对整个图的分割。

def find_connected_components(graph, n):
    visited = [False] * n
    components = []

    def dfs(v, comp):
        visited[v] = True
        comp.append(v)
        for neighbor in graph[v]:
            if not visited[neighbor]:
                dfs(neighbor, comp)

    for v in range(n):
        if not visited[v]:
            comp = []
            dfs(v, comp)
            components.append(comp)

    return components

对于有向图，DFS 还可以用于拓扑排序。拓扑排序是对有向无环图（DAG）的顶点进行线性排序，使得对每一条有向边 (u, v)，u 在排序中都出现在 v 之前。基于 DFS 的拓扑排序利用了后序遍历的特性：当我们对图进行 DFS 后序遍历时，先完成遍历的节点是"较深的"节点（即叶子或路径末端的节点），将遍历完成的顺序反转即可得到拓扑排序。

def topological_sort(graph, n):
    visited = [0] * n  # 0=未访问, 1=访问中, 2=已完成
    result = []
    has_cycle = [False]

    def dfs(v):
        if visited[v] == 1:  # 发现回边，存在环
            has_cycle[0] = True
            return
        if visited[v] == 2:
            return

        visited[v] = 1  # 标记为正在访问
        for neighbor in graph[v]:
            dfs(neighbor)
            if has_cycle[0]:
                return

        visited[v] = 2  # 标记为已完成
        result.append(v)   # 后序加入结果

    for v in range(n):
        if visited[v] == 0:
            dfs(v)

    return result[::-1]  # 反转得到拓扑排序

上述实现中，visited 数组使用了三个状态值：0 表示未访问、1 表示在当前 DFS 路径上（正在访问）、2 表示访问完成。这种三色标记法不仅可以防止重复访问，还能检测有向图中的环——当我们在 DFS 过程中遇到了标记为"正在访问"的节点时，就说明存在一条回边，即图中有环。

三、DFS 时间戳

DFS 时间戳（Timestamp）是对 DFS 遍历过程进行精确记录的技术。在遍历过程中，我们为每个节点记录两个时间值：发现时间（discovery time, d[v]）和完成时间（finish time, f[v]）。发现时间记录的是节点第一次被访问的时刻，完成时间记录的是节点所有邻接点都被探索完毕、即将离开的时刻。这两个时间戳构成了一个重要的区间性质——括号定理。

3.1 发现时间与完成时间

时间戳通过在 DFS 递归调用的入口和出口分别递增全局计数器来实现。入口处记录发现时间并递增计数器，出口处记录完成时间并递增计数器。

def dfs_with_timestamps(graph, n):
    visited = [False] * n
    d = [0] * n  # 发现时间
    f = [0] * n  # 完成时间
    timer = [0]  # 使用列表实现跨作用域的可变计数器

    def dfs(v):
        timer[0] += 1
        d[v] = timer[0]       # 记录发现时间
        visited[v] = True

        for neighbor in graph[v]:
            if not visited[neighbor]:
                dfs(neighbor)

        timer[0] += 1
        f[v] = timer[0]       # 记录完成时间

    for v in range(n):
        if not visited[v]:
            dfs(v)

    return d, f

3.2 括号定理与区间性质

括号定理（Parenthesis Theorem）是 DFS 时间戳最重要的性质。对于有向图或无向图中的任意两个节点 u 和 v，以下三种情况恰好有一种成立：

区间包含：如果区间 [d[u], f[u]] 完全包含区间 [d[v], f[v]]，那么 v 是 u 的后代（在 DFS 树中），即 u 的 DFS 子树包含 v。
区间不相交：如果区间 [d[u], f[u]] 和 [d[v], f[v]] 完全不相交，那么 u 和 v 分别属于不同的 DFS 子树，彼此没有祖先-后代关系。
不可能交叉：不可能出现两个区间部分重叠的情况。这个性质是 DFS 遍历过程的核心特征——对任意两个节点，它们的发现-完成时间区间要么一个包含另一个，要么完全不相交。

括号定理的直观理解：可以把 DFS 遍历过程想象成在树中行走，每到达一个节点时就画一个左括号"("，离开时画一个右括号")"。那么每个节点的"发现-完成"区间就对应着一对括号。括号定理保证了这些括号对要么嵌套（祖先-后代关系），要么并列（不同子树关系），永远不会出现跨括号交叉的情况。

3.3 拓扑排序与时间戳的关系

利用完成时间的递减顺序进行拓扑排序是 DFS 时间戳的一个重要应用。对于有向无环图（DAG），如果我们按照完成时间从大到小排列节点，得到的序列就是一个合法的拓扑排序。这个性质成立的原因在于：如果存在一条从 u 到 v 的有向路径，那么 DFS 一定会在 u 完成之前先完成 v 的探索（因为 v 是 u 的后代或可到达的节点），因此 f[v] < f[u]。

# 基于完成时间的拓扑排序（单行实现）
def topological_sort_by_finish(graph, n):
    visited = [False] * n
    finish_stack = []

    def dfs(v):
        visited[v] = True
        for nb in graph[v]:
            if not visited[nb]:
                dfs(nb)
        finish_stack.append(v)  # 后续遍历记录

    for v in range(n):
        if not visited[v]:
            dfs(v)

    return finish_stack[::-1]  # 反转 = 完成时间递减

四、DFS 树与边的分类

在有向图或无向图上执行 DFS 时，遍历过程中实际走过的边构成了一个树形结构，称为 DFS 树（DFS Tree）或 DFS 森林（DFS Forest，当图不连通时）。在 DFS 树的基础上，图中的所有边可以被分为四类：树边、回边、前向边和横叉边。这种边的分类是理解图算法（如强连通分量 Tarjan 算法、桥与割点检测）的基础。

4.1 四类边的定义与识别

基于 DFS 时间戳，我们可以精确地区分这四类边：

边类型	定义	时间戳关系	有向图	无向图
树边 (Tree Edge)	DFS 遍历树中的边，连接父节点与子节点	d[u] < d[v] < f[v] < f[u]	存在	存在
回边 (Back Edge)	指向已在当前 DFS 路径上的祖先节点的边	d[v] < d[u] < f[u] < f[v]	存在	存在（会导致树边重复计数）
前向边 (Forward Edge)	指向非直接子节点的后代节点的边	d[u] < d[v] < f[v] < f[u]	存在	不存在（会被视为树边）
横叉边 (Cross Edge)	连接不同子树或不同 DFS 树的边	d[v] < f[v] < d[u] < f[u]	存在	不存在（会被视为回边）

4.2 边的分类在图算法中的作用

边的分类在多个经典图算法中扮演着关键角色：

环检测：在有向图中，当且仅当存在回边时，图中存在环。在无向图中，只要存在一条非树边（连接已访问节点），就意味着存在环。基于这个原理，我们可以在 O(V+E) 时间内完成环检测。
桥（Bridge）检测：桥是指删除后会使图不再连通的边。在无向图的 DFS 树中，一条树边 (u, v) 是桥当且仅当 v 的子树中没有回边能到达 u 或 u 的祖先。这一性质是 Tarjan 找桥算法的理论基础。
强连通分量（SCC）：Kosaraju 算法和 Tarjan 算法都依赖 DFS 和边的分类。特别地，Tarjan 算法通过维护每个节点的 low 值（通过子树中的回边和横叉边能到达的最早祖先的发现时间），在一次 DFS 遍历中即可计算出所有强连通分量。

# 基于 DFS 的桥检测（Tarjan 算法简化版）
def find_bridges(graph, n):
    visited = [False] * n
    d = [0] * n
    low = [0] * n
    timer = [0]
    bridges = []

    def dfs(v, parent):
        timer[0] += 1
        d[v] = low[v] = timer[0]
        visited[v] = True

        for nb in graph[v]:
            if nb == parent:
                continue
            if visited[nb]:
                # 回边，更新 low 值
                low[v] = min(low[v], d[nb])
            else:
                # 树边
                dfs(nb, v)
                low[v] = min(low[v], low[nb])
                # low[nb] > d[v] 说明子树没有回边越过 v
                if low[nb] > d[v]:
                    bridges.append((v, nb))

    for v in range(n):
        if not visited[v]:
            dfs(v, -1)

    return bridges

在桥检测算法中，low[v] 表示从节点 v 出发，通过 v 的子树中的任意条树边后最多再走一条回边能够到达的最早祖先的发现时间。如果 low[nb] > d[v]，说明 nb 的子树中没有任何回边能够到达 v 或 v 的祖先，因此边 (v, nb) 就是一座桥。这个算法是 DFS 时间戳和图论性质结合的经典范例。

五、DFS 的剪枝优化

纯粹的 DFS 是一种穷举搜索方法，其时间复杂度往往是指数级的。对于规模稍大的问题，穷举所有状态空间是不可行的。剪枝（Pruning）是在保证正确性的前提下，通过提前判断某些分支不可能产生有效解来减少搜索空间的技术。剪枝是 DFS 从理论走向实用的关键。

5.1 可行性剪枝

可行性剪枝（Feasibility Pruning）是最基本的剪枝方式：在搜索过程中，如果当前的部分解已经违反了问题的约束条件，那么无论后续如何扩展，都不可能得到一个合法解，因此可以立即停止这一分支的探索。

# 数独求解中的可行性剪枝
def solve_sudoku(board):
    def is_valid(board, row, col, num):
        # 检查行
        for j in range(9):
            if board[row][j] == num:
                return False
        # 检查列
        for i in range(9):
            if board[i][col] == num:
                return False
        # 检查 3x3 宫格
        box_row, box_col = (row // 3) * 3, (col // 3) * 3
        for i in range(3):
            for j in range(3):
                if board[box_row + i][box_col + j] == num:
                    return False
        return True

    def dfs(board):
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for num in map(str, range(1, 10)):
                        if is_valid(board, i, j, num):   # 可行性剪枝
                            board[i][j] = num
                            if dfs(board):
                                return True
                            board[i][j] = '.'
                    return False  # 所有数字都尝试失败
        return True  # 所有格子都已填满

    dfs(board)
    return board

在数独求解中，可行性剪枝体现在：当我们尝试在空格中填入数字时，只有在不违反行、列、宫格约束的情况下才继续搜索。这一简单的剪枝策略就能将搜索空间从 9^81 急剧缩小到可处理的范围。

5.2 最优性剪枝

最优性剪枝（Optimality Pruning）也称为"分支限界"，主要用于求解最优化问题。其核心思想是：维护当前已找到的最优解，如果在搜索过程中发现当前分支不可能比已知最优解更好，则提前终止该分支的搜索。最优性剪枝通常需要结合一个"乐观估计函数"（heuristic lower/upper bound）来实现。

# 旅行商问题（TSP）的最优性剪枝
def tsp_with_pruning(dist_matrix):
    n = len(dist_matrix)
    visited = [False] * n
    best_cost = [float('inf')]
    best_path = [None]

    # 启发式估计：当前路径的最小可能剩余代价
    def lower_bound(curr_cost, unvisited):
        # 简化估计：剩余未访问城市的最小入边之和
        remaining = sum(
            min(dist_matrix[v][u] for u in range(n) if u != v)
            for v in unvisited
        )
        return curr_cost + remaining

    def dfs(curr_city, count, cost, path):
        if count == n:  # 访问了所有城市
            total = cost + dist_matrix[curr_city][0]  # 回到起点
            if total < best_cost[0]:
                best_cost[0] = total
                best_path[0] = path[:]
            return

        unvisited = [i for i in range(n) if not visited[i]]
        if lower_bound(cost, unvisited) >= best_cost[0]:
            return  # 最优性剪枝：不可能比当前最优更好了

        for nxt in unvisited:
            visited[nxt] = True
            path.append(nxt)
            dfs(nxt, count + 1, cost + dist_matrix[curr_city][nxt], path)
            path.pop()
            visited[nxt] = False

    visited[0] = True
    dfs(0, 1, 0, [0])
    return best_cost[0], best_path[0]

5.3 重复状态剪枝

重复状态剪枝（Duplicate State Pruning）的核心思想是：如果在搜索过程中发现当前状态已经访问过，或者之前已经在更优的条件下访问过等价状态，则跳过当前分支。这种剪枝在有环图搜索和需要记录状态的问题中尤其重要。记忆化搜索（Memoization）可以看作是重复状态剪枝的一种特例——在递归过程中缓存已计算过的子问题结果。

# 重复状态剪枝示例：使用缓存避免重复计算
from functools import lru_cache

# 单词拆分问题：判断字符串能否由字典中的单词组成
def word_break(s, word_dict):
    word_set = set(word_dict)

    @lru_cache(maxsize=None)  # 自动重复状态剪枝
    def dfs(start):
        if start == len(s):
            return True

        for end in range(start + 1, len(s) + 1):
            if s[start:end] in word_set:
                if dfs(end):  # 如果已计算过 end，直接从缓存返回
                    return True

        return False

    return dfs(0)

在单词拆分问题中，如果不使用记忆化，朴素 DFS 的时间复杂度为 O(2^n)。通过 @lru_cache 自动缓存每个 start 位置对应的计算结果，当不同的拆分路径到达同一个 start 位置时，直接从缓存中读取结果而不再重复计算，从而将时间复杂度降低到 O(n^2)。这就是重复状态剪枝的威力。

剪枝策略对比总结：

可行性剪枝确保不越过约束边界，适用于所有约束满足问题；最优性剪枝利用上下界估计来剪掉不可能优于当前最优解的分支，适用于最优化问题；重复状态剪枝通过缓存已访问状态来避免重复搜索，适用于具有重叠子问题的场景。在实战中，这三种剪枝策略通常会配合使用，形成多层次的搜索优化体系。

六、DFS 在排列组合生成中的应用

排列组合的生成是回溯法最经典的应用领域之一。从 n 个元素中选取 k 个元素的所有排列或组合，都可以通过 DFS 遍历解空间树来系统地生成。这类问题的核心在于控制好"选择的范围"和"选择的顺序"。

6.1 全排列生成

全排列问题要求输出 n 个元素的所有可能排列方式。通过 DFS 回溯，我们逐位确定排列中的每个元素，并使用 used 数组标记哪些元素已经被选择过，从而避免重复使用同一元素。

# 全排列生成：输入 [1,2,3] 输出 [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
def permute(nums):
    n = len(nums)
    used = [False] * n
    result = []

    def dfs(path):
        if len(path) == n:
            result.append(path[:])  # 深拷贝当前排列
            return

        for i in range(n):
            if not used[i]:
                # 做选择
                used[i] = True
                path.append(nums[i])

                dfs(path)  # 递归确定下一个位置

                # 撤销选择
                path.pop()
                used[i] = False

    dfs([])
    return result

全排列的时间复杂度为 O(n * n!)，因为一共有 n! 个排列，而每个排列的复制需要 O(n) 时间。当 n 较小时（n <= 10），这个算法是可行的；当 n 超过 12 时，n! 会超过 4.7 亿，实际计算已经不可行。

6.2 子集生成

子集生成（也称为幂集）问题要求输出一个集合的所有子集。与排列不同，子集不关心元素的顺序。因此，在 DFS 过程中，我们通过控制搜索的起始位置来避免生成重复的子集（如 [1,2] 和 [2,1] 被视为同一子集）。

# 子集生成：输入 [1,2,3] 输出 [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
def subsets(nums):
    result = []

    def dfs(start, path):
        # 每个节点都是一种子集
        result.append(path[:])

        # 从 start 开始，避免重复
        for i in range(start, len(nums)):
            path.append(nums[i])
            dfs(i + 1, path)  # 下一层从 i+1 开始
            path.pop()

    dfs(0, [])
    return result

子集生成的时间复杂度为 O(n * 2^n)。与全排列不同，子集生成通过传递 start 参数来控制每层递归的选择范围。在第 k 层递归中，我们只能选择索引大于等于 start 的元素。这种方法保证了每个子集只被生成一次（按递增索引顺序），不需要 used 数组。实际上，子集生成就是所有 DFS 节点的完整遍历——根节点代表空集，每个节点都对应一个子集。

6.3 组合生成

组合生成问题要求从 n 个元素中选取 k 个元素的所有可能方式（C(n, k)）。与子集生成一样，组合也不关心元素顺序，因此同样使用 start 参数来控制选择范围。唯一的区别是，我们只在路径长度恰好为 k 时才记录结果。

# 组合生成：C(4,2) = [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
def combine(n, k):
    result = []

    def dfs(start, path):
        # 剪枝：剩余元素不够凑满 k 个
        if len(path) + (n - start + 1) < k:
            return

        if len(path) == k:
            result.append(path[:])
            return

        for i in range(start, n + 1):
            path.append(i)
            dfs(i + 1, path)
            path.pop()

    dfs(1, [])
    return result

组合问题的一个重要优化是剪枝。在示例中，我们添加了一个剪枝条件：如果当前路径长度加上剩余可选择元素的数量仍然小于 k，则提前终止搜索。例如在 C(4,2) 中，当 start=4 且 path=[] 时，剩余元素只有 [4] 一个，即使全部选上也无法凑满 2 个，因此可以直接剪掉。

排列 vs 组合 vs 子集核心区别：

排列（Permutations）使用 used 数组标记已选元素，每层递归遍历所有元素。组合（Combinations）使用 start 参数限制选择范围，只在路径长度为 k 时输出。子集（Subsets）使用 start 参数，所有节点都输出。掌握这三种模式的区别是解决回溯问题的关键。

七、DFS 在经典问题中的应用

DFS 和回溯算法在现实生活中有着广泛的应用，从路径规划到游戏 AI，从数独求解到八皇后问题。本节将深入分析几个经典问题的 DFS 解法，并探讨其中的优化技巧。

7.1 迷宫寻路问题

迷宫寻路是 DFS 最直观的应用场景之一。给定一个由通道和墙壁组成的二维网格，DFS 从起点出发，沿着一条路径探索，遇到死胡同则回溯，直到找到终点或遍历完所有可能的路径。

# 迷宫寻路：从左上角到右下角，1 表示通路，0 表示墙壁
def maze_solver(maze):
    if not maze or not maze[0]:
        return []

    rows, cols = len(maze), len(maze[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    path = []
    found = [False]

    def dfs(r, c):
        # 检查边界和障碍物
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if maze[r][c] != 1:  # 墙壁或已访问
            return

        # 到达终点
        if r == rows - 1 and c == cols - 1:
            path.append((r, c))
            found[0] = True
            return

        # 标记已访问（用 2 表示）
        maze[r][c] = 2
        path.append((r, c))

        # 向四个方向探索
        for dr, dc in directions:
            dfs(r + dr, c + dc)
            if found[0]:  # 找到路径即停止
                return

        # 回溯：恢复状态
        path.pop()
        maze[r][c] = 1  # 注意：有些场景不恢复墙壁，取决于需求

    dfs(0, 0)
    return path if found[0] else []

在迷宫问题中，DFS 寻路不一定找到最短路径（那是 BFS 擅长的事情），但它能够快速找到一条可行路径，特别是在迷宫很大但路径比较"深"的情况下。如果只需要找一条路径而非最短路，DFS 通常比 BFS 更快找到解。需要注意的是，DFS 在迷宫问题中的状态标记需要谨慎处理：标记已访问防止循环，但在某些需要枚举所有路径的场景下，回溯时需要恢复状态。

7.2 八皇后问题

八皇后问题是回溯算法的经典教科书案例。问题的要求是：在 8x8 的国际象棋棋盘上放置 8 个皇后，使得任意两个皇后都不在同一行、同一列或同一对角线上。这是一个典型的约束满足问题，DFS 回溯法是其标准解法。

# 八皇后问题（N皇后通用解法）
def solve_n_queens(n):
    cols = set()       # 已被占据的列
    diag1 = set()      # 主对角线：row - col 为定值
    diag2 = set()      # 副对角线：row + col 为定值
    result = []
    board = ['.' * n for _ in range(n)]

    def dfs(row):
        if row == n:  # 所有皇后都已放置
            result.append(board[:])
            return

        for col in range(n):
            d1 = row - col   # 主对角线检查
            d2 = row + col   # 副对角线检查

            if col in cols or d1 in diag1 or d2 in diag2:
                continue  # 可行性剪枝

            # 放置皇后
            cols.add(col)
            diag1.add(d1)
            diag2.add(d2)
            board[row] = board[row][:col] + 'Q' + board[row][col+1:]

            dfs(row + 1)  # 递归到下一行

            # 移除皇后（回溯）
            cols.remove(col)
            diag1.remove(d1)
            diag2.remove(d2)
            board[row] = '.' * n

    dfs(0)
    return result

# 测试：4 皇后有 2 个解，8 皇后有 92 个解
solutions = solve_n_queens(8)
print(f"8 皇后共有 {len(solutions)} 个解")

八皇后问题的巧妙之处在于对角线冲突的检测方法。主对角线（从左上到右下）上的所有格子满足 row - col 为常数，副对角线（从右上到左下）上的所有格子满足 row + col 为常数。利用这一性质，我们只需要三个集合（列集合、主对角线集合、副对角线集合）就能在 O(1) 时间内完成冲突检测。最终算法的时间复杂度为 O(N!)，但由于强大的剪枝能力，实际搜索空间远小于 N!。对于 8 皇后问题，92 个解可以在毫秒级内全部找到。

7.3 岛屿数量问题

岛屿数量（Number of Islands）是 LeetCode 上的经典问题，也是 DFS 在二维网格中的典型应用。给定一个由 '1'（陆地）和 '0'（水域）组成的二维网格，计算岛屿（相连的陆地组成的连通分量）的数量。DFS 在这里的作用是"淹没"整个岛屿——从一块陆地出发，将与之相连的所有陆地都标记为已访问。

# 岛屿数量：DFS 淹没法
def num_islands(grid):
    if not grid or not grid[0]:
        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:
            return
        if grid[r][c] != '1':
            return

        # 标记为已访问（"淹没"）
        grid[r][c] = '0'

        # 向四个方向递归
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)  # 淹没整个岛屿

    return count

岛屿数量问题的一个特点是：不需要显式的 visited 集合，也不需要回溯恢复状态。我们直接修改原始网格将 '1' 改为 '0'，这既是标记已访问的方式，也是"淹没"岛屿的语义表达。每个 DFS 调用会遍历一个岛屿的所有单元格，因此主循环中遇到 '1' 的次数就是岛屿的数量。时间复杂度为 O(rows * cols)，空间复杂度最坏 O(rows * cols)（递归栈深度）。

DFS 问题模式识别：在解决实际问题时，识别问题是否适合用 DFS 是一个关键技能。以下特征通常暗示 DFS 能发挥作用：问题需要枚举所有可能性（全排列、子集）、问题可以被建模为图或树的搜索（连通分量、路径查找）、问题需要在解空间树中做选择与撤销选择（数独、八皇后）、问题需要系统地遍历状态空间（组合优化、约束满足）。

八、DFS 与 BFS 的对比分析

深度优先搜索（DFS）和广度优先搜索（BFS）是两种最基本的图遍历策略。理解它们之间的区别与适用场景，是算法学习中的重要环节。

对比维度	DFS（深度优先搜索）	BFS（广度优先搜索）
数据结构	栈（递归本质也是函数调用栈）	队列
空间复杂度	O(h)，h 为树的深度	O(w)，w 为树的最大宽度
最优解	不保证找到最短路径	保证找到最短路径（无权图）
遍历顺序	沿一条路径走到黑，再回溯	按层逐层向外扩展
适合场景	排列组合、连通性、拓扑排序、环检测	最短路径、层级遍历、拓扑排序（Kahn算法）
实现难度	递归实现简洁，但需注意栈溢出	迭代实现直观，无栈溢出风险
回溯能力	天然支持（递归返回即回溯）	不支持回溯

选择建议：如果你需要找到最短路径（在无权图中），优先选择 BFS。如果你需要遍历所有可能的解（如排列组合、数独），或者的问题对深度更敏感而对广度不敏感，选择 DFS。另外，DFS 的空间效率通常更好（存储深度而非宽度），但在极端情况下（如链状图），DFS 的递归栈深度可能达到 O(V)，存在栈溢出风险。

九、总结与核心要点

深度优先搜索（DFS）是算法学习中最重要的基础算法之一，它不仅是图遍历的基本工具，更是回溯法、剪枝优化、以及许多高级算法（Tarjan、Kosaraju、拓扑排序）的基石。

DFS 核心要点速记：

1. 递归本质：DFS 利用函数调用栈的"深入-返回"机制，天然支持深度方向的系统探索。

2. 回溯模式："选择-探索-撤销"三段式结构是回溯法的标准范式，状态重置是必须牢记的关键操作。

3. 时间戳：发现时间与完成时间构成括号定理，是分析 DFS 树结构和边分类的理论基础。

4. 四类边：树边、回边、前向边、横叉边的区分是理解图算法（强连通分量、桥、割点）的前提。

5. 剪枝策略：可行性剪枝、最优性剪枝、重复状态剪枝是 DFS 从理论走向实用的三大法宝。

6. 三种模式：全排列用 used 数组、子集与组合用 start 参数，掌握这三种模式可解决绝大部分回溯问题。

复杂度总结

问题类型	时间复杂度	空间复杂度	说明
图遍历（邻接表）	O(V + E)	O(V)	V=顶点数, E=边数
全排列	O(n * n!)	O(n)	n 为元素个数
子集生成	O(n * 2^n)	O(n)	n 为集合大小
N 皇后	O(N!)	O(N)	实际远小于 N!（强剪枝）
数独求解	O(9^m)	O(m)	m 为空格数（剪枝后大幅减少）

实战建议

在实际面试和工程应用中，DFS 题目通常遵循以下解题步骤：第一步，判断问题是否属于"枚举所有可能性"或"在解空间中搜索"的类型；第二步，确定状态表示方式（路径、已选元素、当前位置等）；第三步，确定状态的转移方式（每一步可以有哪些选择）；第四步，确定剪枝条件（什么情况下可以提前终止）；第五步，编写回溯代码框架（选择-递归-撤销）。只要掌握这套方法论，绝大多数 DFS 相关题目都可以迎刃而解。

进阶学习方向：掌握了经典 DFS 之后，可以进一步学习迭代加深搜索（IDS，结合 DFS 的空间优势和 BFS 的最优性）、双向搜索（从起点和终点同时进行 DFS 或 BFS）、启发式搜索（A* 算法，在 DFS 框架中引入启发式评估函数）、以及蒙特卡洛树搜索（MCTS，在游戏 AI 中广泛使用的 DFS 变体）。