本篇节选自OI wiki

引入

DFS 全称是 Depth First Search ，中文名是深度优先搜索，是一种用于遍历或搜索树或图的算法．所谓深度优先，就是说每次都尝试向更深的节点走．该算法讲解时常常与 BFS 并列，但两者除了都能遍历图的连通块以外，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)，其中n 表示点数，𝑚表示边数．注意空间复杂度包含了栈空间，栈空间的空间复杂度是 𝑂(𝑛)的．

栈实现

DFS 可以使用 为遍历中节点的暂存容器来实现；这与用 队列（Queue） 实现的 BFS 形成高度对应．

vector<vector<int>> adj;  // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历

void dfs(int s) {
  stack<int> st;
  st.push(s);
  vis[s] = true;

  while (!st.empty()) {
    int u = st.top();
    st.pop();

    for (int v : adj[u]) {
      if (!vis[v]) {
        vis[v] = true;  // 确保栈里没有重复元素
        st.push(v);
      }
    }
  }
}

递归实现

函数在递归调用时的求值如同对栈的添加和删除元素的顺序，故函数调用所占据的虚拟地址被称为 函数调用栈（Call Stack）

vector<vector<int>> adj;  // 邻接表
vector<bool> vis;         // 记录节点是否已经遍历

void dfs(const int u) {
  vis[u] = true;
  for (int v : adj[u])
    if (!vis[v]) dfs(v)
}

DFS 序列

DFS 序列是指 DFS 调用过程中访问的节点编号的序列．我们发现，每个子树都对应 DFS 序列中的连续一段（一段区间）．

一般图上 DFS

对于非连通图，只能访问到起点所在的连通分量．对于连通图，DFS 序列通常不唯一．注：树的 DFS 序列也是不唯一的．在 DFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 DFS 树．DFS 树是原图的一个生成树．DFS 树 有很多性质，比如可以用来求 强连通分量．