文章目录深入浅出DFS深度优先搜索与 BFS广度优先搜索详解C实现前言一、图的存储先准备好“地图”二、BFS广度优先搜索——层层推进的“雷达扫描”1. 核心思想2. 执行过程3. C 代码实现4. 时间复杂度三、DFS深度优先搜索——不撞南墙不回头的“探险家”1. 核心思想2. 两种实现方式3. 递归版本代码极简4. 迭代版本使用栈5. 关键点提醒四、DFS vs BFS一张表讲透区别五、经典应用场景实战1. 求连通分量DFS 专属2. 无权图最短路径BFS 专属六、完整测试代码七、小结与学习建议深入浅出DFS深度优先搜索与 BFS广度优先搜索详解C实现前言在算法与数据结构的学习中**图Graph与树Tree**的遍历是绝对的核心基础。而支撑起这个基础的正是两大经典搜索算法DFSDepth-First Search深度优先搜索BFSBreadth-First Search广度优先搜索无论你是准备算法面试还是刷 LeetCode亦或是构建复杂的后端系统如网络爬虫、社交关系推荐这两个算法都无处不在。本文将从底层逻辑出发配合C 完整代码带你彻底吃透 DFS 与 BFS并搞懂它们到底在什么场景下使用。一、图的存储先准备好“地图”在开始遍历之前我们首先需要把图存起来。最常用的方式有两种邻接矩阵Adjacency Matrix适合稠密图。邻接表Adjacency List适合稀疏图更常用。为了直观起见本文统一使用邻接表进行存储图结构如下所示无向图示例0 —— 1 | / | | / | 2 —— 3在 C 中我们使用vectorint graph[n]来表示#includeiostream#includevector#includequeue#includestackusingnamespacestd;// 构建图voidbuildGraph(vectorintadj[],intn){// 添加边无向图adj[0].push_back(1);adj[0].push_back(2);adj[1].push_back(0);adj[1].push_back(2);adj[1].push_back(3);adj[2].push_back(0);adj[2].push_back(1);adj[2].push_back(3);adj[3].push_back(1);adj[3].push_back(2);}二、BFS广度优先搜索——层层推进的“雷达扫描”1. 核心思想BFS 从起点出发一圈一圈向外扩展。先访问离起点最近的节点再访问次近的以此类推。它的实现强制依赖于队列Queue——先进先出FIFO。2. 执行过程将起始节点入队并标记已访问。当队列不为空时取出队首节点并输出。将该节点的所有未被访问的邻居节点入队并标记。3. C 代码实现voidBFS(vectorintadj[],intstart,intn){vectorboolvisited(n,false);queueintq;visited[start]true;q.push(start);coutBFS 遍历顺序: ;while(!q.empty()){intnodeq.front();q.pop();coutnode ;// 遍历所有邻居for(intneighbor:adj[node]){if(!visited[neighbor]){visited[neighbor]true;q.push(neighbor);}}}coutendl;}4. 时间复杂度邻接表O(V E)邻接矩阵O(V²)三、DFS深度优先搜索——不撞南墙不回头的“探险家”1. 核心思想DFS 从起点出发沿着一条路一直走到底直到无法前进时再回溯Backtracking尝试另一条路。2. 两种实现方式递归实现最简洁显式栈实现防止栈溢出3. 递归版本代码极简voidDFS_recursive(vectorintadj[],vectorboolvisited,intnode){visited[node]true;coutnode ;for(intneighbor:adj[node]){if(!visited[neighbor]){DFS_recursive(adj,visited,neighbor);}}}4. 迭代版本使用栈voidDFS_iterative(vectorintadj[],intstart,intn){vectorboolvisited(n,false);stackintst;st.push(start);coutDFS (迭代) 遍历顺序: ;while(!st.empty()){intnodest.top();st.pop();if(visited[node])continue;visited[node]true;coutnode ;// 注意栈是逆序入栈但遍历顺序依然正确for(intneighbor:adj[node]){if(!visited[neighbor]){st.push(neighbor);}}}coutendl;}5. 关键点提醒递归 DFS 中访问标记发生在入栈递归调用前迭代 DFS 中需要出栈时再标记否则会出现重复入栈的问题。四、DFS vs BFS一张表讲透区别对比维度DFS深度优先BFS广度优先数据结构栈Stack / 递归队列Queue空间复杂度O(h)h 为树高最好O(w)w 为最大宽度通常较大能否求最短路径❌ 不能保证除非全遍历✅ 第一次到达即为最短路径无权图适用场景路径是否存在、拓扑排序、连通分量、回溯问题八皇后、迷宫最短路径、层级遍历、Web 爬虫、社交网络好友推荐遍历倾向纵深挖掘横向扩展五、经典应用场景实战1. 求连通分量DFS 专属intcountComponents(vectorintadj[],intn){vectorboolvisited(n,false);intcount0;for(inti0;in;i){if(!visited[i]){DFS_recursive(adj,visited,i);count;}}returncount;}2. 无权图最短路径BFS 专属voidshortestPathBFS(vectorintadj[],intstart,inttarget,intn){vectorintdist(n,-1);queueintq;dist[start]0;q.push(start);while(!q.empty()){intnodeq.front();q.pop();if(nodetarget){cout最短距离为: dist[node]endl;return;}for(intneighbor:adj[node]){if(dist[neighbor]-1){dist[neighbor]dist[node]1;q.push(neighbor);}}}}六、完整测试代码将以下代码整合在一起即可运行观察效果#includeiostream#includevector#includequeue#includestackusingnamespacestd;// 构建图省略见上文intmain(){intn4;vectorintadj[n];buildGraph(adj,n);// BFSBFS(adj,0,n);// DFS 递归vectorboolvisited(n,false);coutDFS (递归) 遍历顺序: ;DFS_recursive(adj,visited,0);coutendl;// DFS 迭代DFS_iterative(adj,0,n);return0;}预期输出BFS 遍历顺序: 0 1 2 3 DFS (递归) 遍历顺序: 0 1 2 3 DFS (迭代) 遍历顺序: 0 2 3 1注意由于邻接表插入顺序不同DFS 的递归和迭代输出顺序可能不同但都属于深度优先的有效遍历。七、小结与学习建议千万不要死记硬背代码理解“栈”和“队列”背后的数据结构逻辑。刷题时问自己三个问题这道题需要“最短路径”吗→ 优先 BFS这道题需要“回溯枚举”吗→ 优先 DFS树高会超过递归深度吗→ 改用迭代栈多画图、多 debug观察每一步栈/队列的变化这是最快的学习方式。DFS 与 BFS 是算法世界的“任督二脉”打通它们后续学习动态规划、图论、A搜索都将事半功倍。*