CC++ & Algorithm

DFS与BFS的比较——哪个更适合你？

困难4
语言版本：C++Python
概述：DFS空间小但可能绕远路，BFS保证最短路径但占用空间大，需要根据场景选择。

深度优先搜索 vs 广度优先搜索：到底该选谁？

在编程的世界里，我们经常需要在一堆数据中“找东西”。比如，从城市地图中找到一条从家到学校的路，或者在游戏地图中搜索隐藏宝物。深度优先搜索（DFS） 和 广度优先搜索（BFS） 就是两种最常用的“找东西”方法，它们就像两种不同的探险策略：一个喜欢死磕一条路走到黑，另一个喜欢一层一层稳稳推进。学会它们，你就能解决很多搜索问题，比如迷宫寻路、八皇后游戏、社交网络找朋友等。

本文会从多个角度对比这两种搜索，用生活里的例子帮你搞懂，最后给出完整的代码，并指出新手容易踩的坑。

1. 先认识两个家伙：DFS 和 BFS

DFS（深度优先搜索）：像走迷宫时，你选定一个岔路口就一直往深处走，直到撞墙（遇到死路或找到目标），然后退回上一个岔路口，换另一条路继续。它用栈（或者递归）来记住走过的路。
BFS（广度优先搜索）：像在操场找人，你从起点开始，先喊一声，让一圈人知道；再让他们分别喊下一圈。它用队列来记录“下一圈要喊谁”。

举个例子：你有一串钥匙掉在房间里，房间里有几个抽屉。

  • 用DFS：你打开第一个抽屉，如果里面还有小盒子，就继续打开小盒子，直到最里面，没找到再退回打开第二个抽屉。
  • 用BFS：先把所有抽屉都打开第一层，如果没有，再打开每个抽屉里的第二层……这样虽然同时打开很多抽屉，但能保证最早找到钥匙的房间（最短路径）。

2. 核心对比：四个关键点

2.1 空间占用——谁更省内存？

DFS 只需要记住当前这条路径上的节点（最多等于树或迷宫的最大深度）。比如迷宫有10层深，它只记录10个位置。想象你在图书馆找书，只拿一张纸记下你走过哪几排书架，非常省地方。
BFS 需要记住同一层的所有节点。最坏情况下，如果树的最后一层有半棵树那么多节点，它就要记下几百个甚至上万个。就像在操场上找朋友，你需要在脑子里记下今天操场上所有人，才能一层层传话。

生活例子：你的作业本有100页，每页有10道题。

  • 用DFS做题：你从第1页开始，一口气做到第100页，只记得当前页码和最后几道题的思路。
  • 用BFS做题：你先做所有页的第1题，再做所有页的第2题……你需要记住100页上每一题是否做完，记录量很大。

结论：如果你的电脑内存很小（比如旧手机），或者问题规模很大（比如超大的迷宫），DFS更友好。

2.2 时间效率——谁跑得快？

一般情况下，两者时间复杂度都是 O(N)，N 是节点总数（比如迷宫中的格子数）。但实际速度受目标位置和搜索顺序影响：

  • 目标在起点旁边：BFS 第一层就找到了，非常快；DFS 可能先往反方向深入很久才回来。
  • 目标在很深的地方：DFS 直冲深处，很快就碰到；BFS 必须一层层扩散，等它到深层可能已经花了很多时间。

例子：你要找的“宝藏”藏在迷宫最深处，DFS 像坐直线电梯，BFS 像爬楼梯绕远路。反过来，宝藏就在你脚边，BFS 弯腰就捡到，DFS 却先跑到楼下翻个底朝天。

注意：如果问题规模很大，但每次只求“是否存在解”，DFS 通常更快（因为它可能早退）；如果必须找最短路径，BFS 虽然到深层慢，但首次找到就是最短。

2.3 能否找到最短路径——谁是导航高手？

BFS 保证最短路径，因为它是一圈一圈向外扩散，第一次碰到目标时，走过的圈数（步数）一定是最少的。这就像你在地铁图上，从起点站开始，每换乘一次就是一圈，第一次到终点站时，转乘次数最少。
DFS 不保证最短，因为它可能先走一条很长的冤枉路。比如你从家去学校，DFS 可能先跑去外婆家再绕回来，虽然也能到，但路程多了一倍。

