

DFS（图论）

DFS 全称是 Depth First Search ，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况。

DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样。有关该类搜索思想请参阅 DFS（搜索） .

DFS 最显著的特征在于其 递归调用自身 。同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次 。符合以上两条规则的函数，便是广义上的 DFS。

具体地说，DFS 大致结构如下：

DFS(v) // v 可以是图中的一个顶点，也可以是抽象的概念，如 dp 状态等。
  在 v 上打访问标记
  for u in v 的相邻节点
    if u 没有打过访问标记 then
      DFS(u)
    end
  end
end

以上代码只包含了 DFS 必需的主要结构。实际的 DFS 会在以上代码基础上加入一些代码，利用 DFS 性质进行其他操作。

该算法通常的时间复杂度为 $O(n+m)$ ，空间复杂度为 $O(n)$ ，其中 $n$ 表示点数， $m$ 表示边数。注意空间复杂度包含了栈空间，栈空间的空间复杂度是 $O(n)$ 的。在平均 $O(1)$ 遍历一条边的条件下才能达到此时间复杂度，例如用前向星或邻接表存储图；如果用邻接矩阵则不一定能达到此复杂度。

备注：目前大部分算法竞赛（包括 NOIP、大部分省选以及 CCF 举办的各项赛事）都支持 无限栈空间 ，即：栈空间不单独限制，但总内存空间仍然受题面限制。但大部分操作系统会对栈空间做额外的限制，因此在本地调试时需要一些方式来取消栈空间限制。

在 Windows 上，通常的方法是在 编译选项 中加入 -Wl,--stack=1000000000 ，表示将栈空间限制设置为 1000000000 字节。

在 Linux 上，通常的方法是在运行程序前 在终端内 执行 ulimit -s unlimited ，表示栈空间无限。每个终端只需执行一次，对之后每次程序运行都有效。

实现¶

以链式前向星为例：（和上方伪代码每行一一对应）

void dfs(int u) {
  vis[u] = 1;
  for (int i = head[u]; i; i = e[i].x) {
    if (!vis[e[i].t]) {
      dfs(v);
    }
  }
}

DFS 序列¶

DFS 序列是指 DFS 调用过程中访问的节点编号的序列。

我们发现，每个子树都对应 DFS 序列中的连续一段（一段区间）。

括号序列¶

DFS 进入某个节点的时候记录一个左括号 ( ，退出某个节点的啥时候记录一个右括号 ) 。

每个节点会出现两次。相邻两个节点的深度相差 1。

一般图上 DFS¶

对于非连通图，只能访问到起点所在的连通分量。

对于连通图，DFS 序列通常不唯一。

注：树的 DFS 序列也是不唯一的。

在 DFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 DFS 树。DFS 树是原图的一个生成树。

DFS 树有很多性质，比如可以用来求强连通分量。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Ir1d, greyqz, yjl9903, partychicken, ChungZH, qq1010903229, TrisolarisHD, Acfboy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

DFS（图论）

实现¶

DFS 序列¶

括号序列¶

一般图上 DFS¶

评论