DFS可视化工具在线

伪代码

DFS 通常写成递归形式，但迭代写法把栈显式化，可避免在深图上撑爆调用栈。两者产生相同的发现顺序。

DFS(图, 源点):
    时间 = 0
    访问(源点)

访问(u):
    已访问.加入(u)
    disc[u] = ++时间          // 发现时间
    对 u 的每个邻居 v:
        若 v 不在已访问中:
            父结点[v] = u
            访问(v)
    fin[u] = ++时间           // 完成时间

发现时间与完成时间才是 DFS 真正的产物。后代的区间 [disc[u], fin[u]] 严格嵌套在其祖先的区间之内，而这种嵌套性正是拓扑排序、环检测、Tarjan 强连通分量、割点与桥的共同基础。

分步示例演算

从 A 出发在可视化工具默认加载的图上运行 DFS，邻居始终按字母顺序选取。

示例图: 无向边 A-B (2)、A-C (3)、B-C (1) 和 C-D (4)。DFS 忽略权重。

1. 访问 A. disc[A] = 1。第一个未访问的邻居是 B，于是立即递归下去，而不是接着看 C。
2. 访问 B. disc[B] = 2。邻居是 A，它是父结点被跳过，以及未访问的 C。递归进入 C。
3. 访问 C. disc[C] = 3。邻居是 A、B 和 D。A 已访问且不是父结点，因此 A-C 是一条回边，证明存在环。B 是父结点。D 未访问，于是递归进入 D。
4. 访问 D. disc[D] = 4。它唯一的邻居是父结点 C。无事可做，因此 fin[D] = 5。
5. 回溯. 控制返回 C，它已无剩余邻居，因此 fin[C] = 6。随后 B 在 7 完成，A 的剩余邻居 C 此时已访问，于是在 8 完成。

遍历顺序是 A、B、C、D。BFS 恰好也以同样顺序访问这四个结点，但生成的树不同：BFS 得到扁平的树 A 到 B、A 到 C、C 到 D，而 DFS 得到单链 A 到 B 到 C 到 D。回边 C 到 A 标出了环 A-B-C-A，嵌套区间 A[1,8]、B[2,7]、C[3,6]、D[4,5] 直接反映了递归深度。

复杂度及其来源

时间: O(V + E) · 空间: O(V)

每个结点恰好被访问一次，因为已访问检查守住了递归调用；每条边从两个端点各被检查一次，无向图中共 2E 次，有向图中为 E 次。空间是已访问集合加递归栈，均为 O(V)。递归深度等于最长简单路径的长度，因此在一条百万结点的链上，大多数语言中递归实现都会撑爆调用栈，此时必须改用显式栈的写法。

何时使用深度优先搜索，何时不宜

问题关乎结构时选 DFS，关乎距离时选 BFS。

常见陷阱

• 在深图上栈溢出. 递归 DFS 在一条路径上每个结点递归一次。视语言不同，大约在一万到十万个结点时调用栈就会崩溃。请改为显式栈，或在语言允许时有意识地调高递归上限。
• 把通往父结点的边当作回边. 无向图中每条边都从两端出现，因此回到父结点的那条边总是看起来像回边。请显式跳过父结点；同时注意存在平行边时只能跳过一次。
• 用已访问集合检测有向图中的环. 在有向图中遇到已访问结点并不意味着存在环，它可能是通往已完成子树的横叉边。你需要三种颜色：未访问、位于当前递归栈中、已完成。只有指向递归栈的边才闭合一个环。
• 以为遍历顺序唯一. DFS 的输出取决于邻居的迭代顺序。两个都正确的实现可能给出不同的合法顺序，因此测试应当验证性质而不是某个确切序列。

常见问题

深度优先搜索有什么用？

DFS 是拓扑排序、环检测、强连通分量、割点、桥以及迷宫生成的基础。在工程实践中，它支撑构建工具与包管理器的依赖解析、死锁检测，以及各类回溯求解器。

DFS 的时间复杂度是多少？

使用邻接表时为 O(V + E) 时间和 O(V) 空间。每个结点访问一次，每条边从两个端点各检查一次。空间是已访问集合加递归栈，栈深等于图中最长的简单路径。

DFS 是递归的还是迭代的？

两者皆可。递归写法更短，并且自然地给出发现时间与完成时间。迭代写法使用显式栈，在图深到足以撑爆调用栈时是必需的，也就是数万个结点串成一条链的情形。

DFS 如何检测环？

在无向图中，指向一个已访问且不是当前结点父结点的边就闭合了一个环。在有向图中必须记录哪些结点位于当前递归栈内，因为只有回到栈中的边才是真正的回边。指向已完成结点的边是横叉边或前向边，什么也证明不了。

为什么 DFS 比 BFS 省内存？

DFS 只保存从根到当前结点的这条路径，内存与深度成正比。BFS 要保存整层前沿，在宽图上这可能占全部结点的很大一部分。在深而窄的图上情况相反，BFS 反而更轻。