深度优先搜索 DFS：回溯与剪枝

FreeGuideOnline 最新 2026-06-18

深度优先搜索 (DFS) 与回溯剪枝

深度优先搜索（Depth-First Search，DFS）是一种沿着树或图的纵深方向进行探索的算法。它毫不妥协地“一条路走到黑”，直到撞到无路可走的“死胡同”，才沿原路返回，寻找下一个出口。这种“不撞南墙不回头”的特性，恰好天然契合了回溯和剪枝两大优化策略，是解决组合、排列、棋盘、路径等复杂搜索问题的基石。

一、深度优先搜索：基础与实现

1.1 核心思想

DFS 的核心可以概括为三点：

  • 纵深优先：只要当前节点还有未访问的邻居，就继续深入。
  • 回溯：当当前节点的所有路径都已探索完毕或无法满足条件时，返回上一节点。
  • 状态标记：避免重复访问已处理节点（在图遍历中尤为重要，但在基于状态的搜索中，标记方式常变为“路径选择”）。

想象走迷宫：你总是选择最左边的一条路，边走边撒面包屑；走到尽头发现是死路，就沿着面包屑退回到上一个路口，选择下一个方向。这就是 DFS。

1.2 递归实现

递归天生适合 DFS，因为函数调用栈自动帮我们记录了回溯路径。

def dfs(node, visited):
    # 处理当前节点
    visited.add(node)
    
    # 对每一个邻接节点
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs(neighbor, visited)

对于二叉树的前序遍历，它本身就是一种 DFS：

def preorder(root):
    if not root:
        return
    print(root.val)          # 处理节点
    preorder(root.left)      # 纵深左子树
    preorder(root.right)     # 纵深右子树

1.3 迭代实现（显式栈）

当递归深度过深可能导致栈溢出或需要精细控制时，可以使用手动栈模拟。

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            # 将所有未访问邻居压栈（顺序可调整）
            for neighbor in reversed(node.neighbors):  
                if neighbor not in visited:
                    stack.append(neighbor)

二、回溯：聪明的“下一步”选择器

回溯是 DFS 在解决多步骤决策问题时的增强形式。问题的解可以看成一段决策序列，每一步有多个选择，决策树庞大。回溯的核心是：走不通就撤销，换一条路再试。

2.1 回溯算法框架

回溯问题通常遵循“路径、选择列表、结束条件”的模式：

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.append(路径的拷贝)
        return
    
    for 选择 in 选择列表:
        做出选择
        backtrack(路径, 新选择列表)
        撤销选择

以生成 [1,2,3] 的全排列为例，代码直观展示了回溯过程：

def permute(nums):
    res = []
    def backtrack(path, used):
        if len(path) == len(nums):   # 结束条件：已排满
            res.append(path[:])      # 存储路径拷贝
            return
        
        for i, num in enumerate(nums):
            if used[i]:              # 跳过已用元素
                continue
            # 做选择
            path.append(num)
            used[i] = True
            # 继续递归
            backtrack(path, used)
            # 撤销选择——回溯的关键步骤
            path.pop()
            used[i] = False
    
    backtrack([], [False] * len(nums))
    return res

2.2 回溯的三种典型问题

  1. 排列：顺序相关，选择需要标记元素使用情况。
  2. 组合：顺序无关，通过维护一个 start 索引来避免重复选择。 
    def combine(n, k):
    res = []
    def backtrack(start, path):
        if len(path) == k:
            res.append(path[:])
            return
        for i in range(start, n+1):
            path.append(i)
            backtrack(i+1, path)  # 下一层从 i+1 开始，保证不重复
            path.pop()
    backtrack(1, [])
    return res
  3. 子集：类似组合，但收集所有中间状态。

三、剪枝：砍掉不可能的枝桠

回溯穷举所有可能性，即使现代计算机也会在组合爆炸面前崩溃。剪枝就是在决策树的分叉口提前判断：“这条路走下去绝不会得到有效解”，从而跳过该分支。

3.1 可行性剪枝

判断当前选择能否导向一个可行解。若不能，立即停止向下搜索。

示例：组合总和 II（给定数组，每个数字只能使用一次，不允许重复组合）

