在一张图里找路时，有时并不关心最少经过几条边，而是想先沿一条可能的路径走下去；走不通时，再退回最近的分叉点换一条路。这个过程就是深度优先搜索（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 → B → D
↑
返回 B → E
↑
返回 A → C → FD 没有未访问的邻居，函数就结束并返回到处理 B 的那一层；B 的下一个邻居 E 随后被处理。这个从深处返回分叉点、继续尝试另一条边的过程叫回溯（backtracking）。
用显式栈实现
递归调用层数受运行时限制。图很深时，可以把调用栈换成自己维护的列表：
def dfs_iterative(graph, start):
stack = [start]
visited = set()
order = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
for neighbor in reversed(graph[node]):
if neighbor not in visited:
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，只是相同深度的邻居选择顺序不同。
递归版在进入节点时立即处理节点，属于前序（preorder）遍历。显式栈的写法也保留了这个顺序。若要在「所有邻居都处理完成后」再记录节点，需要把记录操作放到递归调用之后；拓扑排序常使用这种后序（postorder）时机。
visited 与有环图
树从根向下没有环，递归可以只靠终止条件结束。图可能存在环：
A → B → C
↑ ↓
└───────┘没有 visited 时，DFS 会不断执行 A → B → C → A。递归版在进入节点后马上标记，显式栈版在弹出节点后检查和标记，都是为了让每个节点至多展开一次。
从一个起点出发只能访问到它所在的连通部分。若要遍历图中的全部节点，需要对每个尚未访问的节点再启动一次 DFS：
def connected_components(graph):
visited = set()
components = []
for start in graph:
if start in visited:
continue
component = []
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
component.append(node)
stack.extend(graph[node])
components.append(component)
return components对于无向图，每条边需要同时出现在两个端点的邻接表里。上面的每次外层循环发现一个未访问节点，就得到一个连通分量（connected component）。
DFS 能解决什么
DFS 的访问顺序本身不保证最短路径；它适合需要沿路径深入、或需要在返回时收集信息的问题。
| 场景 | DFS 中的动作 |
|---|---|
| 判断两点是否可达 | 找到目标即停止 |
| 统计连通分量 | 每次完整遍历一个尚未访问的区域 |
| 网格中的岛屿数量 | 从陆地格子出发，把相连陆地全部标记 |
| 枚举路径 | 进入节点时加入路径，回溯时移除 |
| 拓扑排序 | 所有后继处理完后，再记录当前节点 |
| 检测有向图环 | 区分「已完成」和「当前递归路径上」的节点 |
「岛屿」问题可以把网格看作图：每个陆地格子是一个节点，上下左右相邻的陆地之间有边。一次 DFS 会淹没一整块相连陆地，外层扫描遇到下一块未访问陆地时，岛屿数加一。
与 BFS 的边界
| 维度 | DFS | BFS |
|---|---|---|
| 核心结构 | 栈或递归 | 队列 |
| 搜索顺序 | 先沿一条分支深入 | 按距离逐层扩展 |
| 无权图最短路径 | 不保证 | 第一次发现目标即为最少边数 |
| 内存形态 | 主要保存当前路径和待选分支 | 可能同时保存整层节点 |
| 常见问题 | 连通性、回溯、依赖顺序 | 层序遍历、最少步数、最短边数 |
在一棵很深但不宽的树中，DFS 通常只保留一条向下的路径；在一层拥有大量节点的图中，BFS 的队列会变大。两者在邻接表上的时间复杂度相同，都是 O(V + E)，其中 V 是节点数，E 是边数。
选择的依据是问题要保留的顺序：最少步数对应 BFS；需要走到底再返回、处理一个完整连通区域或收集后序结果时，对应 DFS。