不爱吃饭的蓝胖子要开始整活了！！！​

大家好，我是蓝胖子！好久不见，倍感思念！今天带来的是——C++ DFS深搜详解~~

希望你能看到最后，有惊喜哈！

                                                             正片开始 ——————————————————————————————————————————

一、什么是DFS？​

深度优先搜索（Depth-First Search，DFS）​ 是一种用于遍历或搜索树或图的算法。它的核心思想就像走迷宫一样：​“一条路走到黑，撞了南墙再回头”​。

想象一下，你面前有好多条岔路。DFS会让你选择其中一条路，一直往里走，直到走到死胡同（没有路了），然后才回溯到上一个岔路口，换另一条路继续探索。这种“不撞南墙不回头”的执着劲儿，就是DFS的精髓！

二、DFS的工作原理

DFS的工作流程可以用几个关键词概括：递归、深入、回溯。

1. 选择起点：从一个节点（比如迷宫的入口）开始。
2. 标记与深入：访问当前节点，并把它标记为“已访问”。然后，从它的邻居中选一个未访问的节点，一头扎进去，重复这个过程。
3. 回溯：当走到一个节点，发现它的所有邻居都已经被访问过了（或者无路可走），就“退回”到上一个节点，看看还有没有其他没走过的路。
4. 重复：不断重复“深入”和“回溯”，直到所有能到达的节点都被访问一遍。

这个过程天然适合用递归来实现，因为“深入”就是函数调用自己，“回溯”就是函数返回。

三、C++实现DFS的两种方式

3.1 递归实现（最常用、最直观）​

递归是DFS最自然的表达方式。下面是一个通用的递归模板，适用于大多数DFS问题：

// 假设图用邻接表 vector<vector<int>> graph 表示

vector<bool> visited; // 访问标记数组

void dfs(int node) {

// 1. 处理当前节点（例如输出、记录路径等）

cout << "正在访问节点: " << node << endl;

// 标记为已访问

visited[node] = true;

// 2. 递归探索所有未访问的邻居

for (int neighbor : graph[node]) {

if (!visited[neighbor]) {

dfs(neighbor); // 这就是“深入”

}

}

// 函数结束，自动“回溯”到上一层调用者

}

关键点：

• visited 数组至关重要，防止重复访问，陷入无限循环。
• 递归的“递”就是深入，“归”就是回溯。

3.2 迭代实现（使用显式栈）​

如果你担心递归深度太深导致栈溢出，或者就是想用循环，可以用栈（Stack）来模拟递归过程。

核心：我们用stack手动管理了需要访问的节点顺序，代替了系统调用栈。

四、经典实战：全排列问题

光说不练假把式！让我们用DFS解决一个经典问题：生成数字1到n的所有全排列。

问题：输入n，输出1~n这n个数字所有可能的排列顺序。

DFS思路：

1. 想象我们有n个空位，需要依次填入数字。
2. 状态：当前正在填第几个空位（step），以及哪些数字已经被用过了（used数组）。
3. 选择：对于当前空位，尝试所有未被使用的数字。
4. 递归：填入一个数字后，标记它已被使用，然后去填下一个空位（step+1）。
5. 回溯：当填完所有空位（step > n），就得到了一个排列，输出它。然后关键一步：返回上一层时，要把刚才填的数字标记为“未使用”，这样它才能被用于其他位置。

代码实现：

void dfs_iterative(int start, const vector<vector<int>>& graph) {

    int n = graph.size();

    vector<bool> visited(n, false);
    
    stack<int> stk;

    stk.push(start);

    while (!stk.empty()) {

    int node = stk.top();

    stk.pop();

    if (!visited[node]) {

        // 处理当前节点

        cout << "正在访问节点: " << node << endl;

        visited[node] = true;

        // 注意：栈是后进先出，为了和递归顺序一致，

        // 有时需要将邻居逆序入栈，这里简单处理所有邻居

        for (int neighbor : graph[node]) {

            if (!visited[neighbor]) {

                stk.push(neighbor);

            }

        }

    }

    }

}

输入 3

输出：

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

这就是DFS强大而优雅的地方！通过递归和回溯，我们系统地枚举了所有可能性。

五、DFS的常见应用场景

掌握了模板，DFS就能大显身手了：

• 图的连通性检测：判断两个点是否相连，或者图中有几个连通块。
• 路径查找：迷宫问题、棋盘问题（如八皇后）。
• 组合与排列：就像上面的例子，求所有子集、所有组合。
• 拓扑排序。
• 解决回溯问题：如数独、N皇后等约束满足问题。

六、DFS vs BFS（广度优先搜索）​

经常有小伙伴分不清DFS和它的好兄弟BFS，这里简单对比下：

特性	DFS (深度优先搜索)	BFS (广度优先搜索)
核心数据结构	栈 (递归隐式使用)	队列
搜索顺序	一条路走到黑，再回溯	一层一层向外扩散
空间复杂度	O(h)，h为递归深度	O(w)，w为最宽层的宽度
适合解决的问题	​“所有解”​、连通性、拓扑排序	​“最短路径”​、层序遍历
形象比喻	探险家，喜欢深入洞穴	雷达，一圈一圈扫描

简单记：要所有可能方案，用DFS；要找最短最快路线，用BFS。

七、注意事项与小技巧

1. 剪枝：这是优化DFS的关键！在递归过程中，如果提前发现当前路径不可能得到正确解，就立刻返回，节省大量时间。比如求组合时，如果剩余元素全选上也不够数量，就可以剪枝。
2. 避免重复状态：像visited数组一样，有时需要更复杂的状态记录（比如用哈希集合）来避免搜索相同的状态。
3. 递归深度：递归虽然简洁，但深度过大可能导致栈溢出。对于极端情况，考虑迭代实现或优化算法。
4. 恢复现场：回溯时，一定要把状态还原到递归之前的样子，这是DFS正确的保证！

---

本文花费了蓝胖子的大量心血，也请大家尊重原创，不要转载，谢谢！！！​