在一张图里找路时，有时并不关心最少经过几条边，而是想先沿一条可能的路径走下去；走不通时，再退回最近的分叉点换一条路。这个过程就是深度优先搜索（Depth-First Search，DFS）。
以这张有向图为例：
A
↙ ↘
B C
↙ ↘ ↘
D E F若邻居按从左到右的顺序处理，从 A 开始的 DFS 访问顺序是 A → B → D → E → C → F。它不会像 BFS 那样先访问完 B、C 这一层，而是先把 A → B → D 这条路走到底。
栈与递归为何会向深处走
DFS 依赖栈（Stack）的后进先出（LIFO）顺序。刚发现的节点会排在最前面处理，于是搜索不断延伸到最新发现的分支。
图用邻接表保存。递归调用本身也使用调用栈，因此下面的递归函数就是一种 DFS：
graph = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F"],
"D": [],
"E": [],
"F": [],
}
def dfs(graph, node, visited=None, order=None):
if visited is None:
visited = set()
if order is None:
order = []
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited, order)
return order
print(dfs(graph, "A"))
# ['A', 'B', 'D', 'E', 'C', 'F']递归调用栈不仅记住“当前在哪个节点”，还记住当前节点的邻居处理到了哪里。调用过程可以展开成：
| 动作 | 调用栈 | 接下来发生什么 |
|---|---|---|
| 进入 A | A | 先处理 A 的第一个邻居 B |
| 进入 B | A, B | 先处理 B 的第一个邻居 D |
| 进入 D | A, B, D | D 没有邻居，返回 B |
| 回到 B | A, B | 继续处理 B 的下一个邻居 E |
| 进入 E | A, B, E | E 没有邻居，返回 B，再返回 A |
| 回到 A | A | 继续处理 A 的下一个邻居 C |
| 进入 C、F | A, C, F | F 结束后逐层返回 |
D 结束后，程序没有重新从 A 开始，也没有忘记 B 处理到了哪里。调用栈把执行位置保留下来，所以返回 B 后会接着查看 E。
用显式栈实现
递归调用层数受运行时限制。图很深时，可以把调用栈换成自己维护的列表：
def dfs_iterative(graph, start):
stack = [start]
visited = {start}
order = []
while stack:
node = stack.pop()
order.append(node)
for neighbor in reversed(graph[node]):
if neighbor in visited:
continue
visited.add(neighbor)
stack.append(neighbor)
return order
print(dfs_iterative(graph, "A"))
# ['A', 'B', 'D', 'E', 'C', 'F']这里要从右向左把 B、C 压入栈：C 先压入、B 后压入，后进先出的栈会先弹出 B。若不使用 reversed，同一张图会得到 A → C → F → B → E → D；两种都是 DFS，只是分支的选择顺序不同。
显式栈版也在节点入栈时标记 visited。若等到弹出时才标记，在多条边汇合到同一节点的图中，同一个节点可能被重复压栈。弹出时再跳过重复项也能得到正确结果，但栈中会暂时保留多余记录。
递归版在进入节点时立即处理节点，属于前序（preorder）遍历。显式栈的写法也保留了这个顺序。若要在「所有邻居都处理完成后」再记录节点，需要把记录操作放到递归调用之后。在有向无环图中，DFS 拓扑排序会记录后序结果，再把结果反转；若图中可能有环，还要另外记录当前递归路径来检测环。
visited 与有环图
按父子方向遍历树时不会回到祖先，递归可以自然结束。一般的图可能存在环：
A → B → C
↑ ↓
└───────┘没有 visited 时，DFS 会不断执行 A → B → C → A。递归版在进入节点后标记，显式栈版在压入节点时标记，都是为了让每个节点至多展开一次。
从一个起点出发，只能访问沿边可以到达的部分。若要遍历无向图中的全部连通分量，需要对每个尚未访问的节点再启动一次 DFS：
def connected_components_undirected(graph):
visited = set()
components = []
for start in graph:
if start in visited:
continue
component = []
stack = [start]
visited.add(start)
while stack:
node = stack.pop()
component.append(node)
for neighbor in graph[node]:
if neighbor in visited:
continue
visited.add(neighbor)
stack.append(neighbor)
components.append(component)
return components对于无向图，每条边需要同时出现在两个端点的邻接表里。上面的每次外层循环发现一个未访问节点，就会完整访问它所在的连通分量（Connected Component）。
这段代码不能直接用来求有向图的强连通分量。对于有向图，从 A 能到 B，不代表从 B 也能回到 A；强连通分量要求分量内任意两点都能互相到达，需要 Tarjan、Kosaraju 等算法。
DFS 与回溯是什么关系
DFS 描述的是搜索顺序：先沿一个分支深入，无法继续时返回。回溯（Backtracking）是在这种搜索顺序上维护“当前选择”，返回时再撤销选择。
例如枚举从 A 到 F 的所有简单路径时，当前路径会随着递归变化：
def all_paths(graph, start, target):
paths = []
path = []
def search(node):
path.append(node)
if node == target:
paths.append(path.copy())
else:
for neighbor in graph[node]:
if neighbor not in path:
search(neighbor)
path.pop()
search(start)
return paths
print(all_paths(graph, "A", "F"))
# [['A', 'C', 'F']]path.append(node) 是做出选择，递归调用是沿当前分支深入，path.pop() 是返回时撤销选择。普通 DFS 遍历只需要永久记录 visited，不一定存在需要撤销的状态；因此 DFS 经常用来实现回溯，但两者不是同义词。
DFS 能解决什么
DFS 的访问顺序本身不保证最短路径；它适合需要沿路径深入、或需要在返回时收集信息的问题。
| 场景 | DFS 中的动作 |
|---|---|
| 判断两点是否可达 | 找到目标即停止 |
| 统计无向图连通分量 | 每次完整遍历一个尚未访问的区域 |
| 网格中的岛屿数量 | 从陆地格子出发，把相连陆地全部标记 |
| 枚举路径 | 进入节点时加入路径，返回时移除 |
| 拓扑排序 | 在 DAG 中记录后序，最后反转结果 |
| 检测有向图环 | 区分「已完成」和「当前递归路径上」的节点 |
「岛屿」问题可以把网格看作图：每个陆地格子是一个节点，上下左右相邻的陆地之间有边。一次 DFS 会淹没一整块相连陆地，外层扫描遇到下一块未访问陆地时，岛屿数加一。
与 BFS 的边界
| 维度 | DFS | BFS |
|---|---|---|
| 核心结构 | 栈或递归 | 队列 |
| 搜索顺序 | 先沿一条分支深入 | 按距离逐层扩展 |
| 无权图最短路径 | 不保证 | 第一次发现目标即为最少边数 |
| 内存形态 | 主要保存当前路径和待选分支 | 可能同时保存整层节点 |
| 常见问题 | 连通性、回溯、依赖顺序 | 层序遍历、最少步数、最短边数 |
在一棵很深但不宽的树中，递归 DFS 的调用栈主要是一条向下的路径；在一层拥有大量节点的图中，BFS 的队列会变大。不过一般图上的 DFS 仍需保存 visited，显式栈也可能积累多个待处理分支，所以整体空间复杂度最坏是 O(V)。递归版的调用深度最坏也是 O(V)，过深时可能超过语言运行时的递归限制。
两者在邻接表上的时间复杂度相同，都是 O(V + E)，其中 V 是节点数，E 是边数。这个复杂度依赖 visited 保证每个节点只展开一次；若问题要求枚举所有可能路径，路径数量可能远大于 V + E，不再是一次普通遍历的复杂度。
选择的依据是问题要保留的顺序：最少步数对应 BFS；需要走到底再返回、处理一个完整连通区域或收集后序结果时，对应 DFS。