Olverae Assets

1 一句话定义

DFS（深度优先搜索）就是从起点出发，沿一条路一直往深处走到底，走不动了再回退换一条没走过的路，靠递归（或一个栈）来记住"该回到哪里"。

把它想成走迷宫：手扶着一面墙一直往前走，能往里就往里钻，直到撞墙（没有新路）；这时原路退回到最近的岔路口，换一条还没走过的支路继续钻。这种"不到黄河不回头、撞墙才回退"的策略就是 DFS——它和 BFS 的区别只有一个：BFS 用队列逐层扩，DFS 用栈/递归一路扎到底。

这正是下一节交互区的示例图（和 BFS 页同一张）。圈里的 ①…⑥ 是 DFS 的访问顺序：从 0 一路深入，绿色边是"递归深入"走的边。对比 BFS 的 0,1,2,3,4,5（逐层），你会看到同一张图、两种完全不同的脚步。

2 模型 · 单步看递归怎么"扎到底再回退"

DFS 最自然的写法是递归，"该回到哪里"由调用栈替你记着。点 ▶ 单步看：每次进入 dfs(v) 就压一帧、标记 v，沿第一个没访问的邻居往下钻；撞墙（没有新邻居）就返回、弹栈。

DFS 的骨架（递归 = 自带一个栈）

和 BFS 几乎一样，只是把"队列 + while"换成"递归调用"。

void dfs(Graph g, int v) {
    visited[v] = true;                //  一进来就标记
    printf("%d ", v);              // ← 处理 v：打印/记录访问序（遍历的目的就在这步）
    for (int w : neighbours(v))
        if (!visited[w])              // 没访问过的邻居
            dfs(g, w);               // 递归深入这条边
}

DFS 和 BFS 的差别只在一处：BFS 用队列（先进先出 → 逐层），DFS 用递归/栈（后进先出 → 扎到底）。两者都靠 visited[] 防重复——递归 DFS 漏标 visited，遇到环会无限递归、栈溢出（和递归页"漏写基准"同源）。

DFS 遍历 · 源点 0（递归）

图（橙=正在处理，蓝虚线=在调用栈上(未走完)，绿=已彻底完成）

调用栈（栈顶在上 = 此刻正在 dfs 的那一层）

已访问顺序

还没开始

代码（当前行高亮）

提示

点 ▶ 演示 DFS：看递归调用栈怎么一路加深、撞墙后又一层层弹出。圈里的数字是访问的先后顺序。

0

已访问

0

栈深（递归层数）

—

当前顶点

3 核心要点 · 4 句人话吃透 DFS

每张卡片先一句大白话。重点是看清 DFS 和 BFS 的"唯一区别"，以及 DFS 擅长干什么。

① 栈/递归 = DFS 的发动机

一句话：DFS 用栈（后进先出）或递归，最后遇到的岔路最先被深入，于是"一条道走到黑"。

递归 DFS 不用自己写栈——函数调用栈就替你记着"撞墙后该回到哪个顶点、从哪个邻居继续"。把递归改成显式栈，效果一样。

② 和 BFS 只差一个容器

一句话：把 BFS 的队列换成栈，就是 DFS。骨架几乎一模一样，区别只在"下一个取谁"。

两者都遍历"所有可达点"、都靠 visited 防重复、都是 O(V+E)。BFS 逐层（适合最短路），DFS 扎到底（适合"是否连通 / 找环 / 拓扑序"）。

BFS: 队列 → 0,1,2,3,4,5 (按层) DFS: 递归 → 0,1,3,2,4,5 (扎到底)

③ DFS ≠ 最短路

一句话：DFS 第一次到达某点，走的不一定是最短路——求无权最短路要用 BFS。

DFS 会先一头扎到很深，可能绕一大圈才到某点。它擅长的是可达性、连通分量、环检测、拓扑排序，而不是最短距离。

④ 复杂度 O(V + E)

一句话：每个顶点访问一次、每条边看一次，邻接表下 O(V+E)，和 BFS 同级。

递归深度最坏是 O(V)（一条长链），要留意栈空间。要遍历整张图（含不连通部分）时，对每个还没访问的顶点各发起一次 DFS。

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是写 DFS 最常翻车的坑——漏标 visited 栈溢出、标记太晚、拿 DFS 求最短路、漏扫不连通部分。点击卡片看运行效果。

① 忘了标 visited

有环图里无限递归 → 栈溢出

② 标记时机太晚

递归返回后才标 → 同点被重复深入

③ 拿 DFS 求最短路

DFS 先到 ≠ 最短，最短路要用 BFS

④ 漏扫不连通部分

只从顶点 0 发起 → 别的连通块没访问到

// 点击上方任一卡片，查看错误代码与运行效果

$ ./a.out （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题正对 DFS 套路：数据结构、与 BFS 的区别、访问顺序、最短路误区、DFS 的拿手用途。最后到练习系统亲手写 DFS。

去做例题：DFS · 连通分量个数

去做例题

Depth-First Search (DFS)

深度优先搜索 DFS