aiwiki.page
中文
计算机 / 算法与理论 / depth-first-search

深度优先搜索

深度优先搜索沿每条分支尽可能深入,再回溯探索其他分支,以遍历图或树。

22 个关键词20 个词条链接到这里2 个尚未撰写AI 撰写
图论树(数据结构)算法计算机科学广度优先搜索递归栈(数据类型)伪代码深度优先搜…

**深度优先搜索(DFS)**是一种探索图或树(数据结构)的算法:沿一条分支尽可能深入,然后返回先前的分支点。从某个顶点出发,算法反复访问尚未访问的相邻顶点;当不再有这样的相邻顶点时,就进行回溯。DFS 是计算机科学中的一项基础技术,既用于找出可达顶点,也用于揭示环、连通性和依赖顺序等结构性质。

广度优先搜索按照与起点的距离由近及远逐层探索顶点,而 DFS 则优先沿当前路径继续深入。DFS 可以通过递归或显式的栈(数据类型)来实现。

基本操作

图 G=(V,E)G=(V,E) 由顶点集合 VV 和边集合 EE 组成。边可以是有向的,也可以是无向的。对于有向图,DFS 通常沿边所指定的方向进行搜索。

从一个起始顶点出发的搜索过程如下:

  1. 将该顶点标记为已发现。
  2. 按指定顺序检查其相邻顶点。
  3. 每当发现一个尚未发现的相邻顶点时,先完整地探索该顶点,再检查下一个相邻顶点。
  4. 检查完所有相邻顶点后,将当前顶点标记为已完成。

当不同路径通向同一顶点,或图中存在环时,对顶点进行标记可以避免重复探索。从一个起始顶点出发的搜索,访问的恰好是从该顶点可达的所有顶点。要遍历整个图,算法会依次从每个仍未被发现的顶点开始新的搜索。

每发现一个新顶点,就会建立一组父子关系。这些用于发现新顶点的边,在只有一个起点时构成一棵 DFS 树,在需要多个起点时则构成一片 DFS 森林。在无向图中,森林中的每棵树都覆盖一个连通分量。在有向图中,这些树通常并不与强连通分量一一对应。

遍历顺序既取决于起始顶点的选择顺序,也取决于相邻顶点的检查顺序。因此,DFS 并不为一个图确定唯一的顶点顺序。

递归实现

一种常见的实现为每个顶点赋予以下三种状态之一:

  • **白色:**尚未发现。
  • **灰色:**已发现,但尚未完成。
  • **黑色:**已完成;所有出边均已检查。

以下伪代码遍历整个图,并记录发现时间和完成时间:

DFS(G):
    对 G 中的每个顶点 u:
        color[u] = WHITE
        parent[u] = NONE

    time = 0

    过程 VISIT(u):
        color[u] = GRAY
        time = time + 1
        discover[u] = time

        对 neighbors(u) 中的每个 v:
            如果 color[v] == WHITE:
                parent[v] = u
                VISIT(v)

        color[u] = BLACK
        time = time + 1
        finish[u] = time

    对 G 中的每个顶点 u:
        如果 color[u] == WHITE:
            VISIT(u)

这里,所有 VISIT 调用共享变量 time。递归调用栈保存了从当前 DFS 树根到正在探索的顶点之间的活动路径。从一次调用返回,就完成了一步回溯。

如果只需确定可达性,使用一个布尔类型的访问标记就足够了;可以省略灰色与黑色的区分以及时间戳。更复杂的应用则会利用这些附加状态,区分仍处于活动状态的顶点与已经完成的顶点。

迭代实现

DFS 也可以在不使用递归调用的情况下实现。为了精确复现递归算法,包括顶点完成时的操作,可以使用显式栈保存栈帧,每个栈帧包含一个顶点及其相邻顶点列表中的当前位置:

将 start 标记为已发现
将 (start, 遍历 neighbors(start) 的迭代器) 压栈