生活例子：你在一个网格地图上找朋友。

  • 用BFS：先找所有距离1步的格子，没有；再找距离2步的……第一次找到朋友时，步数肯定最小。
  • 用DFS：要是你一直往北走，哪怕朋友就在东边一步远，你也要走到北边尽头再回头，找到时可能已经走了10步。

关键：如果你只需要“有没有路”，选DFS；如果你要“最短的路”（无权图），选BFS。

2.4 实际应用——什么场景用谁？

  • DFS 强项：

    • 判断“是否存在一条路径”（比如迷宫有出口吗？）
    • 遍历所有节点（比如打印所有文件夹里的文件）
    • 回溯法解决棋盘问题（八皇后、数独、解谜游戏）
    • 拓扑排序、连通性检测
      为什么：DFS 递归代码短，容易实现，内存小。

  • BFS 强项：

    • 求无权图的最短路径（比如社交网络里你距离小明最近的朋友）
    • 层次遍历（比如按层打印二叉树）
    • 迷宫最短步数、地图导航
    • 同时搜索多个目标（比如雷达扫描）
      为什么：保证最短路径，且层数即步数。

总结口诀：

  • 找最短、找最近 → 用 BFS
  • 找存在、找全解 → 用 DFS
  • 要递归、省内存 → 用 DFS
  • 要精确、不怕大 → 用 BFS（注意队列不要撑爆内存）

3. 新手最容易犯的3个错误

❌ 错误1：忘记标记已访问节点 → 死循环

写DFS或BFS时，如果不记录哪些节点已经去过，就会原地打转。比如迷宫来回走同一个格子，永远找不到终点。

正确做法：用一个集合 visited 或二维数组来标记，访问过就不再重复。

❌ 错误2：BFS的队列用错了方向

用 pop() 而不是 popleft()，会把BFS变成DFS（深度优先）。队列必须先进先出，用 deque.popleft() 或列表的 pop(0)（但效率低）。

❌ 错误3：递归深度过大导致栈溢出

DFS 如果用递归实现，当树的深度超过 Python 默认递归深度（约1000）时，程序会崩溃。解决方法：改用手工栈（循环 + 列表）或者提高递归限制 sys.setrecursionlimit。

小贴士：如果问题规模大（比如10000层），优先用循环实现的DFS（手动栈）或BFS。

4. 完整可运行的代码示例（迷宫寻路）

下面我们用同一个迷宫来演示DFS和BFS。迷宫用二维列表表示，0是路，1是墙。起点(0,0)，终点(3,3)。

# 迷宫地图：0 = 路，1 = 墙
maze = [
    [0, 0, 1, 0],   # 第0行
    [0, 1, 0, 0],   # 第1行
    [0, 0, 0, 1],   # 第2行
    [0, 0, 0, 0]    # 第3行
]

# ---------- 1. DFS：找是否存在一条路径（不保证最短） ----------
def dfs_maze(x, y, target, visited):
    """
    递归深度优先搜索，返回 True 表示找到路径，False 表示没找到。
    x, y : 当前坐标
    target : 目标坐标 (tx, ty)
    visited : 已访问集合
    """
    # 检查是否越界
    if x < 0 or x >= 4 or y < 0 or y >= 4:
        return False
    # 检查是不是墙，或者已经访问过
    if maze[x][y] == 1 or (x, y) in visited:
        return False
    # 到达目标？
    if (x, y) == target:
        return True
    
    # 标记当前格子已访问
    visited.add((x, y))
    
    # 四个方向：下、上、右、左（顺序无所谓）
    for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
        next_x = x + dx
        next_y = y + dy
        if dfs_maze(next_x, next_y, target, visited):
            return True  # 只要一条路成功就返回
    
    # 所有方向都失败
    return False

# ---------- 2. BFS：找最短路径的步数 ----------
from collections import deque

