DFS算法（递归）

DFS算法（递归）

DFS（Depth-First Search，深度优先搜索）是一种用于遍历或搜索树、图等数据结构的算法。其核心思想是：沿着一条路径尽可能深入地探索，直到无法继续前进（遇到已访问节点或无未访问邻接节点），再回溯到上一个节点，选择另一条未探索的路径继续深入。

• 所以可以用来遍历所有的路径

• 特点是一路深入，适合处理节点的先后关系、连通性等，适合搜索所有的路径

• 深度优先遍历可以求一个点到另一个点的最短路径的长度

一、DFS的应用场景

1. 图的遍历：连通性判断、强连通分量（SCC）求解。
2. 路径搜索：迷宫求解、两点间是否存在路径。
3. 拓扑排序：在有向无环图（DAG）中用于任务调度。
4. 回溯法：排列组合、子集问题、N皇后等。

二、DFS的原理

DFS的遍历过程类似于“走迷宫”：从起点出发，选择一个方向一直走到底，碰壁后退回上一个岔路口，选择另一个方向继续，直到遍历所有可达节点。

• 递归特性：DFS天然适合用递归实现（递归调用本身就是一种栈结构，可保存“回溯点”）。
• 非递归实现：也可用栈（Stack）手动模拟递归过程，记录待访问节点和回溯路径。
• 访问标记：必须通过一个“访问标记”机制（如布尔数组）记录已访问的节点，避免重复访问和死循环（尤其是图中存在环的情况）。

通用模版（递归版本）

DFS(当前顶点u) {// 标记当前顶点为已访问visited[u] = true;// 处理当前顶点u处理u;// 递归遍历所有未访问的邻接顶点for(所有从u出发能到达的顶点v) {if(v未被访问) {DFS(v);  // 递归深入v}}
}// 调用方式
初始化visited数组为false;
DFS(起点s);

通用模版（非递归版本）

DFS(起点s) {// 初始化visited数组：标记顶点是否已访问，初始化为falsestack栈：用于存储待访问顶点将起点s入栈;visited[s] = true;  // 标记起点为已访问// 循环处理栈中所有顶点while(栈不为空) {// 取出栈顶顶点uu = 栈顶顶点;弹出栈顶;// 处理当前顶点u（如输出、记录路径等）处理u;// 遍历u的所有邻接顶点v（逆序入栈，保证遍历顺序与递归一致）for(所有从u出发能到达的顶点v，按逆序遍历) {if(v未被访问) {visited[v] = true;  // 标记为已访问将v入栈;  // 入栈待处理}}}
}

三、DFS的实现步骤（以图为例）

假设我们用邻接表存储图（adj 是一个数组，adj[u] 表示节点 u 的所有邻接节点），下面是DFS的标准实现步骤：

步骤1：准备数据结构

• 图的存储：用邻接表 vector<vector<int>> adj 表示图（适用于稀疏图，效率更高）。
• 访问标记：用布尔数组 visited[] 标记节点是否已访问（初始化为 false）。
• 起始节点：从指定的起始节点 start 开始遍历。

步骤2：递归实现DFS的核心逻辑

1. 标记当前节点为已访问：进入函数后，首先将 visited[current] 设为 true，表示该节点已被处理。
2. 处理当前节点：根据需求执行具体操作（如输出节点值、记录路径等）。
3. 遍历所有邻接节点：对当前节点 current 的每一个邻接节点 next：
   • 若 next 未被访问（!visited[next]），则递归调用 dfs(next)，深入探索该路径。
   • 若 next 已被访问，则跳过（避免重复或死循环）。
4. 自动回溯：当当前节点的所有邻接节点都被处理后，函数自动返回（回溯到上一层调用），继续处理上一个节点的其他邻接节点。

步骤3：非递归实现（栈模拟）

若递归深度过深可能导致栈溢出，可用栈手动模拟DFS过程：

1. 创建栈并将起始节点 start 入栈，同时标记 visited[start] = true。
2. 当栈不为空时，弹出栈顶节点 current 并处理。
3. 遍历 current 的所有邻接节点 next：
   • 若 next 未被访问，则标记 visited[next] = true 并将其入栈（注意：为保证遍历顺序与递归一致，通常逆序入栈邻接节点）。
4. 重复步骤2-3，直到栈为空。

四、代码示例（C++实现）

以无向图为例，假设图结构如下（节点0-4）：

0 connected to 1, 2
1 connected to 0, 3, 4
2 connected to 0
3 connected to 1
4 connected to 1

递归实现

#include <iostream>
#include <vector>
using namespace std;// 邻接表存储图
vector<vector<int>> adj;
// 访问标记数组
vector<bool> visited;// 递归DFS函数：从节点u开始遍历
void dfs(int u) {// 1. 标记当前节点为已访问visited[u] = true;// 2. 处理当前节点（此处简单输出）cout << u << " ";// 3. 遍历所有邻接节点，递归访问未访问的节点for (int v : adj[u]) {if (!visited[v]) {  // 仅访问未被访问的节点dfs(v);}}// 4. 函数结束后自动回溯
}int main() {// 初始化图（5个节点：0-4）int n = 5;adj.resize(n);visited.resize(n, false);// 添加边（无向图，双向添加）adj[0].push_back(1);adj[0].push_back(2);adj[1].push_back(0);adj[1].push_back(3);adj[1].push_back(4);adj[2].push_back(0);adj[3].push_back(1);adj[4].push_back(1);// 从节点0开始DFScout << "DFS遍历结果（递归）：";dfs(0);  // 输出：0 1 3 4 2return 0;
}

非递归实现（栈模拟）

#include <iostream>
#include <vector>
#include <stack>
using namespace std;// 非递归DFS：用栈模拟
void dfs(int start, const vector<vector<int>>& adj) {int n = adj.size();vector<bool> visited(n, false);stack<int> st;// 1. 起始节点入栈并标记st.push(start);visited[start] = true;cout << "DFS遍历结果（非递归）：";// 2. 栈非空时循环while (!st.empty()) {// 弹出栈顶节点并处理int u = st.top();st.pop();cout << u << " ";// 3. 邻接节点入栈（逆序入栈，保证遍历顺序与递归一致）// 注：栈是后进先出，逆序入栈可让邻接节点按原顺序被访问for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {int v = *it;if (!visited[v]) {visited[v] = true;st.push(v);}}}
}int main() {// 图结构与递归示例相同int n = 5;vector<vector<int>> adj(n);adj[0].push_back(1);adj[0].push_back(2);adj[1].push_back(0);adj[1].push_back(3);adj[1].push_back(4);adj[2].push_back(0);adj[3].push_back(1);adj[4].push_back(1);// 从节点0开始DFSdfs(0, adj);  // 输出：0 1 3 4 2return 0;
}

五、时间复杂度

• 对于图：遍历所有节点 V 和边 E，时间复杂度为 O(V + E)。
• 对于树（特殊的图，边数 E = V-1）：时间复杂度为 O(V)。

总结：DFS的核心是“深度优先、回溯探索”，通过递归或栈实现，关键是用访问标记避免重复访问，广泛应用于各类搜索和遍历问题。