深度优先搜索（DFS）详解及C++实现

Ne0inhk

— 11 min read

深度优先搜索（DFS）详解及C++实现

一、什么是深度优先搜索（DFS）？

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。其核心思想是：尽可能深地搜索图的分支，当某条分支搜索到尽头无法继续前进时，回溯到上一个节点，再选择另一条未探索的分支继续搜索，直到所有节点都被访问完毕。

可以用一个生动的比喻理解DFS：想象你走进一个迷宫，每次遇到岔路时，随机选择一条路一直走，直到走到死胡同（无法继续前进），然后沿原路返回上一个岔路，选择另一条未走过的路继续探索，直到找到出口或遍历完整个迷宫。

DFS的实现通常依赖栈（Stack）这种数据结构（手动实现时），或者直接利用递归函数调用栈（更简洁，也是最常用的方式）。递归实现的本质是将每次的节点访问和回溯过程交给函数栈来管理，无需手动维护栈结构。

二、DFS的核心特性与适用场景

1. 核心特性

  • 不撞南墙不回头：优先深入探索当前分支，而非横向遍历同级节点；
  • 回溯思想：探索到尽头后，返回上一节点继续探索其他分支，需要记录节点访问状态（避免重复访问）；
  • 空间复杂度：取决于递归深度或栈的大小，最坏情况下为O(n)（n为节点数）；
  • 时间复杂度：遍历图时，时间复杂度为O(V+E)（V为顶点数，E为边数）；遍历树时，为O(n)（树中边数为n-1）。

2. 适用场景

  • 图的遍历（连通分量查找、拓扑排序等）；
  • 树的遍历（前序、中序、后序遍历，路径搜索等）；
  • 迷宫问题（最短路径不适用，DFS不保证最短，需用BFS；但可用于判断是否存在路径）；
  • 排列组合问题（如全排列、子集生成等）；
  • 回溯法解决的经典问题（如N皇后、数独求解等）。

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

DFS的实现分为递归实现和非递归实现（手动栈）。递归实现代码简洁，易于理解；非递归实现则更灵活，可避免递归深度过大导致的栈溢出问题。下面以「无向图的遍历」和「树的前序遍历」为例，讲解两种实现方式。

1. 递归实现（最常用）

递归实现的核心逻辑：

  1. 访问当前节点，标记为已访问；
  2. 遍历当前节点的所有邻接节点；
  3. 对每个未访问的邻接节点，递归调用DFS函数。

案例1：无向图的DFS遍历

假设我们有如下无向图：

0 → 1 → 2
0 → 3 → 4

用邻接表存储图（邻接表是图的常用存储方式，适合稀疏图），然后通过递归DFS遍历所有节点。

#include<iostream>#include<vector>usingnamespace std;// 邻接表存储图 vector<vector<int>> adj;// 标记节点是否被访问 vector<bool> visited;// 递归实现DFSvoiddfs(int u){// 标记当前节点为已访问 visited[u]=true;// 访问当前节点（此处为打印节点值） cout << u <<" ";// 遍历当前节点的所有邻接节点for(int v : adj[u]){// 如果邻接节点未被访问，递归调用DFSif(!visited[v]){dfs(v);}}}intmain(){// 图的节点数int n =5;// 初始化邻接表和访问标记数组 adj.resize(n); visited.resize(n,false);// 构建无向图 adj[0].push_back(1); adj[1].push_back(0); adj[1].push_back(2); adj[2].push_back(1); adj[0].push_back(3); adj[3].push_back(0); adj[3].push_back(4); adj[4].push_back(3); cout <<"DFS遍历结果（递归）：";// 从节点0开始遍历（若图不连通，需遍历所有未访问节点）dfs(0); cout << endl;return0;}

输出结果：
DFS遍历结果（递归）：0 1 2 3 4

说明：从节点0出发，先深入探索1→2分支，回溯后再探索3→4分支，最终遍历所有节点。

