波仔
⌨️ 第四章 流程图与算法
📄 一句话概括

走迷宫的两种走法：广度优先（BFS）一圈一圈向外扩散（用队列，天然找【最短】）；深度优先（DFS）一条路走到黑、碰壁回头（用栈，省内存、找【所有解】）；剪枝＝走到一半发现【这条路注定白走】就提前回头——搜索的三件套。

📝 本节和前面几节的关系

3-17 的树是【场地】，本篇是【走法】。回收 3-16 的队列与栈——BFS 用队列、DFS 用栈，两种数据结构决定了两种走法，3-16 的伏笔在此兑现。

一、BFS：层层扩散，天然最短

从起点出发，先把所有一步能到的访问完，再访问两步能到的——像水面涟漪一圈圈扩：

from collections import deque

graph = {                       # 邻接表：谁连着谁
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def bfs(start, target):
    visited = {start}
    q = deque([(start, [start])])       # 队列装【节点 + 走过来的路径】
    while q:
        node, path = q.popleft()        # 先进先出——所以先访完近的
        if node == target:
            return path                 # 第一次命中 = 步数最少
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                q.append((nxt, path + [nxt]))

print(bfs("A", "F"))    # ['A', 'C', 'F'] —— 2 步，绕开 D/E 的长路

为什么 BFS 找最短：队列先进先出——【离起点 2 步的】一定在【3 步的】之前被访问，第一次撞见目标时路径必然最少。地图导航、社交网络【几度好友】、走迷宫最短路全是它。

二、DFS：一条道走到黑，回头再探

能深入就深入，走投无路退一步换条岔路——用栈（或递归，函数调用栈天然就是）：

def dfs(node, target, visited=None, path=None):
    if visited is None:
        visited, path = set(), []
    visited.add(node)
    path.append(node)
    if node == target:
        return path
    for nxt in graph[node]:
        if nxt not in visited:
            r = dfs(nxt, target, visited, path)   # 递归深入（栈就是调用栈）
            if r:
                return r
    return None

print(dfs("A", "F"))    # ['A', 'B', 'D', 'E', 'F'] —— 含回头走过的 D，不保证最短

性格：不保证最短（先深入哪条看运气）；内存省（只记当前一条路）；找【所有解】的主场——数独穷举、全排列、文件树遍历（4-7 递归的主战场）。

三、剪枝：注定白走就别走

搜索树大到爆炸时（O(2ⁿ) 级），走到一半就能判断【再走也没戏】——立刻回头，把整棵子树剪掉：

def subset_sum(nums, target, i=0, acc=0):
    if acc == target:
        return True
    if acc > target or i == len(nums):   # 剪枝：加超了 / 没数了 —— 整棵子树不走了
        return False
    return (subset_sum(nums, target, i + 1, acc + nums[i])      # 要第 i 个
            or subset_sum(nums, target, i + 1, acc))            # 不要

print(subset_sum([3, 34, 4, 12, 5, 2], 9))   # True（4+5）

两类常用剪枝：可行性剪枝（当前已超限——如 acc > target，继续只会更超）；重复剪枝（访问过的状态不再进——BFS 的 visited 就是它）。AI 对弈（alpha-beta 剪枝）、数独求解全靠它把天文数字的搜索树砍到能跑。

四、动手 Demo：两种走法的答案对比

# graph 沿用上文
print(bfs("A", "F"))    # ['A', 'C', 'F']      —— 最短 2 步
print(dfs("A", "F"))    # ['A', 'B', 'D', 'E', 'F'] —— 4 节点含回头（先深入 B 支路）

看到什么算成功：两条不同路径，BFS 的更短。

读结果：同图同目标，BFS 给最短路（队列的功劳）；DFS 的 path 记的是【走过的全部顺序】——D 是条死胡同但也在序列里（走到了才发现），找到的是【先撞见的那条】。要最短用 BFS、要全解用 DFS——口诀就这一句。

五、30 秒实验

把 graph 里 E 到 F 的连线删掉再跑 bfs("A", "F")——返回 ['A', 'C', 'F'] 不变；把 C 到 F 也删掉——返回 None（此路不通）。30 秒验证图结构一改、搜索立刻给出新答案——算法是通用发动机，图才是图纸。

六、常见误区

  1. 【BFS 和 DFS 只是遍历顺序不同，没本质区别】——错。队列 vs 栈的结构差异带来能力差异：BFS 天然最短路、DFS 天然省内存——数据结构决定算法能力（3-16 的中心思想）。
  2. 【BFS 一定比 DFS 慢】——分场景。找最近解 BFS 快（不用走深）；找【很深处】的解或枚举全部，DFS 少占内存还能配合剪枝——没有万能选手。
  3. 【visited 可加可不加】——图里有环时必须加：没 visited，A→B→A→B 永远转圈（BFS 死循环、DFS 爆栈）——树没环可省，图必须有。
自测三问（点开对答案） 1. **BFS 和 DFS 各用什么数据结构？各带来什么能力？** 答：BFS 用队列（先进先出）——近的先访问，天然最短路；DFS 用栈（后进先出，递归即调用栈）——一路到底，省内存、便枚举。 2. **为什么 BFS 第一次命中就是最短路径？** 答：队列保证按离起点的步数分层访问——2 步的节点全访完才轮到 3 步的，首次命中时步数必然最少。 3. **剪枝的原理是什么？举一类。** 答：搜索中途判断【该分支不可能出解】就整棵子树放弃——如子集和问题里当前和已超目标还继续加，可行性剪枝直接回头。

相关笔记