★ FEATURED ARTICLE 教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载DFS深度优先搜索与 BFS广度优先搜索是图与树结构中最基础、应用最广泛的两类遍历算法也是面试与工程实践中高频出现的核心考点。本文以 Learn-Algorithms 仓库中 5 Graph/DFS 和 BFS.md 文档为骨架结合仓库内二叉树、堆等源码实现系统讲解两种算法的核心思想、数据结构差异、代码模板、应用场景与典型面试题帮助读者从原理到实战一次性掌握 DFS/BFS。一、算法总览两条截然不同的搜索路径在 Learn-Algorithms 仓库的图论笔记中见 5 Graph/README.md图的遍历被明确划分为两类遍历广度优先 BFS、深度优先 DFS这两类算法解决的是同一个问题——如何系统地访问图中的所有顶点——但采取了完全相反的访问顺序策略。1.1 DFS深度优先一条路走到黑DFSDepth-First Search深度优先搜索以深度为准则从一个起点出发先沿着一条分支一直往下走直到走到目标节点如果走到了尽头没有达到目标且无路可走就**回溯backtrack**到上一步的状态换一条没走过的路继续探索。这正如原文档所述DFS深度优先搜索以深度为准则先一条路走到底直到达到目标没有达到目标又无路可走了那么则退回到上一步的状态走其他路。这便是回溯上来。核心关键词是回溯DFS 天然携带回溯特性这是它能够用于穷举所有路径寻找可行解的根本原因。1.2 BFS广度优先层层推进BFSBreadth-First Search广度优先搜索在面临一个路口时会把所有岔路口都记下来然后选择其中一个进入记录它的分支情况再返回去进入下一个岔路如此反复直到所有可达节点都被访问。BFS广度优先搜索在面临一个路口时把所有的岔路口都记下来然后选择其中一个进入然后将它的分路情况记录下来然后再返回来进入另外一个岔路并重复这样的操作。核心特征是按层扩散BFS 总是先访问距离起点最近的一层节点再逐层向外推进。1.3 一句话对比原文档要点DFS 用递归的形式用到了栈结构先进后出BFS 选取状态用队列的形式先进先出。维度DFS深度优先BFS广度优先访问顺序沿一条分支深入再回溯逐层向外扩散底层数据结构栈Stack递归调用栈天然是栈队列Queue先进先出空间复杂度节点数 N最坏 O(N)但通常较小只保存路径上的节点最坏 O(N)需保存整层节点是否天然找到最短路径否是无权图下首次访问即最短典型实现递归 / 显式栈显式队列循环适用场景连通性判断、路径枚举、回溯、拓扑排序、DFS 序最短路径、层序遍历、状态扩散、多源搜索二、核心差异的根源栈与队列的选择原文档一句话点破了两种算法的本质区别——DFS 用栈递归调用栈BFS 用队列。这一差异直接决定了算法的行为特征。2.1 为什么 DFS 需要栈先进后出LIFODFS 需要后进入的分支先处理。递归函数执行时系统调用栈天然满足先进后出函数 A 调用 BB 必须先返回A 才能继续。因此 DFS 用递归实现时无需显式建栈调用栈就是它的栈。如果用显式栈模拟 DFS核心模板如下// 显式栈版 DFS void dfs_iterative(int start) { Stack s; push(s, start); visited[start] 1; while (!stack_empty(s)) { int u pop(s); process(u); // 访问节点 for (int v : neighbors(u)) { if (!visited[v]) { visited[v] 1; push(s, v); // 后进先出实现深度优先 } } } }注意栈的 LIFO 特性决定了越晚压入的节点越先被访问这正是沿一条分支深入下去的驱动力。2.2 为什么 BFS 需要队列先进先出FIFOBFS 需要先记录的分支先处理只有队列的 FIFO 语义能满足先入队的节点距离更近的一层先被出队访问从而保证按层扩散。仓库中 4 Tree/1-二叉树 /btree/队列.h 实现了一个链式队列其注释与实现精确对应了 BFS 对数据结构的要求只在一段进行插入另一端删除元素该队列用head队头与tail队尾两个指针维护结构enQueue在队尾插入新节点、deQueue从队头弹出节点isEmpty通过q-head q-tail判断队列是否为空O(1) 完成入队出队操作// 入队加入到队尾 Status enQueue(Queue *q, ElemType e) { LinkQueue *newNode (LinkQueue *)malloc(sizeof(LinkQueue)); if (!newNode) return ERROR; newNode-elem e; newNode-next NULL; q-tail-next newNode; q-tail newNode; // 队尾插入 q-length; return OK; } // 出队队头弹出 Status deQueue(Queue *q, ElemType *e) { LinkQueue *p q-head-next; if (!p) return ERROR; // 队列空 if (e) *e p-elem; LinkQueue *temp p-next; q-head-next temp; if (p q-tail) // 只有一个元素时防止队尾指针丢失 q-tail q-head; free(p); q-length--; return OK; }源码中还注意到顺序存储队列的经典缺陷4 Tree/1-二叉树 /btree/队列.h 注释在队列采用顺序存储时有一个毛病就是队列操作一段时间后头指针到了队列容器的尾部而头指针前面的容器内存不可用了造成内存极大的浪费这个问题可以通过循环队列来解决。但是在链式队列上则不存在这样的问题这一细节对理解 BFS 工程实现很有价值大规模图遍历时若用数组队列会频繁扩容浪费内存链式队列或循环队列是更稳妥的选择。三、二叉树上的 DFS 与 BFS仓库源码实战Learn-Algorithms 仓库在二叉树部分给出了 DFS 与 BFS 的完整 C 语言实现是理解两种算法最直观的练武场。3.1 二叉树结构定义仓库 4 Tree/1-二叉树 /btree/bintree.c 使用链表方式构建二叉树typedef struct BiTNode { char item; struct BiTNode *lChild, *rChild; } BiTNode, *BiTree;节点只有左右两个分支这让 DFS 和 BFS 的实现变得极其清晰。3.2 DFS 在二叉树上的三种体现前序、中序、后序遍历二叉树的先序、中序、后序遍历都是 DFS——它们只是改变了访问节点与递归进入子树的先后顺序。仓库 bintree.c 中三种遍历全部采用递归即调用栈实现// 前序遍历根 - 左 - 右先访问后递归 int PreOrderTraverse(BiTree T) { if (T) { printf(%c\n, T-item); PreOrderTraverse(T-lChild); PreOrderTraverse(T-rChild); } return 0; } // 中序遍历左 - 根 - 右 int InOrderTraverse(BiTree T) { if (T) { InOrderTraverse(T-lChild); printf(%c\n, T-item); InOrderTraverse(T-rChild); } return 0; } // 后序遍历左 - 右 - 根先递归最后访问 int PostOrderTraverse(BiTree T) { if (T) { PostOrderTraverse(T-lChild); PostOrderTraverse(T-rChild); printf(%c\n, T-item); } return 0; }这三个函数印证了原文档的论断DFS 用递归的形式用到了栈结构。每一次递归调用进入更深一层返回时自然完成回溯。3.3 BFS 在二叉树上的体现层序遍历二叉树的层序遍历Level Order就是 BFS。仓库 bintree.c 中LevelOrderTraverse用上述链式队列实现了真正的先进先出逐层访问// 广度优先遍历队列实现 int LevelOrderTraverse(BiTree T) { if (T) { Queue queue; initQueue(queue); BiTree u (BiTree)malloc(sizeof(BiTNode)); enQueue(queue, T); // 根节点先入队 while (!isEmpty(queue)) { deQueue(queue, u); // 队头出队并访问 printf(%c, u-item); if (u-lChild) enQueue(queue, u-lChild); // 左孩子入队 if (u-rChild) enQueue(queue, u-rChild); // 右孩子入队 } } return 0; }对照队列实现队列.h 与 bintree.c可清晰看到 BFS 的完整调用链enQueue入队 →isEmpty判空 →deQueue出队 → 访问 → 孩子节点入队。由于先入队的上一层节点总是先出队访问顺序天然按层展开。仓库 bintree.c 的main函数还给出了完整的可运行流程先按先序方式创建二叉树输入空格表示空节点随后依次打印前序、中序、后序与层序遍历结果printf(创建二叉树输入\空格\创建空节点先序方式建立二叉树:\n); binaryTree CreateBiTree(); printf(前序遍历:\n); PreOrderTraverse(binaryTree); printf(中序遍历:\n); InOrderTraverse(binaryTree); printf(后序遍历:\n); PostOrderTraverse(binaryTree); printf(层序遍历:\n); LevelOrderTraverse(binaryTree);四、通用图上的 DFS 与 BFS 模板图比二叉树复杂在于可能存在环且一个节点可能有多个邻居。因此通用模板必须引入visited数组防止重复访问。4.1 通用 DFS 模板递归版void dfs(int u, int visited[], Graph *g) { visited[u] 1; // 标记已访问防环 process(u); // 访问/处理节点 for (int i 0; i g-degree[u]; i) { int v g-adj[u][i]; if (!visited[v]) { dfs(v, visited, g); // 深入下一层 } } }4.2 通用 BFS 模板void bfs(int start, int visited[], Graph *g) { Queue q; initQueue(q); enQueue(q, start); visited[start] 1; while (!isEmpty(q)) { int u; deQueue(q, u); process(u); // 访问节点 for (int i 0; i g-degree[u]; i) { int v g-adj[u][i]; if (!visited[v]) { visited[v] 1; enQueue(q, v); // 未访问邻居入队 } } } }要点visited标记应在入队/压栈时设置而非出队时设置否则同一节点可能被重复入队破坏复杂度 O(VE) 的保证。五、应用场景何时用 DFS何时用 BFS5.1 DFS 的典型场景连通性判断判断两个节点是否连通、统计连通分量个数路径枚举与回溯全排列、N 皇后、数独、组合问题仓库 8 Algorithms Analysis/回溯法.md 有专门讲解拓扑排序以 DFS 后序顺序逆序输出可得拓扑序见仓库 5 Graph/拓扑排序.md二分图判定、强连通分量、桥与割点Tarjan 系算法均基于 DFS树上的 DFS 序、子树统计将子树问题转化为区间问题。5.2 BFS 的典型场景无权图最短路径BFS 第一次访问到某节点时走过的步数即最短步数层序遍历二叉树按层输出、逐层统计节点数状态空间搜索迷宫、拼图用状态作为节点、操作作为边BFS 保证找到步数最少的解多源扩散问题多起点同时入队如感染扩散腐烂橘子类问题拓扑排序Kahn 算法基于入度与队列实现。仓库 5 Graph/README.md 列出了图的工业界应用场景导航路径规划、任务调度、社区发现、匹配等这些场景背后的路径搜索与连通性分析本质上都由 DFS/BFS 支撑导航路径规划用户选择开始地点和目的地之后导航软件给出路程最短、不走高速、时长最短等方案其中路程最短正是 BFS 类算法加权场景延伸为 Dijkstra的应用而连通性、社区发现则依赖 DFS 遍历能力。六、复杂度分析与优化技巧6.1 时间复杂度DFS每个节点访问一次、每条边检查一次时间复杂度O(V E)V 为顶点数E 为边数。BFS同样每个节点入队出队各一次、每条边检查一次时间复杂度也是O(V E)。两者渐进复杂度相同差异体现在空间与结果特性上。6.2 空间复杂度与优化DFS递归空间 O(树高)最坏退化为链时 O(N)显式栈版可避免系统调用栈溢出风险在深图中更安全BFS空间为最宽一层的节点数星型图中可达 O(N)优化技巧用visited位图/哈希代替布尔数组降低空间BFS 双向扩展从起点和终点同时 BFS相遇即停止可将搜索空间从 b^d 降到约 2·b^(d/2)DFS 加剪枝在递归前判断是否满足约束大幅减少无效分支是回溯法的核心优化见 8 Algorithms Analysis/回溯法.md。七、面试高频题与 LeetCode 对照类型算法经典题目二叉树遍历DFS前序/中序/后序遍历递归迭代两种写法层序遍历BFS二叉树层序遍历、锯齿形层序遍历图连通性DFS/BFS岛屿数量、省份数量、被围绕的区域最短路径BFS单词接龙、打开转盘锁、二进制矩阵中的最短路径回溯/枚举DFS全排列、子集、组合总和、N 皇后拓扑排序DFS/BFS课程表判断有向图是否有环仓库 9 Algorithms Job Interview 目录收录了大量面试代码其中 codes/7 bianrytree/binary_search.c 等文件可作为练习素材。面试中常考的核心考点包括递归版与迭代版互转能写出 DFS 的显式栈版本和 BFS 的队列版本visited 标记时机解释为何入队时标记优于出队时标记复杂度分析准确说出 O(VE) 与空间占用场景判别最短路径/逐层扩散优先 BFS枚举/回溯/连通性优先 DFS。八、小结对比项DFSBFS搜索策略深度优先走到底再回溯广度优先逐层扩散数据结构栈递归调用栈队列FIFO是否适合找最短路径否是无权图是否适合枚举/回溯是否复杂度O(VE)O(VE)空间O(树高/路径长)O(最宽层节点数)DFS 与 BFS 是算法学习的基石也是无数高级算法Dijkstra、A*、Tarjan、拓扑排序、最大流的共同底座。掌握本节内容后可进一步阅读仓库中的 5 Graph/README.md 了解图论整体框架、5 Graph/最短路径.md 学习 BFS 在加权图上的延伸Dijkstra并通过 4 Tree/1-二叉树 /btree/bintree.c 亲手运行一遍完整代码完成从理论到实战的闭环。赞分享教程【免费下载链接】Learn-Algorithms算法学习笔记项目地址https://gitcode.com/gh_mirrors/le/Learn-Algorithms点击查看免费下载相关推荐InternVL Stage2预训练原理对比学习生成任务的双路对齐InternVL Stage2预训练原理对比学习生成任务的双路对齐 InternVL 是一个接近 GPT 4o 表现的开源多模态大模型系列其 StageLeetCode 搜索算法指南DFS、BFS、双向搜索与状态空间实战解析LeetCode 搜索算法指南DFS、BFS、双向搜索与状态空间实战解析 导读 本文是 leetcode 题解仓库中《搜索篇上》的完整技术指南聚焦算法面文档教程知识库ta4j指标系统深度剖析从简单移动平均到复杂艾略特波浪分析ta4j指标系统深度剖析从简单移动平均到复杂艾略特波浪分析 ta4j是一个强大的Java技术分析库提供了从基础到高级的完整指标系统帮助开发者构建专业的交易金融科技上一篇Compiler Explorer 编译器配置指南.properties 文件的组结构、短链接兼容与自动化实践下一篇Pimcore分类存储中KeyGroupRelation和CollectionGroupRelation的sorter属性NULL值问题解析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
阅读完成 · 觉得有帮助？