案例2：二叉树的前序遍历（DFS）

二叉树的前序遍历（根→左→右）是DFS的典型应用，递归实现非常简洁。

#include<iostream>usingnamespace std;// 二叉树节点定义structTreeNode{int val; TreeNode* left; TreeNode* right;TreeNode(int x):val(x),left(nullptr),right(nullptr){}};// 递归实现前序遍历（DFS）voidpreorderDFS(TreeNode* root){// 递归终止条件：节点为空if(root ==nullptr){return;}// 访问根节点 cout << root->val <<" ";// 递归遍历左子树preorderDFS(root->left);// 递归遍历右子树preorderDFS(root->right);}intmain(){// 构建一棵二叉树：// 1// \ // 2// /// 3 TreeNode* root =newTreeNode(1); root->right =newTreeNode(2); root->right->left =newTreeNode(3); cout <<"二叉树前序遍历（DFS）：";preorderDFS(root); cout << endl;// 释放内存（简化处理，实际应手动遍历释放）delete root->right->left;delete root->right;delete root;return0;}

输出结果：
二叉树前序遍历（DFS）：1 2 3

2. 非递归实现（手动栈）

当递归深度过大时（如遍历深度为1e4的树），会导致栈溢出（C++默认递归栈大小有限），此时需要用手动栈实现DFS。核心逻辑与递归一致，只是将递归调用栈替换为手动维护的栈。

非递归实现步骤：

  1. 将起始节点压入栈，标记为已访问；
  2. 弹出栈顶节点，访问该节点；
  3. 将该节点的所有未访问邻接节点压入栈（注意：为保证遍历顺序与递归一致，需逆序压入，因为栈是先进后出）；
  4. 重复步骤2-3，直到栈为空。

案例1：无向图的DFS遍历（非递归）

#include<iostream>#include<vector>#include<stack>usingnamespace std; vector<vector<int>> adj; vector<bool> visited;// 非递归实现DFS（手动栈）voiddfsNonRecursive(int start){ stack<int> st;// 压入起始节点，标记为已访问 st.push(start); visited[start]=true;while(!st.empty()){// 弹出栈顶节点int u = st.top(); st.pop();// 访问当前节点 cout << u <<" ";// 遍历邻接节点（逆序压入，保证遍历顺序与递归一致）for(auto it = adj[u].rbegin(); it != adj[u].rend();++it){int v =*it;if(!visited[v]){ visited[v]=true; st.push(v);}}}}intmain(){int n =5; adj.resize(n); visited.resize(n,false);// 构建无向图（同递归案例） adj[0].push_back(1); adj[1].push_back(0); adj[1].push_back(2); adj[2].push_back(1); adj[0].push_back(3); adj[3].push_back(0); adj[3].push_back(4); adj[4].push_back(3); cout <<"DFS遍历结果（非递归）：";dfsNonRecursive(0); cout << endl;return0;}

输出结果：
DFS遍历结果（非递归）：0 1 2 3 4

说明：这里对邻接节点逆序遍历（rbegin()和rend()），是因为栈是“先进后出”的。如果直接正序压入，遍历顺序会变成0→3→4→1→2，虽然也是DFS，但与递归实现的顺序不一致（不影响遍历完整性，仅影响顺序）。

案例2：二叉树的前序遍历（非递归DFS）

#include<iostream>#include<stack>usingnamespace std;structTreeNode{int val; TreeNode* left; TreeNode* right;TreeNode(int x):val(x),left(nullptr),right(nullptr){}};// 非递归实现前序遍历（DFS）voidpreorderDFSNonRecursive(TreeNode* root){if(root ==nullptr){return;} stack<TreeNode*> st;// 压入根节点 st.push(root);while(!st.empty()){// 弹出栈顶节点，访问 TreeNode* node = st.top(); st.pop(); cout << node->val <<" ";// 注意：先压右子树，再压左子树（栈先进后出，保证左子树先访问）if(node->right !=nullptr){ st.push(node->right);}if(node->left !=nullptr){ st.push(node->left);}}}intmain(){// 构建与递归案例相同的二叉树 TreeNode* root =newTreeNode(1); root->right =newTreeNode(2); root->right->left =newTreeNode(3); cout <<"二叉树前序遍历（非递归DFS）：";preorderDFSNonRecursive(root); cout << endl;// 释放内存delete root->right->left;delete root->right;delete root;return0;}

