1. 项目概述与核心价值最近在带新人或者自己回顾基础算法时发现一个挺有意思的现象很多朋友一提到深度优先搜索DFS脑子里立刻蹦出来的就是“递归”、“回溯”、“栈”这些术语但真要自己动手写一个解决实际问题的DFS代码哪怕是一个简单的全排列或者图的遍历往往就卡壳了。要么是递归边界条件没想清楚导致死循环要么是状态标记和恢复搞混了结果输出一堆重复项。这让我想起自己刚学算法那会儿也是对着书本上的伪代码琢磨半天总觉得隔着一层窗户纸。所以今天我们不谈那些高大上的理论就从一个最朴素、最直接的“C 实现深度优先搜索DFS的简单示例代码”入手。这个标题听起来平平无奇但它背后要解决的核心痛点非常明确如何将一个抽象的、图论或树上的搜索思想转化为清晰、健壮、可复用的C代码。这不仅仅是写几行递归函数那么简单它涉及到对问题状态的建模、递归函数的正确设计、避免常见陷阱的工程技巧以及如何将DFS作为一种思维模式应用到各类场景中。这篇文章适合谁呢如果你是刚开始接触算法竞赛的在校生或者是在工作中需要用到路径搜索、状态枚举等功能的开发者亦或是想巩固一下基础的数据结构爱好者那么这篇从“第一性原理”出发的代码拆解应该能给你带来一些实实在在的启发。我们会从一个最简单的“数字全排列”问题开始逐步深入到图的遍历并探讨非递归的实现。我会把我在调试这些代码时踩过的坑、总结的经验毫无保留地分享出来。2. DFS的核心思想与递归实现剖析2.1 深度优先搜索的本质一条路走到黑在开始写代码之前我们必须先统一思想。深度优先搜索Depth-First Search这个名字已经形象地说明了它的策略从起点开始选择一条分支尽可能深地探索下去直到这条路径的尽头无法继续或达到目标然后“回溯”到上一个分支点选择另一条未探索的路继续深入。你可以把它想象成走迷宫遇到岔路口先随便选一条路一直走走到死胡同就原路返回到上一个岔路口再换另一条没走过的路试试。这种“一条路走到黑不行就退回换路”的策略就是DFS的精髓。它天然适合用递归来实现因为递归函数的调用栈Call Stack完美地模拟了“前进”和“回溯”的过程每一次递归调用相当于向前探索一步每一次函数返回就相当于回溯一步。2.2 经典入门案例数字全排列的DFS实现全排列问题是理解递归DFS最好的敲门砖。问题描述很简单给定一个数字n输出1到n这n个数字的所有可能排列顺序。例如n3输出123, 132, 213, 231, 312, 321。我们先直接看代码然后逐行拆解其设计逻辑#include iostream #include vector using namespace std; int n; // 排列的数字范围1 ~ n vectorint path; // 记录当前已经选择的数字序列路径 vectorbool used; // 标记数字i是否已经被使用过 void dfs() { // 递归终止条件当路径长度达到n时说明一个排列已完成 if (path.size() n) { for (int num : path) cout num ; cout endl; return; } // 遍历所有可能的选择1到n for (int i 1; i n; i) { // 如果数字i还没有被使用过则可以选择它 if (!used[i]) { // 做出选择将i加入路径并标记为已使用 path.push_back(i); used[i] true; // 递归基于当前选择继续向下搜索 dfs(); // 撤销选择回溯在返回上一层递归前恢复现场 used[i] false; path.pop_back(); } } } int main() { cin n; used.resize(n 1, false); // 初始化标记数组下标从1开始 dfs(); return 0; }代码逻辑深度解析状态定义这是DFS设计的第一步也是最关键的一步。在这个问题中一个“状态”由两部分构成path路径记录了从搜索起点到当前节点所做的所有选择序列。它定义了“我们走到了哪里”。used使用标记这是一个布尔数组记录了每个数字是否已被纳入当前路径。它定义了“哪些选择在当前路径下是合法的”。没有这个标记我们就会重复选择同一个数字这是排列问题不允许的。递归函数dfs()的设计参数为什么这个dfs()函数没有参数因为我们将状态path和used定义为了全局变量。这是一种常见的写法简化了函数签名让递归体内的操作更直观。但需要注意在多线程或复杂嵌套调用时全局变量可能带来问题对于简单教学示例是合适的。终止条件if (path.size() n)。这表示当前路径已经包含了n个数字一个完整的排列已经生成。此时应该输出结果并返回结束这一条分支的搜索。核心循环for (int i 1; i n; i)。这个循环枚举了在当前状态下所有可能的选择即所有未被使用的数字。选择与递归对于每一个合法的选择i!used[i]我们执行三步操作path.push_back(i); used[i] true;——做出选择。更新状态将数字i纳入路径。dfs();——递归深入。基于新的状态包含了i的路径继续向下探索剩余数字的排列。这是DFS“深度”的体现。used[i] false; path.pop_back();——撤销选择回溯。当递归调用返回时意味着以i开头的所有子排列都已经被搜索完毕。为了探索以其他数字开头的排列我们必须将状态恢复到选择i之前的样子。这是回溯算法最精髓、也最容易出错的一步。忘记回溯或者回溯的顺序不对都会导致状态混乱和错误结果。实操心得理解“递归树”在脑子里或纸上画一棵“递归树”对理解DFS至关重要。树的根节点是空状态。第一层我们有n个分支选择1,2,...,n。选择1之后进入第二层此时可用的选择是{2,3,...,n}以此类推。dfs()的每次调用对应树上的一个节点递归调用就是在访问子节点函数返回就是在返回父节点。used数组保证了我们在一条路径上不会重复访问数字而path则记录了从根到当前节点的路径。2.3 从排列到组合DFS的变体理解了全排列我们稍微改动一下问题就能解决组合问题。比如从n个数中选出k个数的所有组合不考虑顺序。#include iostream #include vector using namespace std; int n, k; vectorint path; // 增加一个参数 start表示当前可以选择的数字起始位置 void dfs(int start) { if (path.size() k) { for (int num : path) cout num ; cout endl; return; } // 从start开始枚举避免产生顺序不同的相同组合如[1,2]和[2,1] for (int i start; i n; i) { path.push_back(i); dfs(i 1); // 下一层从i1开始选保证数字递增从而去重 path.pop_back(); // 回溯 } } int main() { cin n k; dfs(1); return 0; }关键改动解析去重逻辑组合[1,2]和[2,1]被视为同一种。为了在搜索中避免生成重复组合我们引入了一个新参数start。它表示当前层可以选择的数字的最小值。递归调用dfs(i 1)。这意味着当我们选择了数字i后下一层递归只能从比i大的数字开始选。这样就保证了path中的数字永远是按照递增顺序排列的从而天然地避免了顺序不同导致的重复。这是一种非常经典的“按顺序枚举”去重技巧。注意事项参数传递 vs 全局变量在组合DFS中我们使用了参数start来传递状态。这与全排列中使用全局used数组是两种不同的状态管理方式。全局变量优点是函数签名简洁在简单问题中直观。缺点是函数隐藏了依赖且在多路径搜索时需谨慎处理回溯。参数传递将状态显式地作为参数传递使得函数的依赖关系一目了然更符合“纯函数”的思想减少了副作用在复杂DFS中更安全、更模块化。在实际工程中更推荐使用参数传递或将状态封装成结构体作为参数。3. 图的深度优先遍历实现详解树和排列可以看作特殊的图无环连通图。现在我们将DFS应用到更一般的图结构上。图有两种常见的表示方法邻接矩阵和邻接表。邻接表在稀疏图中更节省空间也更常用。3.1 基于邻接表的图DFS遍历假设我们有一个无向图共有n个节点编号1~n以及若干条边。#include iostream #include vector using namespace std; const int MAXN 1000; // 根据题目要求调整最大节点数 int n, m; // n: 节点数 m: 边数 vectorint graph[MAXN]; // 邻接表graph[i]存储与节点i相邻的所有节点 bool visited[MAXN]; // 标记节点是否已被访问 void dfs(int u) { // u: 当前正在访问的节点 // 标记当前节点已访问 visited[u] true; cout Visiting node: u endl; // 遍历当前节点的所有邻居 for (int v : graph[u]) { // 如果邻居v尚未被访问则递归访问它 if (!visited[v]) { dfs(v); } // 如果v已被访问则说明是已探索过的边或父节点在无向图中跳过 } // 函数结束自动回溯到调用者父节点 } int main() { cin n m; // 初始化邻接表 for (int i 1; i n; i) { graph[i].clear(); } // 读入边构建无向图 for (int i 0; i m; i) { int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); // 无向图需要添加双向边 } // 初始化访问标记 fill(visited, visited MAXN, false); // 图可能不连通需要从每个未访问的节点开始DFS for (int i 1; i n; i) { if (!visited[i]) { cout Start a new DFS from node i : endl; dfs(i); } } return 0; }代码关键点解析数据结构选择vectorint graph[MAXN]是一个“向量数组”每个graph[i]是一个动态数组存储节点i的所有邻接点。这比int graph[MAXN][MAXN]的邻接矩阵在边数远小于n²时高效得多。递归函数设计dfs(int u)的参数u就是当前访问的节点。函数首先标记u为已访问并处理这里简单打印然后遍历u的所有邻居。访问检查if (!visited[v])是防止重复访问和陷入死循环的关键。没有这个检查对于无向图从u访问v后又会从v访问回u导致无限递归。对于有向图则可能在有环的图中无限循环。处理不连通图在main函数中我们用一个循环检查所有节点。如果发现未访问的节点i就以i为起点开始一次新的DFS。这确保了即使图被分割成多个连通分量每个分量都会被遍历到。3.2 记录DFS遍历路径有时我们不仅需要遍历还需要记录从起点到某个节点的路径。vectorint path; // 全局路径记录 void dfs_with_path(int u, int target) { visited[u] true; path.push_back(u); // 进入节点时加入路径 if (u target) { // 找到目标输出路径 cout Path found: ; for (int node : path) cout node ; cout endl; // 注意这里不return如果需要所有路径则继续如果只需一条可以return并清理状态。 } for (int v : graph[u]) { if (!visited[v]) { dfs_with_path(v, target); } } // 回溯离开节点时从路径中移除 path.pop_back(); visited[u] false; // 关键如果要求所有简单路径必须恢复访问标记 }重要区别在遍历仅访问每个节点一次的场景下visited标记在递归返回后不需要重置。因为我们的目的就是访问所有节点访问过就不用再去了。在寻路查找所有可能路径的场景下visited标记在递归返回后必须重置即visited[u] false;。因为一条路径探索完后我们需要“释放”这个节点允许其他路径再次经过它。同时path也需要进行对应的push_back和pop_back操作。这种“标记-递归-取消标记”的模式是回溯法搜索所有解的标准模板。踩坑实录visited数组的两种用法这是我早期最容易混淆的点连通性检测/遍历visited是永久标记。一旦访问永不恢复。目的是保证每个节点只被处理一次时间复杂度O(VE)。全路径搜索visited是临时标记。在一条路径的探索过程中标记回溯时清除。目的是防止在单条路径中重复访问节点形成环同时允许节点出现在不同的路径中。搜索所有简单路径的时间复杂度是指数级的。务必根据问题需求想清楚你的visited数组代表什么是否需要回溯。4. 非递归迭代DFS实现显式栈的使用递归虽然直观但在深度极大时可能导致栈溢出。此外理解非递归实现能让你更透彻地把握DFS“栈”的本质。我们可以用C STL中的stack来模拟递归过程。4.1 非递归DFS框架我们以图的遍历为例实现一个非递归版本。#include iostream #include vector #include stack using namespace std; const int MAXN 1000; vectorint graph[MAXN]; bool visited[MAXN]; void dfs_iterative(int start) { stackint stk; stk.push(start); // 注意在入栈时标记还是在出栈时标记逻辑不同 visited[start] true; // 方案1入栈即标记 while (!stk.empty()) { int u stk.top(); stk.pop(); cout Visiting node: u endl; // 处理节点 // 注意遍历邻接点的顺序栈是LIFO所以为了和递归顺序一致可能需要逆序入栈。 for (int v : graph[u]) { if (!visited[v]) { visited[v] true; // 入栈前标记避免同一节点多次入栈 stk.push(v); } } } }非递归DFS的要点栈的作用栈stk显式地保存了待访问的节点替代了递归的隐式调用栈。标记时机这是一个关键细节。上述代码采用“入栈即标记”visited[v] truebeforestk.push(v)。这可以防止同一个节点被多次压入栈中提高效率并且能保证每个节点只被访问一次。另一种“出栈时标记”可能导致节点重复入栈但在某些需要记录访问顺序的场景下有用。遍历顺序由于栈是“后进先出”(LIFO)for (int v : graph[u])正向遍历邻居并压栈实际访问顺序会是邻接表顺序的逆序。如果希望与递归顺序完全一致可以反向遍历邻居for (auto it graph[u].rbegin(); it ! graph[u].rend(); it)。路径记录在非递归中记录路径比递归麻烦。通常需要另一个栈或一个parent数组来记录每个节点的前驱节点当找到目标时再反向回溯构造路径。4.2 非递归DFS处理树的前序遍历对于树结构非递归DFS就是经典的前序遍历迭代写法。struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void preorderTraversal(TreeNode* root) { if (root nullptr) return; stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* node stk.top(); stk.pop(); cout node-val ; // 处理当前节点 // 栈是LIFO所以先右后左这样出栈顺序才是左-右前序中左右 if (node-right) stk.push(node-right); if (node-left) stk.push(node-left); } }实操心得递归 vs 非递归的选择优先使用递归代码简洁逻辑清晰尤其是对于树和状态空间搜索递归能自然地表达“分支”和“回溯”。在算法竞赛和大多数业务代码中递归深度通常不会导致栈溢出。考虑使用非递归问题深度极大有栈溢出风险如链状图。需要精确控制栈的状态或者需要将DFS过程暂停/恢复如协程、生成器模式。作为学习练习加深对DFS运行机制的理解。C中递归的函数调用有一定开销在极端性能敏感场景非递归可能略有优势但通常不是主要瓶颈。5. DFS常见应用场景与实战变种掌握了DFS的模板我们来看看它能解决哪些经典问题。理解这些问题如何被映射到DFS框架下是提升算法能力的关键。5.1 连通块计数岛屿问题LeetCode上经典的“200. 岛屿数量”。给定一个二维网格1代表陆地0代表水计算岛屿的数量连通陆地块。class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; // 方向数组代表上下左右四个方向的偏移量 vectorpairint, int directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 定义DFS函数淹没标记一块连续的陆地 functionvoid(int, int) dfs [](int i, int j) { // 边界条件判断 if (i 0 || i m || j 0 || j n || grid[i][j] ! 1) { return; } // 将当前陆地标记为已访问这里直接改为0即“淹没” grid[i][j] 0; // 向四个方向递归探索 for (auto dir : directions) { dfs(i dir.first, j dir.second); } }; // 遍历整个网格 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { // 发现一块未访问的陆地岛屿计数1并DFS淹没整个岛 count; dfs(i, j); } } } return count; } };场景映射分析状态每个(i, j)坐标就是一个节点。边上下左右相邻的1节点之间存在边。DFS作用从一块陆地出发递归地访问并标记所有与之连通的陆地从而将整个“岛屿”从地图上“抹去”标记为已访问。主循环遍历所有格子每当遇到一个未被访问的陆地1就说明发现了一个新岛屿启动一次DFS。5.2 回溯法解决经典问题N皇后N皇后是回溯法的标杆问题。在N×N的棋盘上放置N个皇后使得它们互不攻击即任意两个皇后不在同一行、同一列或同一斜线上。#include iostream #include vector #include string using namespace std; vectorvectorstring solveNQueens(int n) { vectorvectorstring solutions; vectorstring board(n, string(n, .)); // 初始化棋盘全为. // 使用三个布尔数组进行快速冲突检测 vectorbool cols(n, false); // 列标记 vectorbool diag1(2 * n - 1, false); // 主对角线标记 (row - col n - 1) vectorbool diag2(2 * n - 1, false); // 副对角线标记 (row col) functionvoid(int) backtrack [](int row) { if (row n) { // 所有行都成功放置了皇后找到一个解 solutions.push_back(board); return; } for (int col 0; col n; col) { int idx1 row - col n - 1; // 主对角线索引 int idx2 row col; // 副对角线索引 // 检查当前位置是否安全 if (!cols[col] !diag1[idx1] !diag2[idx2]) { // 做出选择 board[row][col] Q; cols[col] diag1[idx1] diag2[idx2] true; // 递归到下一行 backtrack(row 1); // 撤销选择回溯 board[row][col] .; cols[col] diag1[idx1] diag2[idx2] false; } } }; backtrack(0); // 从第0行开始放置 return solutions; }优化技巧解析状态表示我们逐行放置皇后所以状态是当前行号row。冲突检测优化这是代码的精华。最笨的方法是每次放置前检查所有已放置的皇后。cols[col]记录第col列是否已被占用。diag1[idx1]记录“行号-列号”为常数的主对角线是否被占用。对于同一个主对角线上的格子row - col的值是相同的。加上n-1是为了让索引非负。diag2[idx2]记录“行号列号”为常数的副对角线是否被占用。时间复杂度通过这三个数组我们可以在O(1)时间内判断一个位置是否安全将回溯的复杂度从O(N!)优化到仍然是指数级但常数项小了很多的程度这是通过“空间换时间”的典型实践。6. DFS调试技巧与性能考量6.1 调试可视化递归过程当DFS代码出现错误尤其是回溯逻辑错误时最有效的调试方法之一是打印递归树。int depth 0; // 全局或引用传递的深度计数器 void dfs_debug(int u, string indent ) { visited[u] true; cout indent Enter dfs( u ) endl; // ... 处理当前节点 ... for (int v : graph[u]) { if (!visited[v]) { dfs_debug(v, indent ); // 增加缩进 } } cout indent Leave dfs( u ) endl; // visited[u] false; // 如果是寻路可能需要回溯 }通过缩进你可以清晰地看到递归的进入和退出顺序以及参数的传递对于理解递归流程和查找逻辑错误比如该回溯的没回溯非常有帮助。6.2 性能陷阱与优化思路栈溢出递归深度过深如链状图深度达到10^5量级。解决方案改用非递归迭代实现。如果必须用递归尝试调整系统栈大小不推荐平台相关。检查算法是否必要如此深有时问题可以转化为BFS。重复状态与剪枝在搜索空间巨大的问题中如八数码、某些DP的DFS记忆化如果不加处理DFS会探索大量重复状态导致超时。记忆化搜索Memoization将(状态参数)作为键计算结果作为值存储在一个哈希表如unordered_map中。在递归开始时先查表如果已经计算过直接返回结果。这是将DFS与动态规划结合的重要手段。unordered_mapstring, int memo; int dfs(state) { if (memo.count(state)) return memo[state]; // ... 计算过程 ... memo[state] result; return result; }可行性剪枝在递归过程中如果发现当前分支无论如何都不可能达到目标或成为最优解则提前返回终止该分支的搜索。例如在求和问题中如果当前和已经超过目标值就没必要继续加了。遍历顺序的影响对于寻找一条可行路径的问题DFS的顺序可能导致效率天差地别。一个启发式的策略是“优先选择可能性少的分支”这能更快地触底回溯减少搜索范围。例如在解数独时优先填充候选数字最少的格子。6.3 何时选择DFS而非BFS需要所有解/路径DFS回溯天然适合枚举所有可能性如全排列、组合、N皇后。判断连通性/可达性DFS和BFS都可以DFS代码通常更短。拓扑排序、有向图环检测DFS可以方便地利用“访问状态”未访问、访问中、已访问来检测回边从而判断环。寻找一条路径如果路径可能很深且不需要最短路径DFS可能更快找到一条。需要模拟“尝试-回溯”过程这是DFS的看家本领。反之如果问题明确要求最短路径、最少步数或者在无限图中搜索广度优先搜索BFS通常是更好的选择因为它按层推进找到的第一个解就是最短的。写DFS代码就像在问题的状态空间里进行一场有条不紊的探险。递归是你的勘探队visited数组是你的地图标记而回溯则是你安全返回基地的保障。从简单的全排列到复杂的图论问题其核心框架都是相通的定义状态、设计递归函数、确定终止条件、枚举选择、递归深入、回溯恢复。希望这个从简单示例出发的深度剖析能帮你彻底打通DFS的任督二脉下次再遇到需要搜索的问题时能够自信地写出正确、高效的代码。记住多画图多思考状态和边界调试时善用打印这些朴素的习惯比死记硬背模板要管用得多。
C++深度优先搜索(DFS)实现：从递归到迭代的算法详解与实战
1. 项目概述与核心价值最近在带新人或者自己回顾基础算法时发现一个挺有意思的现象很多朋友一提到深度优先搜索DFS脑子里立刻蹦出来的就是“递归”、“回溯”、“栈”这些术语但真要自己动手写一个解决实际问题的DFS代码哪怕是一个简单的全排列或者图的遍历往往就卡壳了。要么是递归边界条件没想清楚导致死循环要么是状态标记和恢复搞混了结果输出一堆重复项。这让我想起自己刚学算法那会儿也是对着书本上的伪代码琢磨半天总觉得隔着一层窗户纸。所以今天我们不谈那些高大上的理论就从一个最朴素、最直接的“C 实现深度优先搜索DFS的简单示例代码”入手。这个标题听起来平平无奇但它背后要解决的核心痛点非常明确如何将一个抽象的、图论或树上的搜索思想转化为清晰、健壮、可复用的C代码。这不仅仅是写几行递归函数那么简单它涉及到对问题状态的建模、递归函数的正确设计、避免常见陷阱的工程技巧以及如何将DFS作为一种思维模式应用到各类场景中。这篇文章适合谁呢如果你是刚开始接触算法竞赛的在校生或者是在工作中需要用到路径搜索、状态枚举等功能的开发者亦或是想巩固一下基础的数据结构爱好者那么这篇从“第一性原理”出发的代码拆解应该能给你带来一些实实在在的启发。我们会从一个最简单的“数字全排列”问题开始逐步深入到图的遍历并探讨非递归的实现。我会把我在调试这些代码时踩过的坑、总结的经验毫无保留地分享出来。2. DFS的核心思想与递归实现剖析2.1 深度优先搜索的本质一条路走到黑在开始写代码之前我们必须先统一思想。深度优先搜索Depth-First Search这个名字已经形象地说明了它的策略从起点开始选择一条分支尽可能深地探索下去直到这条路径的尽头无法继续或达到目标然后“回溯”到上一个分支点选择另一条未探索的路继续深入。你可以把它想象成走迷宫遇到岔路口先随便选一条路一直走走到死胡同就原路返回到上一个岔路口再换另一条没走过的路试试。这种“一条路走到黑不行就退回换路”的策略就是DFS的精髓。它天然适合用递归来实现因为递归函数的调用栈Call Stack完美地模拟了“前进”和“回溯”的过程每一次递归调用相当于向前探索一步每一次函数返回就相当于回溯一步。2.2 经典入门案例数字全排列的DFS实现全排列问题是理解递归DFS最好的敲门砖。问题描述很简单给定一个数字n输出1到n这n个数字的所有可能排列顺序。例如n3输出123, 132, 213, 231, 312, 321。我们先直接看代码然后逐行拆解其设计逻辑#include iostream #include vector using namespace std; int n; // 排列的数字范围1 ~ n vectorint path; // 记录当前已经选择的数字序列路径 vectorbool used; // 标记数字i是否已经被使用过 void dfs() { // 递归终止条件当路径长度达到n时说明一个排列已完成 if (path.size() n) { for (int num : path) cout num ; cout endl; return; } // 遍历所有可能的选择1到n for (int i 1; i n; i) { // 如果数字i还没有被使用过则可以选择它 if (!used[i]) { // 做出选择将i加入路径并标记为已使用 path.push_back(i); used[i] true; // 递归基于当前选择继续向下搜索 dfs(); // 撤销选择回溯在返回上一层递归前恢复现场 used[i] false; path.pop_back(); } } } int main() { cin n; used.resize(n 1, false); // 初始化标记数组下标从1开始 dfs(); return 0; }代码逻辑深度解析状态定义这是DFS设计的第一步也是最关键的一步。在这个问题中一个“状态”由两部分构成path路径记录了从搜索起点到当前节点所做的所有选择序列。它定义了“我们走到了哪里”。used使用标记这是一个布尔数组记录了每个数字是否已被纳入当前路径。它定义了“哪些选择在当前路径下是合法的”。没有这个标记我们就会重复选择同一个数字这是排列问题不允许的。递归函数dfs()的设计参数为什么这个dfs()函数没有参数因为我们将状态path和used定义为了全局变量。这是一种常见的写法简化了函数签名让递归体内的操作更直观。但需要注意在多线程或复杂嵌套调用时全局变量可能带来问题对于简单教学示例是合适的。终止条件if (path.size() n)。这表示当前路径已经包含了n个数字一个完整的排列已经生成。此时应该输出结果并返回结束这一条分支的搜索。核心循环for (int i 1; i n; i)。这个循环枚举了在当前状态下所有可能的选择即所有未被使用的数字。选择与递归对于每一个合法的选择i!used[i]我们执行三步操作path.push_back(i); used[i] true;——做出选择。更新状态将数字i纳入路径。dfs();——递归深入。基于新的状态包含了i的路径继续向下探索剩余数字的排列。这是DFS“深度”的体现。used[i] false; path.pop_back();——撤销选择回溯。当递归调用返回时意味着以i开头的所有子排列都已经被搜索完毕。为了探索以其他数字开头的排列我们必须将状态恢复到选择i之前的样子。这是回溯算法最精髓、也最容易出错的一步。忘记回溯或者回溯的顺序不对都会导致状态混乱和错误结果。实操心得理解“递归树”在脑子里或纸上画一棵“递归树”对理解DFS至关重要。树的根节点是空状态。第一层我们有n个分支选择1,2,...,n。选择1之后进入第二层此时可用的选择是{2,3,...,n}以此类推。dfs()的每次调用对应树上的一个节点递归调用就是在访问子节点函数返回就是在返回父节点。used数组保证了我们在一条路径上不会重复访问数字而path则记录了从根到当前节点的路径。2.3 从排列到组合DFS的变体理解了全排列我们稍微改动一下问题就能解决组合问题。比如从n个数中选出k个数的所有组合不考虑顺序。#include iostream #include vector using namespace std; int n, k; vectorint path; // 增加一个参数 start表示当前可以选择的数字起始位置 void dfs(int start) { if (path.size() k) { for (int num : path) cout num ; cout endl; return; } // 从start开始枚举避免产生顺序不同的相同组合如[1,2]和[2,1] for (int i start; i n; i) { path.push_back(i); dfs(i 1); // 下一层从i1开始选保证数字递增从而去重 path.pop_back(); // 回溯 } } int main() { cin n k; dfs(1); return 0; }关键改动解析去重逻辑组合[1,2]和[2,1]被视为同一种。为了在搜索中避免生成重复组合我们引入了一个新参数start。它表示当前层可以选择的数字的最小值。递归调用dfs(i 1)。这意味着当我们选择了数字i后下一层递归只能从比i大的数字开始选。这样就保证了path中的数字永远是按照递增顺序排列的从而天然地避免了顺序不同导致的重复。这是一种非常经典的“按顺序枚举”去重技巧。注意事项参数传递 vs 全局变量在组合DFS中我们使用了参数start来传递状态。这与全排列中使用全局used数组是两种不同的状态管理方式。全局变量优点是函数签名简洁在简单问题中直观。缺点是函数隐藏了依赖且在多路径搜索时需谨慎处理回溯。参数传递将状态显式地作为参数传递使得函数的依赖关系一目了然更符合“纯函数”的思想减少了副作用在复杂DFS中更安全、更模块化。在实际工程中更推荐使用参数传递或将状态封装成结构体作为参数。3. 图的深度优先遍历实现详解树和排列可以看作特殊的图无环连通图。现在我们将DFS应用到更一般的图结构上。图有两种常见的表示方法邻接矩阵和邻接表。邻接表在稀疏图中更节省空间也更常用。3.1 基于邻接表的图DFS遍历假设我们有一个无向图共有n个节点编号1~n以及若干条边。#include iostream #include vector using namespace std; const int MAXN 1000; // 根据题目要求调整最大节点数 int n, m; // n: 节点数 m: 边数 vectorint graph[MAXN]; // 邻接表graph[i]存储与节点i相邻的所有节点 bool visited[MAXN]; // 标记节点是否已被访问 void dfs(int u) { // u: 当前正在访问的节点 // 标记当前节点已访问 visited[u] true; cout Visiting node: u endl; // 遍历当前节点的所有邻居 for (int v : graph[u]) { // 如果邻居v尚未被访问则递归访问它 if (!visited[v]) { dfs(v); } // 如果v已被访问则说明是已探索过的边或父节点在无向图中跳过 } // 函数结束自动回溯到调用者父节点 } int main() { cin n m; // 初始化邻接表 for (int i 1; i n; i) { graph[i].clear(); } // 读入边构建无向图 for (int i 0; i m; i) { int u, v; cin u v; graph[u].push_back(v); graph[v].push_back(u); // 无向图需要添加双向边 } // 初始化访问标记 fill(visited, visited MAXN, false); // 图可能不连通需要从每个未访问的节点开始DFS for (int i 1; i n; i) { if (!visited[i]) { cout Start a new DFS from node i : endl; dfs(i); } } return 0; }代码关键点解析数据结构选择vectorint graph[MAXN]是一个“向量数组”每个graph[i]是一个动态数组存储节点i的所有邻接点。这比int graph[MAXN][MAXN]的邻接矩阵在边数远小于n²时高效得多。递归函数设计dfs(int u)的参数u就是当前访问的节点。函数首先标记u为已访问并处理这里简单打印然后遍历u的所有邻居。访问检查if (!visited[v])是防止重复访问和陷入死循环的关键。没有这个检查对于无向图从u访问v后又会从v访问回u导致无限递归。对于有向图则可能在有环的图中无限循环。处理不连通图在main函数中我们用一个循环检查所有节点。如果发现未访问的节点i就以i为起点开始一次新的DFS。这确保了即使图被分割成多个连通分量每个分量都会被遍历到。3.2 记录DFS遍历路径有时我们不仅需要遍历还需要记录从起点到某个节点的路径。vectorint path; // 全局路径记录 void dfs_with_path(int u, int target) { visited[u] true; path.push_back(u); // 进入节点时加入路径 if (u target) { // 找到目标输出路径 cout Path found: ; for (int node : path) cout node ; cout endl; // 注意这里不return如果需要所有路径则继续如果只需一条可以return并清理状态。 } for (int v : graph[u]) { if (!visited[v]) { dfs_with_path(v, target); } } // 回溯离开节点时从路径中移除 path.pop_back(); visited[u] false; // 关键如果要求所有简单路径必须恢复访问标记 }重要区别在遍历仅访问每个节点一次的场景下visited标记在递归返回后不需要重置。因为我们的目的就是访问所有节点访问过就不用再去了。在寻路查找所有可能路径的场景下visited标记在递归返回后必须重置即visited[u] false;。因为一条路径探索完后我们需要“释放”这个节点允许其他路径再次经过它。同时path也需要进行对应的push_back和pop_back操作。这种“标记-递归-取消标记”的模式是回溯法搜索所有解的标准模板。踩坑实录visited数组的两种用法这是我早期最容易混淆的点连通性检测/遍历visited是永久标记。一旦访问永不恢复。目的是保证每个节点只被处理一次时间复杂度O(VE)。全路径搜索visited是临时标记。在一条路径的探索过程中标记回溯时清除。目的是防止在单条路径中重复访问节点形成环同时允许节点出现在不同的路径中。搜索所有简单路径的时间复杂度是指数级的。务必根据问题需求想清楚你的visited数组代表什么是否需要回溯。4. 非递归迭代DFS实现显式栈的使用递归虽然直观但在深度极大时可能导致栈溢出。此外理解非递归实现能让你更透彻地把握DFS“栈”的本质。我们可以用C STL中的stack来模拟递归过程。4.1 非递归DFS框架我们以图的遍历为例实现一个非递归版本。#include iostream #include vector #include stack using namespace std; const int MAXN 1000; vectorint graph[MAXN]; bool visited[MAXN]; void dfs_iterative(int start) { stackint stk; stk.push(start); // 注意在入栈时标记还是在出栈时标记逻辑不同 visited[start] true; // 方案1入栈即标记 while (!stk.empty()) { int u stk.top(); stk.pop(); cout Visiting node: u endl; // 处理节点 // 注意遍历邻接点的顺序栈是LIFO所以为了和递归顺序一致可能需要逆序入栈。 for (int v : graph[u]) { if (!visited[v]) { visited[v] true; // 入栈前标记避免同一节点多次入栈 stk.push(v); } } } }非递归DFS的要点栈的作用栈stk显式地保存了待访问的节点替代了递归的隐式调用栈。标记时机这是一个关键细节。上述代码采用“入栈即标记”visited[v] truebeforestk.push(v)。这可以防止同一个节点被多次压入栈中提高效率并且能保证每个节点只被访问一次。另一种“出栈时标记”可能导致节点重复入栈但在某些需要记录访问顺序的场景下有用。遍历顺序由于栈是“后进先出”(LIFO)for (int v : graph[u])正向遍历邻居并压栈实际访问顺序会是邻接表顺序的逆序。如果希望与递归顺序完全一致可以反向遍历邻居for (auto it graph[u].rbegin(); it ! graph[u].rend(); it)。路径记录在非递归中记录路径比递归麻烦。通常需要另一个栈或一个parent数组来记录每个节点的前驱节点当找到目标时再反向回溯构造路径。4.2 非递归DFS处理树的前序遍历对于树结构非递归DFS就是经典的前序遍历迭代写法。struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; void preorderTraversal(TreeNode* root) { if (root nullptr) return; stackTreeNode* stk; stk.push(root); while (!stk.empty()) { TreeNode* node stk.top(); stk.pop(); cout node-val ; // 处理当前节点 // 栈是LIFO所以先右后左这样出栈顺序才是左-右前序中左右 if (node-right) stk.push(node-right); if (node-left) stk.push(node-left); } }实操心得递归 vs 非递归的选择优先使用递归代码简洁逻辑清晰尤其是对于树和状态空间搜索递归能自然地表达“分支”和“回溯”。在算法竞赛和大多数业务代码中递归深度通常不会导致栈溢出。考虑使用非递归问题深度极大有栈溢出风险如链状图。需要精确控制栈的状态或者需要将DFS过程暂停/恢复如协程、生成器模式。作为学习练习加深对DFS运行机制的理解。C中递归的函数调用有一定开销在极端性能敏感场景非递归可能略有优势但通常不是主要瓶颈。5. DFS常见应用场景与实战变种掌握了DFS的模板我们来看看它能解决哪些经典问题。理解这些问题如何被映射到DFS框架下是提升算法能力的关键。5.1 连通块计数岛屿问题LeetCode上经典的“200. 岛屿数量”。给定一个二维网格1代表陆地0代表水计算岛屿的数量连通陆地块。class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; // 方向数组代表上下左右四个方向的偏移量 vectorpairint, int directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 定义DFS函数淹没标记一块连续的陆地 functionvoid(int, int) dfs [](int i, int j) { // 边界条件判断 if (i 0 || i m || j 0 || j n || grid[i][j] ! 1) { return; } // 将当前陆地标记为已访问这里直接改为0即“淹没” grid[i][j] 0; // 向四个方向递归探索 for (auto dir : directions) { dfs(i dir.first, j dir.second); } }; // 遍历整个网格 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { // 发现一块未访问的陆地岛屿计数1并DFS淹没整个岛 count; dfs(i, j); } } } return count; } };场景映射分析状态每个(i, j)坐标就是一个节点。边上下左右相邻的1节点之间存在边。DFS作用从一块陆地出发递归地访问并标记所有与之连通的陆地从而将整个“岛屿”从地图上“抹去”标记为已访问。主循环遍历所有格子每当遇到一个未被访问的陆地1就说明发现了一个新岛屿启动一次DFS。5.2 回溯法解决经典问题N皇后N皇后是回溯法的标杆问题。在N×N的棋盘上放置N个皇后使得它们互不攻击即任意两个皇后不在同一行、同一列或同一斜线上。#include iostream #include vector #include string using namespace std; vectorvectorstring solveNQueens(int n) { vectorvectorstring solutions; vectorstring board(n, string(n, .)); // 初始化棋盘全为. // 使用三个布尔数组进行快速冲突检测 vectorbool cols(n, false); // 列标记 vectorbool diag1(2 * n - 1, false); // 主对角线标记 (row - col n - 1) vectorbool diag2(2 * n - 1, false); // 副对角线标记 (row col) functionvoid(int) backtrack [](int row) { if (row n) { // 所有行都成功放置了皇后找到一个解 solutions.push_back(board); return; } for (int col 0; col n; col) { int idx1 row - col n - 1; // 主对角线索引 int idx2 row col; // 副对角线索引 // 检查当前位置是否安全 if (!cols[col] !diag1[idx1] !diag2[idx2]) { // 做出选择 board[row][col] Q; cols[col] diag1[idx1] diag2[idx2] true; // 递归到下一行 backtrack(row 1); // 撤销选择回溯 board[row][col] .; cols[col] diag1[idx1] diag2[idx2] false; } } }; backtrack(0); // 从第0行开始放置 return solutions; }优化技巧解析状态表示我们逐行放置皇后所以状态是当前行号row。冲突检测优化这是代码的精华。最笨的方法是每次放置前检查所有已放置的皇后。cols[col]记录第col列是否已被占用。diag1[idx1]记录“行号-列号”为常数的主对角线是否被占用。对于同一个主对角线上的格子row - col的值是相同的。加上n-1是为了让索引非负。diag2[idx2]记录“行号列号”为常数的副对角线是否被占用。时间复杂度通过这三个数组我们可以在O(1)时间内判断一个位置是否安全将回溯的复杂度从O(N!)优化到仍然是指数级但常数项小了很多的程度这是通过“空间换时间”的典型实践。6. DFS调试技巧与性能考量6.1 调试可视化递归过程当DFS代码出现错误尤其是回溯逻辑错误时最有效的调试方法之一是打印递归树。int depth 0; // 全局或引用传递的深度计数器 void dfs_debug(int u, string indent ) { visited[u] true; cout indent Enter dfs( u ) endl; // ... 处理当前节点 ... for (int v : graph[u]) { if (!visited[v]) { dfs_debug(v, indent ); // 增加缩进 } } cout indent Leave dfs( u ) endl; // visited[u] false; // 如果是寻路可能需要回溯 }通过缩进你可以清晰地看到递归的进入和退出顺序以及参数的传递对于理解递归流程和查找逻辑错误比如该回溯的没回溯非常有帮助。6.2 性能陷阱与优化思路栈溢出递归深度过深如链状图深度达到10^5量级。解决方案改用非递归迭代实现。如果必须用递归尝试调整系统栈大小不推荐平台相关。检查算法是否必要如此深有时问题可以转化为BFS。重复状态与剪枝在搜索空间巨大的问题中如八数码、某些DP的DFS记忆化如果不加处理DFS会探索大量重复状态导致超时。记忆化搜索Memoization将(状态参数)作为键计算结果作为值存储在一个哈希表如unordered_map中。在递归开始时先查表如果已经计算过直接返回结果。这是将DFS与动态规划结合的重要手段。unordered_mapstring, int memo; int dfs(state) { if (memo.count(state)) return memo[state]; // ... 计算过程 ... memo[state] result; return result; }可行性剪枝在递归过程中如果发现当前分支无论如何都不可能达到目标或成为最优解则提前返回终止该分支的搜索。例如在求和问题中如果当前和已经超过目标值就没必要继续加了。遍历顺序的影响对于寻找一条可行路径的问题DFS的顺序可能导致效率天差地别。一个启发式的策略是“优先选择可能性少的分支”这能更快地触底回溯减少搜索范围。例如在解数独时优先填充候选数字最少的格子。6.3 何时选择DFS而非BFS需要所有解/路径DFS回溯天然适合枚举所有可能性如全排列、组合、N皇后。判断连通性/可达性DFS和BFS都可以DFS代码通常更短。拓扑排序、有向图环检测DFS可以方便地利用“访问状态”未访问、访问中、已访问来检测回边从而判断环。寻找一条路径如果路径可能很深且不需要最短路径DFS可能更快找到一条。需要模拟“尝试-回溯”过程这是DFS的看家本领。反之如果问题明确要求最短路径、最少步数或者在无限图中搜索广度优先搜索BFS通常是更好的选择因为它按层推进找到的第一个解就是最短的。写DFS代码就像在问题的状态空间里进行一场有条不紊的探险。递归是你的勘探队visited数组是你的地图标记而回溯则是你安全返回基地的保障。从简单的全排列到复杂的图论问题其核心框架都是相通的定义状态、设计递归函数、确定终止条件、枚举选择、递归深入、回溯恢复。希望这个从简单示例出发的深度剖析能帮你彻底打通DFS的任督二脉下次再遇到需要搜索的问题时能够自信地写出正确、高效的代码。记住多画图多思考状态和边界调试时善用打印这些朴素的习惯比死记硬背模板要管用得多。
