#创作笔记 DFS

AK后上岸

2026-06-22 19:34:26

发布于：浙江

2阅读

0回复

0点赞

这是一篇有关DFS的创作笔记(图论)

DFS(深度优先搜索)

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

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

DFS常常用来指代用递归函数实现的搜索，但实际上两者并不一样(搜索)

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

具体来说，其框架如下：

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

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

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

实现

栈实现

DFS 可以使用 栈（Stack） 为遍历中节点的暂存容器来实现
这与用 队列（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），DFS 可用递归的方式实现。

以 邻接表（Adjacency List） 作为图的存储方式：

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

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