本篇节选自OI WIKI
引入
DFS 全称是 Depth First Search ，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法．所谓深度优先，就是说每次都尝试向更深的节点走．
该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，用途完全不同，很少有能混用两种算法的情况．\color{red}{用途完全不同，很少有能混用两种算法的情况．}用途完全不同，很少有能混用两种算法的情况．
DFS 常常用来指代用递归函数实现的搜索，但实际上两者并不一样．
过程
DFS 最显著的特征在于其 递归调用自身\color{red}{ 递归调用自身}递归调用自身 ．同时与 BFS 类似，
DFS 会对其访问过的点打上访问标记，在遍历图时跳过已打过标记的点，以确保 每个点仅访问一次．
符合以上两条规则的函数，便是广义上的 DFS．
具体地说，DFS 大致结构如下：
以上代码只包含了 DFS 必需的主要结构．实际的 DFS 会在以上代码基础上加入一些代码，利用 DFS 性质进行其他操作．
性质
该算法通常的时间复杂度为 𝑂(𝑛 +𝑚)，空间复杂度为 𝑂(𝑛)
O(n)，其中n 表示点数，𝑚表示边数．
注意空间复杂度包含了栈空间，栈空间的空间复杂度是 𝑂(𝑛)的．
栈实现
DFS 可以使用 栈（Stack）\color{red}{栈（Stack）}栈（Stack） 为遍历中节点的暂存容器来实现；这与用 队列（Queue） 实现的 BFS 形成高度对应．
递归实现
函数在递归调用时的求值如同对栈的添加和删除元素的顺序，故函数调用所占据的虚拟地址被称为 函数调用栈（Call Stack）
DFS 序列
DFS 序列是指 DFS 调用过程中访问的节点编号的序列．
我们发现，每个子树都对应 DFS 序列中的连续一段（一段区间）．
一般图上 DFS
对于非连通图，只能访问到起点所在的连通分量．
对于连通图，DFS 序列通常不唯一．
注：树的 DFS 序列也是不唯一的．
在 DFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 DFS 树．DFS 树是原图的一个生成树．
DFS 树 有很多性质，比如可以用来求 强连通分量．