输出结果：
二叉树前序遍历（非递归DFS）：1 2 3

四、DFS的经典应用：回溯法求解N皇后问题

DFS的核心是“探索-回溯”，而回溯法是DFS的一种延伸应用，常用于解决“选择-验证-回溯-再选择”的组合优化问题。N皇后问题是回溯法的经典案例：在n×n的棋盘上放置n个皇后，使得任意两个皇后不处于同一行、同一列或同一斜线上。

#include<iostream>#include<vector>#include<string>usingnamespace std; vector<vector<string>> result;// 存储所有合法解// 检查当前位置(row, col)是否可以放置皇后boolisValid(int n,int row,int col, vector<string>& board){// 检查同一列是否有皇后for(int i =0; i < row;++i){if(board[i][col]=='Q'){returnfalse;}}// 检查左上到右下的斜线（左上方向）for(int i = row -1, j = col -1; i >=0&& j >=0;--i,--j){if(board[i][j]=='Q'){returnfalse;}}// 检查右上到左下的斜线（右上方向）for(int i = row -1, j = col +1; i >=0&& j < n;--i,++j){if(board[i][j]=='Q'){returnfalse;}}returntrue;}// DFS回溯函数：当前处理第row行voidbacktrack(int n,int row, vector<string>& board){// 递归终止条件：所有行都处理完毕（找到一个合法解）if(row == n){ result.push_back(board);return;}// 遍历当前行的每一列，尝试放置皇后for(int col =0; col < n;++col){if(isValid(n, row, col, board)){// 选择：在当前位置放置皇后 board[row][col]='Q';// 探索：处理下一行backtrack(n, row +1, board);// 回溯：撤销选择，恢复原状 board[row][col]='.';}}}// 求解N皇后问题 vector<vector<string>>solveNQueens(int n){ result.clear();// 初始化棋盘：n行n列，全部为'.' vector<string>board(n,string(n,'.'));backtrack(n,0, board);return result;}// 打印所有解voidprintResult(const vector<vector<string>&> result){for(auto& solution : result){ cout <<"====================="<< endl;for(auto& row : solution){ cout << row << endl;}}}intmain(){int n =4;// 求解4皇后问题 vector<vector<string>> solutions =solveNQueens(n); cout << n <<"皇后问题共有 "<< solutions.size()<<" 个解："<< endl;printResult(solutions);return0;}

输出结果（4皇后问题的2个解）：
4皇后问题共有 2 个解：

.Q…
…Q
Q…
…Q.

…Q.
Q…
…Q
.Q…

说明：该代码通过DFS回溯，逐行尝试放置皇后，每放置一个皇后就验证合法性，若合法则继续探索下一行，若不合法则回溯到上一行重新选择列。最终遍历出所有合法的放置方案。

五、DFS的常见注意事项

  • 避免重复访问：必须使用visited数组（或其他标记方式）标记已访问的节点，否则会陷入无限循环（尤其是图中有环的情况）；
  • 递归深度控制：递归实现时，若问题规模过大（如n=1e4），会导致栈溢出，此时需改用非递归实现；
  • 回溯的撤销操作：回溯法中，每次选择后必须撤销选择（如N皇后问题中恢复board[row][col]为’.'），否则会影响后续探索；
  • 邻接表的构建：图的DFS遍历中，邻接表比邻接矩阵更高效（空间复杂度O(V+E) vs O(V²)），适合稀疏图；
  • 多连通分量处理：若图不连通，需遍历所有节点，对每个未访问的节点调用DFS（如：for(int i=0; i<n; i++) if(!visited[i]) dfs(i);）。

