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

Ne0inhk

24 Mar 2026 — 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. 递归实现（最常用）

递归实现的核心逻辑：

访问当前节点，标记为已访问；
遍历当前节点的所有邻接节点；
对每个未访问的邻接节点，递归调用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。核心逻辑与递归一致，只是将递归调用栈替换为手动维护的栈。

非递归实现步骤：

将起始节点压入栈，标记为已访问；
弹出栈顶节点，访问该节点；
将该节点的所有未访问邻接节点压入栈（注意：为保证遍历顺序与递归一致，需逆序压入，因为栈是先进后出）；
重复步骤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的关键是理解“探索-回溯”的思想，以及如何通过标记和撤销操作控制遍历过程。

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

Ne0inhk