def combinationSum2(candidates, target):
    candidates.sort()    # 排序是剪枝预处理
    res = []
    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            # 剪枝1：当前数字大于剩余目标，且数组升序，后面更大，直接break
            if candidates[i] > remain:
                break
            # 剪枝2：跳过同一层重复的数字（避免重复组合）
            if i > start and candidates[i] == candidates[i-1]:
                continue
            path.append(candidates[i])
            backtrack(i+1, path, remain - candidates[i])
            path.pop()
    backtrack(0, [], target)
    return res

这里两重剪枝：

  • 大小剪枝：candidates[i] > remain 时，因为排序，后续所有数都更大，整层提前终止。
  • 同层去重剪枝：遇到与前一个元素相等的值，且前一个未选中，说明会重复产生相同组合，跳过。

3.2 最优化剪枝

当问题要求找“最短”、“最长”、“最小代价”等最优解时，可以维护一个全局最优值。若当前路径的代价已经劣于最优值，后续探索毫无意义。

示例：N 皇后改版 —— 最小代价放置

def min_cost_nqueens(n, cost_matrix):
    min_cost = float('inf')
    # cols, diag1, diag2 用于快速检查冲突（可行性剪枝）
    def backtrack(row, current_cost, cols, diag1, diag2):
        nonlocal min_cost
        if row == n:
            min_cost = min(min_cost, current_cost)
            return
        # 最优化剪枝：若当前代价已 >= min_cost，停下
        if current_cost >= min_cost:
            return
        for col in range(n):
            if col in cols or (row-col) in diag1 or (row+col) in diag2:
                continue
            # 做选择
            backtrack(row+1, current_cost + cost_matrix[row][col],
                      cols | {col}, diag1 | {row-col}, diag2 | {row+col})
    backtrack(0, 0, set(), set(), set())
    return min_cost

3.3 对称与顺序剪枝

  • 对称性剪枝：在棋盘或图形问题中，利用对称性减少搜索空间（如 N 皇后可固定第一行皇后在某半区）。
  • 顺序剪枝：在组合问题中强制升序选择，消灭排列带来的冗余（如上文组合问题的 start 参数即可视为一种剪枝）。

四、实战：回溯 + 剪枝解经典问题

4.1 数独求解

数独是约束传播与回溯的完美结合。我们通过三个集合（行、列、宫）快速判断数字是否可行（可行性剪枝），并优先从候选数最少的空格开始填充（一种启发式剪枝）。

def solveSudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empty_cells = []
    
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                num = board[i][j]
                rows[i].add(num)
                cols[j].add(num)
                boxes[(i//3)*3 + j//3].add(num)
            else:
                empty_cells.append((i, j))
    
    def backtrack(index):
        if index == len(empty_cells):
            return True   # 全部填完
        
        i, j = empty_cells[index]
        box_id = (i//3)*3 + j//3
        
        for num in map(str, range(1, 10)):
            if num not in rows[i] and num not in cols[j] and num not in boxes[box_id]:
                # 做选择
                board[i][j] = num
                rows[i].add(num); cols[j].add(num); boxes[box_id].add(num)
                
                if backtrack(index+1):
                    return True
                
                # 撤销选择
                board[i][j] = '.'
                rows[i].remove(num); cols[j].remove(num); boxes[box_id].remove(num)
        return False
    
    backtrack(0)

4.2 单词搜索（二维网格 DFS）

给定 m×n 字母网格，查找单词是否存在。每个字母只能用一次。这也是一种带剪枝的回溯：边界剪枝、已访问标记、以及当前字符不匹配时立即回溯。

def exist(board, word):
    rows, cols = len(board), len(board[0])
    
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if r<0 or r>=rows or c<0 or c>=cols or board[r][c] != word[idx]:
            return False
        
        # 标记并深入
        temp, board[r][c] = board[r][c], '#'
        found = (dfs(r+1, c, idx+1) or
                 dfs(r-1, c, idx+1) or
                 dfs(r, c+1, idx+1) or
                 dfs(r, c-1, idx+1))
        # 回溯恢复
        board[r][c] = temp
        return found
    
    for i in range(rows):
        for j in range(cols):
            if dfs(i, j, 0):
                return True
    return False