六、总结

DFS是一种基于“深度优先、回溯探索”的遍历算法，核心依赖栈（递归栈或手动栈）实现。其代码简洁、思想直观，广泛应用于图遍历、树遍历、排列组合、回溯优化等问题。

在C++实现中，递归版本适合小规模问题，代码易写；非递归版本适合大规模问题，避免栈溢出。学习DFS的关键是理解“探索-回溯”的思想，以及如何通过标记和撤销操作控制遍历过程。

Read more

【LeetCode_27】移除元素

【LeetCode_27】移除元素

刷爆LeetCode系列 * LeetCode27题： * github地址 * 前言 * 题目描述 * 题目思路分析 * 代码实现 * 算法代码优化 LeetCode27题： github地址 有梦想的电信狗 前言 本文用C++实现LeetCode 第27题 题目描述 题目链接：https://leetcode.cn/problems/remove-element/ 题目思路分析 目标分析： 1. 将数组中等于val的元素移除 2. 原地移除，意味着时间复杂度为O(n)，空间复杂度为O(1) 3. 返回nums中与val值不同的元素个数 思路：双指针 * src：用于扫描元素，从待扫描元素的第一个开始，因此初始下标为0 * dst：指向数组中，最后一个位置正确的元素的下标，因此初始值为-1 * count：记录赋值的次数，赋值的次数即为数组中与val值不同的元素个数，初始值为0 操作： * nums[

By Ne0inhk
一文彻底搞清楚数据结构之快速排序和归并排序的深入优化

一文彻底搞清楚数据结构之快速排序和归并排序的深入优化

🔥承渊政道：个人主页 ❄️个人专栏: 《C语言基础语法知识》《数据结构与算法初阶》 ✨逆境不吐心中苦,顺境不忘来时路!🎬 博主简介: 前言:前面小编已经介绍八大排序算法的基本思想和实现方法!但关于其中的快速排序和归并排序还有一些细节可以优化!接下来跟着小编来看看快速排序和归并排序的深入优化,学习一下优化完之后,具体在实际中的应用!废话不多说,下面跟着小编的节奏🎵一起学习吧！ 目录 * 1.快速排序性能的关键点分析 * 1.1三路划分算法思想讲解 * 1.2hoare和lomuto和三路划分单趟排序代码分析 * 1.3三种快排单趟排序运⾏结果分析 * 2.排序数组OJ题 * 2.1lomuto的快速排序跑排序数组OJ题 * 2.2hoare的快速排序跑排序数组OJ题 * 2.3三路划分的快速排序跑排序数组OJ题 * 2.4introsort的快速排序跑排序数组OJ题 * 3.外排序介绍 * 3.1创建随机数据⽂件的代码 * 3.2⽂件归并排序思路分析 * 3.3⽂件归并排序代码实现 * 3.4非递归版

By Ne0inhk
动态规划 路径类 DP 入门：3 道经典例题（最小路径和 + 迷雾森林 + 过河卒）全解析

动态规划 路径类 DP 入门：3 道经典例题（最小路径和 + 迷雾森林 + 过河卒）全解析

文章目录 * 矩阵的最小路径和 * 迷雾森林 * 过河卒 路径类 dp 是线性 dp 的⼀种，它是在⼀个 n × m 的矩阵中设置⼀个⾏⾛规则，研究从起点⾛到终点的 ⽅案数、最⼩路径和或者最⼤路径和等等的问题。 ⼊⻔阶段的《数字三⻆形》其实就是路径类 dp。 矩阵的最小路径和 题目描述 题目解析 1、状态表示 dp[i][j]表示从[1 1]格子走到[i j]格子时，所有方案下的最小路径和。 2、状态转移方程 我们还是以最后一步来推导状态转移方程，走到最后一个格子dp[n][m]

By Ne0inhk