DFS（图论）
引入
DFS 全称是 Depth First Search，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法．所谓深度优先，就是说每次都尝试向更深的节点走．
该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况．
DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样．有关该类搜索思想请参阅 DFS（搜索）.
过程
DFS 最显著的特征在于其 递归调用自身 ．同时与 BFS 类似，DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次 ．符合以上两条规则的函数，便是广义上的 DFS．
具体地说，DFS 大致结构如下：
---|---
以上代码只包含了 DFS 必需的主要结构．实际的 DFS 会在以上代码基础上加入一些代码，利用 DFS 性质进行其他操作．
## 性质
该算法通常的时间复杂度为 𝑂(𝑛 +𝑚)O(n+m)，空间复杂度为 𝑂(𝑛)O(n)，其中 𝑛n 表示点数，𝑚m 表示边数．注意空间复杂度包含了栈空间，栈空间的空间复杂度是 𝑂(𝑛)O(n) 的．在平均 𝑂(1)O(1) 遍历一条边的条件下才能达到此时间复杂度，例如用前向星或邻接表存储图；如果用邻接矩阵则不一定能达到此复杂度．
> 备注：目前大部分算法竞赛（包括 NOIP、大部分省选以及 CCF 举办的各项赛事）都支持 **无限栈空间** ，即：栈空间不单独限制，但总内存空间仍然受题面限制．但大部分操作系统会对栈空间做额外的限制，因此在本地调试时需要一些方式来取消栈空间限制．
>
> * 在 Windows 上，通常的方法是在 **编译选项** 中加入 `-Wl,--stack=1000000000`，表示将栈空间限制设置为 1000000000 字节．
> * 在 Linux 上，通常的方法是在运行程序前 **在终端内** 执行 `ulimit -s unlimited`，表示栈空间无限．每个终端只需执行一次，对之后每次程序运行都有效．
>
## 实现
### 栈实现
DFS 可以使用 [栈（Stack）](../../ds/stack/) 为遍历中节点的暂存容器来实现；这与用 [队列（Queue）](../../ds/queue/) 实现的 BFS 形成高度对应．
C++Python
---|---
---|---
### 递归实现
函数在递归调用时的求值如同对栈的添加和删除元素的顺序，故函数调用所占据的虚拟地址被称为函数调用栈（Call Stack），DFS 可用递归的方式实现．
以 [邻接表（Adjacency List）](../save/#邻接表) 作为图的存储方式：
C++Python
---|---
---|---
以 [链式前向星](../save/#链式前向星) 为例：
C++JavaPython
---|---
---|---
---|---
DFS 序列
DFS 序列是指 DFS 调用过程中访问的节点编号的序列．
我们发现，每个子树都对应 DFS 序列中的连续一段（一段区间）．
括号序列
DFS 进入某个节点的时候记录一个左括号 (，退出某个节点的时候记录一个右括号 )．
每个节点会出现两次．相邻两个节点的深度相差 1．
一般图上 DFS
对于非连通图，只能访问到起点所在的连通分量．
对于连通图，DFS 序列通常不唯一．
注：树的 DFS 序列也是不唯一的．
在 DFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 DFS 树．DFS 树是原图的一个生成树．
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Enter-tainer, ouuan, Tiphereth-A, Craneplayz, iamtwz, Ir1d, shenshuaijie, sshwy, vincent-163, Acfboy, billchenchina, ChungZH, greyqz, Haohu Shen, HeRaNO, ksyx, LLLgoyour, Marcythm, Menci, partychicken, qq1010903229, shawlleyw, StudyingFather, Xeonacid, yjl9903, zychen20 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用