深度优先搜索

Views: --

深度优先搜索（DFS）沿一条尚未探索的边不断深入；无路可走时回退到最近的分叉点。递归调用栈天然记录这条尚未完成的路径。

1. 三种颜色

  • 白色：尚未发现；
  • 灰色：已经发现，但其邻接边还没全部处理完，仍在递归栈中；
  • 黑色：已经完成。
DFS(G):
    for each vertex u:
        color[u] = WHITE
        parent[u] = NIL
    for each vertex u:
        if color[u] == WHITE:
            DFSVisit(u)

DFSVisit(u):
    color[u] = GRAY
    discover[u] = ++time
    for each v in Adj[u]:
        if color[v] == WHITE:
            parent[v] = u
            DFSVisit(v)
    color[u] = BLACK
    finish[u] = ++time

外层循环不能省略，否则非连通图中只会得到一个可达分量。

2. 深度优先森林

每条把白色顶点首次发现的边都是树边。一次 DFS 可能从多个根启动，因此父指针整体构成深度优先森林，而不一定是一棵树。

DFS 的具体森林依赖起点顺序和邻接表顺序；但许多结构结论不依赖这个偶然顺序。

3. 时间戳与括号定理

每个顶点有发现时间 d[u]d[u] 与完成时间 f[u]f[u]。DFS 的递归区间

[d[u],f[u]][d[u],f[u]]

对任意两个顶点只有两种关系：完全分离，或一个完整包含另一个。不会交叉。这叫括号定理。

vv 是 uu 在 DFS 森林中的后代，当且仅当

d[u]<d[v]<f[v]<f[u].d[u]<d[v]<f[v]<f[u].

4. 无向图中的边

无向图 DFS 中：

  • 指向白色顶点的是树边；
  • 非树边连接祖先与后代，称后向边。

实现时同一条无向边会从两端看到。遇到灰色邻居时，若它正是 parent[u]，只是树边的反向记录，不应误判为额外环边；平行边场景还要按边编号区分。

5. 无向图判环

从 uu 遍历到已访问邻居 vv，且 v≠parent[u]v\ne parent[u]，说明存在环。对每个连通分量执行即可。

这个规则不能原样用于有向图。有向图必须依赖灰色结点或时间戳识别后向边。

6. 复杂度

使用邻接表时，每个顶点进入和退出一次，每条边检查常数次：

T=O(V+E),S=O(V).T=O(V+E),\qquad S=O(V).

空间包括颜色、父指针、时间戳和最深可达 O(V)O(V) 的递归栈。图很深时，语言运行时可能栈溢出，可改用显式栈模拟。

7. BFS 与 DFS 如何选择

目标更自然的方法
无权最短路、按层扩散BFS
拓扑排序、强连通分量、环和递归结构DFS
只判断可达性二者都可

二者复杂度都可达 O(V+E)O(V+E)，差异不只是“快慢”，而是遍历顺序暴露出的结构不同。

8. DFS 是许多算法的骨架

拓扑排序利用完成时间；强连通分量利用转置图与完成顺序；割点、桥和双连通分量利用 DFS 树上的回边信息。学会维护“进入、深入、回退、完成”的状态，比背单个题目的代码更重要。

评论