核心思想

DFS（Depth First Search，深度优先搜索）从一个顶点出发，选择一个未访问的邻接点继续向下搜索。

如果当前顶点已经没有可以继续访问的邻接点，就退回上一个顶点，再尝试其他方向。

简单来说就是：

一条路尽量走到底，走不动了再退回来。

这个“退回来”的过程称为回溯。

基本过程

仍然使用上一篇中的图：

    A
   / \
  B   C
 / \   \
D   E   F

假设邻接点按照从左到右的顺序访问，从 A 开始执行 DFS，访问顺序为：

A → B → D → E → C → F

具体过程为：

访问 A
进入 B
进入 D
D 无法继续，退回 B
进入 E
E 无法继续，退回 B，再退回 A
进入 C
进入 F

DFS 不会先处理完同一层的顶点，而是优先沿着当前路径继续深入。

实现要点

递归

DFS 最常见的写法是递归。

对于当前顶点 u：

  1. 将 u 标记为已经访问。
  2. 访问 u。
  3. 遍历 u 的所有邻接点。
  4. 如果邻接点尚未访问，就从该邻接点继续执行 DFS。

递归调用会暂时保存当前顶点的搜索状态。

当下一层搜索结束后，程序会自动返回当前层，继续检查剩余的邻接点。

回溯

以前面的图为例，搜索到 D 时，D 已经没有未访问的邻接点。

此时递归函数结束，程序返回 B：

A → B → D
        ↑
      返回 B

回到 B 后，再继续访问它的另一个邻接点 E。

因此，DFS 的搜索过程可以理解为不断重复：

深入 → 无法继续 → 回退 → 尝试其他方向

递归写法中的回退由函数调用栈自动完成，不需要手动记录返回位置。

栈

递归实现的 DFS，本质上使用了系统的函数调用栈。

也可以使用 std::stack 手动实现：

将起点压入栈

当栈不为空时：
    取出栈顶顶点
    如果它已经访问，跳过
    否则标记并访问
    将它的未访问邻接点压入栈

栈具有后进先出的特点，因此最后压入的顶点会最先被访问。

如果希望迭代写法与递归写法得到相同的访问顺序，通常需要按照相反顺序将邻接点压入栈。

邻接点顺序

DFS 的访问结果通常不是唯一的。

例如，A 同时与 B、C 相邻：

先访问 B：A → B → D → E → C → F
先访问 C：A → C → F → B → D → E

两种结果都属于合法的 DFS 遍历。

实际访问顺序取决于邻接点在邻接表中的存储顺序。

重点：判断 DFS 是否正确时，应检查它是否符合深度优先的过程，而不能只记住一种固定序列。

复杂度

设顶点数为 VV，边数为 EE：

存储方式 时间复杂度 原因
邻接表 O(V+E)O(V+E) 每个顶点访问一次，每条边检查有限次
邻接矩阵 O(V2)O(V^2) 对每个顶点都要扫描矩阵的一整行

visited 数组需要 O(V)O(V) 的空间。

递归调用栈在最坏情况下可能保存 VV 个顶点，因此 DFS 的额外空间复杂度为：

O(V)O(V)

例如，图退化成一条很长的链时，递归深度可能接近顶点数。

A → B → C → D → E → ...

如果图的规模很大，需要注意递归层数过深的问题，此时可以改用显式栈实现。

路径性质

DFS 可以用于寻找起点到目标顶点的一条路径。

在搜索过程中记录每个顶点的前驱：

parent[v] = u;

找到目标顶点后，就可以沿着 parent 数组反向恢复路径。

不过，DFS 第一次找到的路径通常不保证是最短路径。

例如：

A — B — C — D
 \_________/

DFS 可能先沿着：

A → B → C → D

找到 D，但实际上还存在边数更少的路径：

A → D

因此，DFS 更适合判断“是否存在路径”或搜索某一种可行方案。

常见用途

  • 图的遍历
  • 判断两个顶点之间是否存在路径
  • 求连通分量
  • 检测图中是否存在环
  • 拓扑排序
  • 寻找强连通分量
  • 迷宫搜索
  • 回溯问题
  • 树的先序遍历和后序遍历

其中，环检测需要根据图的类型采用不同的判断方式。

无向图中，需要区分当前顶点的父节点；有向图中，通常还要记录顶点是否位于当前递归路径上。

代码

这里继续使用上一篇中的邻接表结构。

visited 数组的作用和非连通图的处理方式已经在 BFS 中记录过，这里不再重复展开。

// 邻接表方式
void DFS(
    const ALGraph& G,
    const int u,
    bool visited[]
) {
    visited[u] = true;
    std::cout << u << " ";

    ArcNode* p = G.vertices[u].first;

    while (p != nullptr) {
        int v = p->adjvex;

        if (!visited[v]) {
            DFS(G, v, visited);
        }

        p = p->next;
    }
}

void DFSTraverse(const ALGraph& G) {
    bool visited[MAXV] = {false};

    for (int v = 0; v < G.vexnum; ++v) {
        if (!visited[v]) {
            DFS(G, v, visited);
        }
    }
}

在 DFS 中，每次递归只负责处理当前顶点及其后续搜索。

DFSTraverse 负责初始化 visited 数组，并保证所有顶点最终都能被检查。

总结

  • 核心过程：沿一条路径不断深入，无法继续时回溯
  • 核心数据结构：栈
  • 常见实现方式：递归
  • 访问顺序：取决于邻接点的存储顺序
  • 邻接表时间复杂度：O(V+E)O(V+E)
  • 邻接矩阵时间复杂度：O(V2)O(V^2)
  • 空间复杂度：O(V)O(V)
  • DFS 找到的路径不一定是最短路径
  • 常见应用：路径搜索、环检测、拓扑排序和回溯

轻松拿下BFS和DFS，不过现在还只学了邻接表的表示方法。
有空再去看看邻接矩阵是什么样的。
看了看目录，明天该学最小生成树了。
也是件麻烦的事啊🫠。
比耶的贵贵