图的基本遍历DFS与BFS

1. 引言图是一种非常重要的数据结构广泛应用于社交网络、地图导航、网页链接分析等领域。图的遍历是最基础的操作之一主要有两种方式深度优先搜索 (Depth First Search, DFS)—— 沿着一条路径走到底再回溯。广度优先搜索 (Breadth First Search, BFS)—— 一层一层向外扩展。本文将详细讲解这两种算法的原理、实现、区别及应用场景并附上 C 代码示例。2. 图的存储方式在讨论遍历之前我们需要先知道图是如何存储在计算机中的。常用的两种方式2.1 邻接矩阵使用一个二维数组adj[n][n]adj[u][v] 1表示存在一条边从 u 到 v。优点判断两点是否相连 O(1)缺点空间复杂度 O(n²)不适合稀疏图边数远小于 n²2.2 邻接表使用一个数组vectorint g[n]g[u]存储所有从 u 出发能直接到达的节点。优点空间复杂度 O(nm)适合大多数竞赛题缺点判断两点是否相连需要遍历链表本文所有代码均采用邻接表存储。intn,m;// n个顶点m条边vectorvectorintg(n1);// 1-based// 读入边for(inti0;im;i){intu,v;cinuv;g[u].push_back(v);// 如果是无向图还需要 g[v].push_back(u);}3. 深度优先搜索 (DFS)3.1 基本思想从起点出发沿着一条未访问过的边走到新节点递归地进行下去直到没有未访问的邻居然后回溯到上一个节点继续探索其他分支。3.2 算法步骤标记当前节点为已访问。输出或处理当前节点。遍历当前节点的所有邻居如果邻居未被访问则递归访问该邻居。返回回溯。3.3 递归实现voiddfs(intu,vectorboolvis,constvectorvectorintg){vis[u]true;coutu ;for(intv:g[u]){if(!vis[v]){dfs(v,vis,g);}}}调用示例vectorboolvis(n1,false);dfs(1,vis,g);3.4 非递归实现使用栈递归可能导致栈溢出当图深度很大时比如 1e5 的链此时可以用显式栈模拟voiddfs_stack(intstart,constvectorvectorintg){vectorboolvis(g.size(),false);stackintst;st.push(start);vis[start]true;coutstart ;while(!st.empty()){intust.top();boolhasNextfalse;for(intv:g[u]){if(!vis[v]){vis[v]true;coutv ;st.push(v);hasNexttrue;break;}}if(!hasNext)st.pop();}}3.5 复杂度时间复杂度O(n m)每个节点和每条边恰好被访问一次。空间复杂度O(n)递归栈深度最坏为 n或显式栈大小。3.6 应用场景连通分量检测拓扑排序后序 DFS强连通分量Tarjan 算法寻找路径 / 回溯问题4. 广度优先搜索 (BFS)4.1 基本思想从起点出发先访问所有距离为 1 的节点再访问距离为 2 的节点依此类推。使用队列来实现。4.2 算法步骤将起点入队标记为已访问。当队列非空时取出队首节点 u输出或处理 u。遍历 u 的所有邻居 v如果 v 未被访问则标记 v 并让 v 入队。重复直到队列为空。4.3 代码实现voidbfs(intstart,constvectorvectorintg){vectorboolvis(g.size(),false);queueintq;q.push(start);vis[start]true;while(!q.empty()){intuq.front();q.pop();coutu ;for(intv:g[u]){if(!vis[v]){vis[v]true;q.push(v);}}}}4.4 计算最短距离无权图在 BFS 过程中可以记录每个节点到起点的距离vectorintdist(g.size(),-1);dist[start]0;queueintq;q.push(start);while(!q.empty()){intuq.front();q.pop();for(intv:g[u]){if(dist[v]-1){dist[v]dist[u]1;q.push(v);}}}4.5 复杂度时间复杂度O(n m)空间复杂度O(n)队列4.6 应用场景无权图的最短路径层次遍历如树的层序二分图判定寻找连通块5. DFS 与 BFS 的对比特性DFSBFS数据结构栈递归或显式栈队列访问顺序深度优先一条路走到黑广度优先按层扩展最短路径不保证保证无权图空间复杂度最坏O(n)递归深度O(n)队列宽度实现复杂度递归简洁非递归稍复杂队列实现简单典型应用回溯、连通分量、拓扑排序最短路径、层序遍历6. 例题实战洛谷 P5318 【深基18.例3】查找文献6.1 题目描述给定 n 篇文章1~n和 m 条引用关系有向边 X→Y 表示 X 引用 Y。从文章 1 出发按照“先看编号较小的文章”的规则分别输出 DFS 和 BFS 的遍历结果。6.2 解题要点建图后需要对每个节点的邻接表排序以保证编号小的优先访问。DFS 注意可能递归深度过大可以使用非递归栈或设置栈空间。BFS 直接使用队列。6.3 参考代码#includebits/stdc.husingnamespacestd;voiddfs(intu,vectorboolvis,constvectorvectorintg){vis[u]true;coutu ;for(intv:g[u]){if(!vis[v])dfs(v,vis,g);}}voidbfs(intstart,constvectorvectorintg){vectorboolvis(g.size(),false);queueintq;q.push(start);vis[start]true;while(!q.empty()){intuq.front();q.pop();coutu ;for(intv:g[u]){if(!vis[v]){vis[v]true;q.push(v);}}}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,m;cinnm;vectorvectorintg(n1);for(inti0;im;i){intx,y;cinxy;g[x].push_back(y);}// 排序保证编号小的优先for(inti1;in;i){sort(g[i].begin(),g[i].end());}vectorboolvis(n1,false);dfs(1,vis,g);cout\n;bfs(1,g);cout\n;return0;}7. 常见问题及优化7.1 如何处理非连通图如果需要遍历整张图所有连通分量可以在主函数中循环每个节点若未访问则调用 DFS/BFSfor(inti1;in;i){if(!vis[i])dfs(i,vis,g);}7.2 递归 DFS 爆栈怎么办改用非递归栈见上文。或者在编译时设置栈大小如-Wl,--stack,104857600但不推荐依赖环境。竞赛中常用非递归写法。7.3 如何记录 DFS 的进入和离开时间inttimer0;vectorinttin,tout;voiddfs(intu){tin[u]timer;for(intv:g[u]){if(!vis[v])dfs(v);}tout[u]timer;}这在 Tarjan 算法中非常有用。8. 总结DFS 和 BFS 是图论最基础的两个遍历算法必须熟练掌握。DFS 适合递归思想的题目如回溯、连通性注意栈深度。BFS 适合求无权图最短路径、层次遍历。在实际代码中记得根据题目要求对邻接表排序、处理不连通图等细节。欢迎指导如果有任何疑问留言讨论。