深度优先搜索（Depth-First Search）

算法原理

深度优先搜索（DFS）是图上遍历的"一条路走到黑"策略：从起点出发，沿一个方向不断深入未访问的邻居，直到无路可走，再回溯到最近一个还有选择的节点换方向——访问顺序与栈天然对应：递归调用栈，或显式的工作栈。这与广度优先搜索（队列驱动、层层扩散）形成鲜明对照：DFS 不保证首次到达即最短，但它贴着"深度"走，是连通性、拓扑排序、割点桥、迷宫求解等一大批算法的地基。

本动画在 6 节点 7 边的无向图上做一次完整 DFS（起点 0，邻居按编号升序尝试）：

邻接表：0:[1,2]  1:[0,3,4]  2:[0,4]  3:[1,5]  4:[1,2,5]  5:[3,4]
访问序：0 → 1 → 3 → 5 → 4 → 2（一拍入栈一节点）
回溯序：2 → 4 → 5 → 3 → 1（一拍弹栈退一步）

节拍（动画严格按此演示）：访问拍——光点沿边滑入新节点、节点入栈；回溯拍——当前节点四邻已尽，光点沿原边退回上一层、栈弹出一格；全部 6 节点访问完毕，栈清空，收大✓。全片 13 拍，栈深峰值 5（0-1-3-5-4 这条纵深链）。

动画怎么看

• 橙色节点：当前在栈上的节点（正在被探索的路径）；
• 淡绿节点：访问过、但已随回溯弹出栈的节点——DFS 的"走过了"痕迹；
• 暗节点：尚未触及；
• 点阵虚线边：路径边亮青色；两端都访问过的边转淡绿；没走过的边保持暗色。本拍移动的边，12 个小点在整拍内一个接一个亮起——光波沿边推进，方向即探索方向；
• 右侧栈列：与图同拍的镜像——入栈时卡片推入栈顶、回溯时弹出淡出，栈底在下、栈顶在上；
• warning 光点：探查者本尊，访问拍沿线滑入，回溯拍沿线退回。

复杂度分析

C++ 参考代码

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> adj = {
    {1, 2},    // 0
    {0, 3, 4}, // 1
    {0, 4},    // 2
    {1, 5},    // 3
    {1, 2, 5}, // 4
    {3, 4},    // 5
};
vector<bool> visited(6, false);

// 递归 DFS：调用栈本身就是那根"栈"
void dfs(int u) {
    visited[u] = true;
    cout << "访问 " << u << endl;      // 入栈
    for (int v : adj[u])
        if (!visited[v])
            dfs(v);
    cout << "回溯 " << u << endl;      // 弹栈
}

int main() {
    dfs(0);                            // 访问序 0 1 3 5 4 2
    return 0;
}

什么时候用深度优先搜索

问"能不能到达""连通块有几个""所有方案/所有路径"时，DFS 是最顺手的工具：迷宫求解、岛屿数量、括号生成、全排列，骨架都是它。图上要拓扑排序（有向无环图）、找强连通分量、判二分图，标准实现也建立在 DFS 之上。它的短板同样鲜明：无权图最短路要用 BFS，带权图要用 Dijkstra——DFS 第一次摸到的路只是"一条路"，不是"最短的路"。写法上最大的坑是递归深度：链状图上递归栈会打满，工程里常用显式栈改迭代版；本动画右侧的栈列正是把"递归调用栈"画成了看得见的一格一格。