深度优先搜索（DFS）详解：原理、代码与复杂度

DFS 解决什么问题

DFS 回答“从这里出发能到达哪里？”：先把一个分支完整探索完，再尝试下一个。当路径的结构比长度更重要时，这种顺序很有用：在迷宫中找出路、判断图中是否有环、为相互依赖的任务排序，或列出谜题的所有解。

与广度优先搜索不同，DFS 不能求最短路径。它的优势在于内存中只需保存当前路径，并且能自然地记录每个节点何时进入、何时结束。

用大白话讲思路

1. 把当前节点标记为已访问。
2. 对每个尚未访问的邻居，走过去，并从那里重复第 1 步。
3. 当一个节点没有未访问的邻居时，它就处理完毕：退回到来时的节点。
4. 回到起点且起点也没有未访问的邻居时，搜索结束。

退回上一个节点称为回溯。使用递归时，调用栈会替你完成这一步。

逐步演示一个例子

使用与 BFS 文章相同的无向图：A–B、A–C、B–D、C–D、C–E、D–F。从 A 出发，邻居按字母顺序尝试。

访问顺序为 A、B、D、C、E、F，完成顺序为 E、C、F、D、B、A。拓扑排序和强连通分量算法用到的正是完成顺序。

Python 实现

递归版本最短，也最贴近算法思想：

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

用列表能让示例更易读，但 in 判断是 O(n)。处理大图时，请另外用一个 set 做成员判断。迭代版本使用显式栈，可避开 Python 的递归深度限制。邻居按逆序入栈，这样出栈顺序就与原顺序一致：

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)
    return order
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

注意与 BFS 的区别：这里节点是在出栈时才标记，所以同一节点可能多次出现在栈中。这对 DFS 是正确的，并能保持真正的深度优先顺序。

检测有向图中的环

DFS 的一个经典应用是给节点染色：白色（未见过）、灰色（在当前路径上）、黑色（已处理完）。一旦遇到灰色节点，就说明有一条边指回当前路径，也就是存在环。

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True              # back edge
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)
print(has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]}))  # True
print(has_cycle({"a": ["b"], "b": ["c"], "c": []}))     # False

时间与空间复杂度

变体与常见错误

• 先序与后序：在进入节点时记录（先序），或在节点处理完毕时记录（后序）。有向无环图的逆后序就是一个拓扑序。
• 连通分量：对每个仍未访问的节点重新发起一次 DFS，每次发起对应一个连通分量。
• 迭代加深 DFS：以深度限制 0、1、2…… 依次运行 DFS。它像 BFS 一样能找到最短路径，同时保持 DFS 的低内存占用。
• 网格上的洪水填充（即画图软件的油漆桶工具），就是在相同颜色的相邻格子上做 DFS 或 BFS。

其他常见错误：忘记使用已访问集合（遇到任何环都会无限循环）；使用 visited=[] 这样的可变默认参数（它会在多次调用间共享）；把无向图中指回父节点的边误当作环。

何时使用 DFS 及实际应用

• DFS 适用于可达性判断、环检测、拓扑排序、连通分量与强连通分量、桥与割点，以及配合回溯法的穷举搜索。
• 需要最少步数时改用 BFS；边带权时改用 Dijkstra 或 A*。
• 面试题：岛屿数量、克隆图、课程表（环检测）、二叉树路径总和、生成排列。
• 实际应用：构建系统和包管理器解析依赖顺序、编译器分析控制流、迷宫生成，以及遍历文件系统或 HTML 文档的树。