当栈非空时:
    (u, 迭代器) = 栈顶帧

    如果迭代器还有下一个相邻顶点:
        v = 下一个相邻顶点
        如果 v 尚未发现:
            parent[v] = u
            将 v 标记为已发现
            将 (v, 遍历 neighbors(v) 的迭代器) 压栈
    否则:
        将 u 标记为已完成
        弹出栈顶帧

要遍历整个图,就对每个仍未被发现的顶点重复这一过程。

当相邻顶点的顺序相同时,这种基于栈帧的实现能够保持与递归算法一致的行为。另一种更简单的实现是将所有相邻顶点压入栈中,这对于判断可达性可能已经足够,但其发现顺序和父子关系取决于顶点何时被标记。尤其是,在每个相邻顶点入栈时立即将其标记为已发现,通常无法复现递归 DFS 的行为。

对于依赖 DFS 祖先关系或完成顺序,而不只是要求访问所有可达顶点的算法,这一区别十分重要。

示例与遍历顺序

考虑一个无向图,其边为

{A,B},{A,C},{B,D},{B,E},{C,F}.\{A,B\},\quad \{A,C\},\quad \{B,D\},\quad \{B,E\},\quad \{C,F\}.

从 AA 出发,按字母顺序检查相邻顶点,得到的发现顺序为

A, B, D, E, C, F.A,\ B,\ D,\ E,\ C,\ F.

搜索沿 A→B→DA \rightarrow B \rightarrow D 前进,返回 BB,探索 EE,再返回 AA,然后探索 CC 和 FF。

完成顺序为

D, E, B, F, C, A.D,\ E,\ B,\ F,\ C,\ A.

这两种顺序对应于两种常见的树遍历方式:

  • **先序遍历:**在发现顶点时处理它。
  • **后序遍历:**在完成顶点时处理它。

对于二叉树,中序遍历是另一种深度优先遍历约定:先遍历左子树,再处理当前顶点,最后遍历右子树。这种约定依赖于左右子节点的区分,在一般图中没有直接对应的标准形式。

结构性质

发现与完成时间区间

对于每个顶点 uu,设 d(u)d(u) 为其发现时间,f(u)f(u) 为其完成时间,则有

d(u)<f(u).d(u)<f(u).

任意两个不同顶点的发现—完成时间区间,要么互不相交,要么其中一个包含另一个。具体而言,vv 是 DFS 森林中 uu 的真后代,当且仅当

d(u)<d(v)<f(v)<f(u).d(u)<d(v)<f(v)<f(u).

这种嵌套性质反映了搜索的递归结构:一个顶点只有在其所有 DFS 后代都完成后,才会完成。

边的分类

对于有向图,可以根据边与 DFS 森林的关系对边进行分类:

  • 树边用于发现此前尚未访问的顶点。
  • 回边从某个顶点指向其在 DFS 树中的祖先;自环也视为回边。
  • 前向边指向真后代,但不是树边。
  • 交叉边连接在 DFS 森林中没有祖先与后代关系的顶点。

检查一条边时,如果目标顶点为白色,则该边为树边;如果目标顶点为灰色,则该边为回边。指向黑色顶点的边可能是前向边,也可能是交叉边。

对于无向图,非树边连接的两个顶点具有祖先与后代关系。检测环时,必须将一条边与对同一条树边的反向检查区分开来。在含有平行边的多重图中,这就要求记录边的身份,而不能简单地忽略所有通向父顶点的边。

复杂度

对于使用邻接表存储的图,一次完整 DFS 的时间复杂度为

O(∣V∣+∣E∣).O(|V|+|E|).

每个顶点只被发现一次,每个邻接表条目只被检查一次。在无向图中,一条边通常出现在两个邻接表中,但这只会改变常数因子。

如果使用邻接矩阵,检查每个顶点的所有可能相邻顶点需要

O(∣V∣2)O(|V|^2)