def bfs_maze(start, target):
    """
    广度优先搜索，返回从 start 到 target 的最短步数，如果不可达返回 -1。
    start : 起点坐标 (sx, sy)
    target : 目标坐标 (tx, ty)
    """
    # 队列里的元素是 (x, y, 步数)
    queue = deque([(start[0], start[1], 0)])
    # 记录已访问节点
    visited = set([start])
    
    while queue:
        x, y, dist = queue.popleft()  # 取出最左边的元素（最早进来的）
        if (x, y) == target:
            return dist  # 第一次遇到目标，步数最小
        
        # 四个方向
        for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
            nx, ny = x + dx, y + dy
            # 检查是否在范围内、不是墙、未访问
            if 0 <= nx < 4 and 0 <= ny < 4 and maze[nx][ny] == 0 and (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append((nx, ny, dist + 1))
    
    return -1  # 所有格子都找完，没找到目标

# ---------- 主程序 ----------
start = (0, 0)
target = (3, 3)

print("DFS 是否存在路径:", dfs_maze(start[0], start[1], target, set()))
# 输出：DFS 是否存在路径: True

shortest = bfs_maze(start, target)
print("BFS 最短路径步数:", shortest)
# 输出：BFS 最短路径步数: 6

# 为了演示，我们可以手动走一条路径验证：起点(0,0) -> (0,1) -> (1,1)被墙挡住，所以换路。
# 实际上BFS找到了 (0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2)->(3,3) 共6步

代码说明：

  • DFS 函数返回 True/False，只告诉你能不能走到终点。
  • BFS 函数返回具体的步数，如果不可达返回 -1。
  • 你可以在自己的电脑上运行这段代码，看看结果。

5. 扩展一下：用树结构理解搜索过程

为了更直观，我们用一棵“决策树”来对比。假设你有三个好朋友：小A、小B、小C，每个朋友又认识两个人。你想找某个叫“小Z”的人。

  • DFS：先找小A，然后小A的朋友1，然后朋友1的朋友……直到找到小Z或走投无路，再退回来。
  • BFS：先找小A、小B、小C（第一层），如果他们都不认识小Z，再找小A的朋友、小B的朋友、小C的朋友（第二层）……

下图（文字版）表示一个简单树，根是“我”，第一层三个朋友，第二层每个朋友有两个朋友。

          我
       /  |  \
     A    B    C
    / \  / \  / \
   D  E F  G H  I

如果想找节点 H（C的朋友），DFS 可能先走 A→D→E 再退回走 B→F→G，最后才到 C→H，绕远路；BFS 第一层见到 A、B、C，其中 C 是 H 的朋友吗？不是，所以第二层见到 D、E、F、G、H、I，一下就找到 H（第二层）。而且 BFS 能告诉你：从“我”到 H 需要 2 步（我是第0层）。

6. 相关知识点指引

学会了DFS和BFS，你还可以继续学习：

  • 递归与回溯：DFS的递归实现是理解回溯法的基础，用来解决八皇后、数独、全排列等问题。
  • 图论基础：这两种搜索是图算法的基础，后面可以学Dijkstra（加权图最短路径）、拓扑排序、强连通分量等。
  • 队列与栈：BFS用队列，DFS用栈（或递归），掌握这两种数据结构是编程基本功。
  • 状态压缩：当搜索空间很大时，可以用位运算来优化 visited 标记。

最后送大家一句话：DFS 像探险家，BFS 像雷达兵。选对工具，事半功倍！

例题精讲

1单选题

在无权图中寻找从起点到终点的最短路径，以下哪种搜索算法更合适？

ADFS
BBFS
C两者一样
D都不合适
2单选题

以下关于DFS和BFS的描述，哪一项是正确的？

ADFS总是比BFS更快
BBFS通常使用递归实现
C在连通图中，两者都能遍历所有节点
DDFS使用队列作为辅助结构
3判断题

在时间复杂度上，DFS和BFS通常都是O(V+E)，其中V是顶点数，E是边数。

4判断题

当需要求解迷宫中的所有可能路径时，BFS比DFS更适合。

5填空题
请补全以下BFS遍历函数的代码，从队列中取出节点：
def bfs(graph, start):
    visited = set()
    queue = [start]
    visited.add(start)
    while queue:
        node = ___  # 从队列头部取出节点
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)