深度优先搜索(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>
using namespace std;
// 邻接表存储图
vector<vector<int>> adj;
// 标记节点是否被访问
vector<bool> visited;
// 递归实现 DFS
void dfs{
visited[u] = ;
cout << u << ;
( v : adj[u]){
(!visited[v]){
(v);
}
}
}
{
n = ;
adj.(n);
visited.(n, );
adj[].(); adj[].();
adj[].(); adj[].();
adj[].(); adj[].();
adj[].(); adj[].();
cout << ;
();
cout << endl;
;
}

