深度优先搜索(DFS)

DFS 用递归或显式栈沿一条路径深入,再回退探索其他分支。常规图遍历访问每个节点和边一次,邻接表下为 O(V+E)。

一句话定义

DFS 用递归或显式栈沿一条路径深入,再回退探索其他分支。常规图遍历访问每个节点和边一次,邻接表下为 O(V+E)。

为什么重要

  • 环检测、拓扑排序、连通分量、岛屿计数等图问题的基础。
  • 回溯(backtracking):全排列、组合、数独、N 皇后本质是对“决策树”做 DFS。
  • 树的前序/中序/后序遍历都是 DFS(见 k2.ds.tree)。

使用边界

枚举全排列等回溯是在更大的决策树上做 DFS,不能沿用原图遍历的线性结论。有向图三色判环与无向图排除父边的规则也不同。

原理 / 图解

示例图:A→B、A→C、B→D、C→D、C→E、D→F。

图 1

访问顺序 A → B → D → F(到底)→ 回退到 A → C → E(D 已访问,跳过)。

三色标记法判环(有向图):白=未访问、灰=正在访问(在当前路径上)、黑=已完成。DFS 中遇到灰色节点,说明找到了一条回到当前路径的边,即存在环。

BFS DFS
数据结构 队列 栈 / 递归
访问顺序 按层 一条路到底
无权最短路 能 不能保证
内存 宽图时大 深图时大(递归深)
典型用途 最短路、按层扩展 判环、拓扑、回溯、连通性

可运行示例

递归与显式栈两种 DFS、三色判环、网格岛屿计数、回溯生成全排列(Python 3.15.0 一稿运行记录):

# 文件:examples/23_dfs.py
# 深度优先搜索 DFS:一条路走到底再回溯(递归 / 栈)。用于连通性、环检测、回溯搜索
import sys
sys.setrecursionlimit(10_000)

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D", "E"], "D": ["F"], "E": [], "F": []}
order = []
def dfs(u, seen=None):
    seen = seen if seen is not None else set()
    seen.add(u); order.append(u)
    for v in graph[u]:
        if v not in seen: dfs(v, seen)
dfs("A"); print("递归 DFS 访问顺序:", order)

def dfs_iter(start):
    seen, stack, out = set(), [start], []
    while stack:
        u = stack.pop()
        if u in seen: continue
        seen.add(u); out.append(u)
        stack.extend(reversed(graph[u]))      # 逆序压栈,保持与递归版相同的顺序
    return out
print("显式栈 DFS 访问顺序:", dfs_iter("A"))

# 有向图环检测(三色标记):依赖是否循环?
def has_cycle(g):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {u: WHITE for u in g}
    def visit(u):
        color[u] = GRAY
        for v in g[u]:
            if color[v] == GRAY or (color[v] == WHITE and visit(v)): return True
        color[u] = BLACK; return False
    return any(color[u] == WHITE and visit(u) for u in g)
print("graph 有环:", has_cycle(graph), "| 加一条 F->A 后有环:", has_cycle({**graph, "F": ["A"]}))

# 岛屿数量(连通分量)
sea = ["11000", "11010", "00100", "00011"]
seen = set()
def flood(r, c):
    if not (0 <= r < len(sea) and 0 <= c < len(sea[0])) or sea[r][c] == "0" or (r, c) in seen: return
    seen.add((r, c)); [flood(r+dr, c+dc) for dr, dc in ((1,0),(-1,0),(0,1),(0,-1))]
islands = 0
for r in range(len(sea)):
    for c in range(len(sea[0])):
        if sea[r][c] == "1" and (r, c) not in seen: flood(r, c); islands += 1
print("岛屿数量:", islands)

# 回溯:全排列(DFS 的典型应用)
def permutations(items, path=()):
    if not items: yield path; return
    for i, x in enumerate(items): yield from permutations(items[:i] + items[i+1:], path + (x,))
print("abc 全排列:", ["".join(p) for p in permutations("abc")])

一稿留存输出:

递归 DFS 访问顺序: ['A', 'B', 'D', 'F', 'C', 'E']
显式栈 DFS 访问顺序: ['A', 'B', 'D', 'F', 'C', 'E']
graph 有环: False | 加一条 F->A 后有环: True
岛屿数量: 4
abc 全排列: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

两种实现的访问顺序一致(显式栈版需把邻居逆序压栈);加一条 F→A 后三色法检测出环。

常见误区

  • 深图用递归:节点链很长时触发 RecursionError(见 k2.ds.stack),改用显式栈。
  • 回溯忘记“撤销选择”:递归返回后要把状态恢复,否则结果互相污染。
  • 无向图判环用三色法:无向图里父节点会被误判为环,要排除来时的边或用并查集。
  • 以为 DFS 能找最短路径:DFS 找到的第一条路径不一定最短。

与 AI 开发的关系

  • 计算图的拓扑序:反向传播需要按拓扑逆序遍历计算图,常用 DFS 后序实现(见 k2.ds.graph)。
  • 代码与文档的递归处理:遍历 AST、目录树、嵌套 JSON。
  • 搜索式推理:思维树(Tree of Thoughts)可以用 BFS 或 DFS 策略探索推理分支。https://arxiv.org/abs/2305.10601
  • 约束求解与规划:带剪枝的回溯是 Agent 规划、排班等问题的基础解法。

延伸阅读

理解检查

用 DFS 枚举 n 个元素的全排列,是否仍是 O(n)?

参考答案:不是。完整输出就有 n! 个排列,每个排列还需要记录 n 个元素。

核验与复现

核验日期:2026-10-14。示例状态:运行通过。本轮日志:23_dfs.py。

配套代码与核验资料

继续浏览基础 返回知识 →返回顶部 ↑
本篇目录
教程图解100%
教程图解