搜索算法 (BFS & DFS)

搜索是图论和树中最核心的操作。主要分为 广度优先搜索 (BFS) 和 深度优先搜索 (DFS)。

从数据结构角度看：

• BFS 依赖 队列 (Queue)。
• DFS 依赖 栈 (Stack) (或递归调用栈)。

1. 广度优先搜索 (BFS)

策略：层层推进，像水波纹一样扩散。

适用场景：

• 寻找最短路径 (在无权图中)。
• 层序遍历。

代码模板 (二叉树层序遍历)

from collections import deque

def bfs(root):
    if not root: return []

    result = []
    queue = deque([root])  # 初始化队列

    while queue:
        level_size = len(queue)
        current_level = []

        for _ in range(level_size):
            node = queue.popleft() # 出队
            current_level.append(node.val)

            # 将邻居加入队列
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)

        result.append(current_level)
    return result

2. 深度优先搜索 (DFS)

策略：不撞南墙不回头。一条路走到黑，只有无路可走时才回退验证其他路径。

适用场景：

• 寻找所有路径。
• 排列组合问题 (回溯法)。
• 连通性检测。

代码模板 (递归版)

def dfs(node, visited):
    if not node or node in visited:
        return

    visited.add(node)
    print(node.val) # 处理当前节点

    for neighbor in node.neighbors:
        dfs(neighbor, visited)

3. 回溯算法 (Backtracking)

回溯是 DFS 的一种应用，常用于解决排列、组合、子集问题。它的核心在于做选择 -> 递归 -> 撤销选择。

示例：全排列

给定 [1, 2, 3]，求全排列。

def permute(nums):
    result = []

    def backtrack(path, used):
        # Base Case: 路径长度等于 nums 长度
        if len(path) == len(nums):
            result.append(path[:]) # 必须拷贝一份
            return

        for num in nums:
            if num in used:
                continue

            # 1. 做选择
            path.append(num)
            used.add(num)

            # 2. 进入下一层
            backtrack(path, used)

            # 3. 撤销选择 (回溯)
            path.pop()
            used.remove(num)

    backtrack([], set())
    return result

print(permute([1, 2, 3]))

本章小结

算法	数据结构	特征	常见应用
BFS	队列	层层扩散	最短路径、最近距离
DFS	栈/递归	深度深入	所有路径、连通分量

• 遇到“最短”、“最少步数”字眼，优先想 BFS。
• 遇到“所有可能”、“组合”字眼，优先想 DFS/回溯。

---

下一章：图论基础