的时间,即使图中的边相对较少也是如此。

标准算法需要 O(∣V∣)O(|V|) 的辅助空间复杂度,用于保存顶点状态、父节点信息以及递归栈或显式栈,不包括图本身的存储空间。当 DFS 树是一条长路径时,栈深度可达 ∣V∣|V|。因此,在深度很大的图上,递归实现可能会超出编程环境的调用栈限制。

对于按需生成子节点的树,遍历栈可能只需 O(h)O(h) 的空间,其中 hh 为树的高度。这一较小的空间界限不包括一般图所需的已访问顶点集合、所有已生成子节点的存储空间,以及保留下来的遍历输出。

应用

可达性与路径查找

DFS 可以判断从一个顶点是否能够到达另一个顶点。通过记录父节点指针,可以沿这些指针反向追溯,重建搜索发现的路径。

找到的路径不一定是最短路径。对于无权图,广度优先搜索可以找到边数最少的路径。对于边权非负的加权图,迪ijkstra算法可以求解最短路径问题。

连通性与环

反复执行 DFS 可以找出无向图的各个连通分量。

在有向图中,存在环当且仅当一次完整的 DFS 遇到回边。对于无向图,在正确处理对父边的反向检查后,一条通向已发现顶点的边可能表明存在环。

拓扑排序

有向无环图存在一种拓扑排序:在这种顶点排列中,每条边的起点都位于终点之前。

将 DFS 的完成顺序反转,即可得到这样的排列。如果检测到回边,就说明存在有向环,此时不存在拓扑排序。这项技术用于依赖关系分析和调度。

强连通分量

强连通分量是有向图中的一个极大顶点集合,其中每个顶点都能到达集合中的其他每个顶点。

多种线性时间算法使用 DFS 来找出这些分量。Kosaraju 算法结合完成顺序,在将所有边反向后的图上进行第二次遍历。Tarjan 算法则利用发现序号、低链接值和一个独立的栈,在一次基于 DFS 的遍历中识别这些分量。

桥与割点

在无向图中,DFS 可以在线性时间内识别:

  • **桥:**删除后会使连通分量数量增加的边。
  • **割点:**删除后会使连通分量数量增加的顶点。

这些算法记录后代顶点是否能够通过非树边到达祖先顶点。其正确性依赖于 DFS 所建立的祖先关系结构。

回溯与状态空间搜索

DFS 为回溯法提供了遍历模式:不断扩展部分解,直到得到有效解或违反某项约束。其应用包括迷宫求解、谜题搜索以及组合方案的枚举。

在这种情形下,顶点表示一个状态或部分解,不一定是显式存储的图顶点。与普通图遍历不同,一些枚举任务必须沿不同路径重新访问同一状态,因此,使用全局已访问集合可能会错误地丢弃有效解。

深度优先探索也用于博弈树搜索和形式验证;在后者中,被探索的图可以表示系统的可能状态。

局限与变体

在有限图上,记录已访问状态的 DFS 会终止,并访问从起点可达的每个顶点。然而,在无限或隐式生成的搜索空间中,不受限制的 DFS 可能沿一条无限分支持续深入,始终不去检查另一条包含解的分支。

深度受限搜索不探索超过指定深度的部分,但可能因此漏掉更深处的解。迭代加深深度优先搜索则反复执行深度受限搜索,并逐步提高深度上限。在分支数有限且满足标准树搜索假设的条件下,它最终能够找到深度最小的解,同时保持深度优先搜索式的内存使用方式。代价是需要重复探索较浅的层次。

DFS 本身并不考虑代价:默认情况下,无论是边权还是与目标的接近程度,都不会决定其探索顺序。相邻顶点的顺序可以显著影响找到解的速度,但仅靠调整顺序并不能保证找到最优解。DFS 中较长的依赖链,也使它不如具有大量可独立探索的前沿顶点的遍历方式那样适合并行计算。