DFS，BFS应用_m0_55997161的博客

DFS，BFS应用 · public static void dfs(TreeNode root) { · if (root == null) { · return; · } · dfs(root.left); · dfs(root.right);. DFS，BFS应用 whlie(true){learn} 2021-12-0715:22:07 457 收藏 分类专栏： 算法 文章标签： 深度优先 宽度优先 算法 版权声明：本文为博主原创文章，遵循CC4.0BY-SA版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/m0_55997161/article/details/121767607 版权 算法 专栏收录该内容 24篇文章 0订阅 订阅专栏 DFS遍历模板  publicstaticvoiddfs(TreeNoderoot){ if(root==null){ return; } dfs(root.left); dfs(root.right); BFS遍历模板 publicstaticvoidbfs(TreeNoderoot){ Queuequeue=newArrayDeque<>(); queue.add(root); while(!queue.isEmpty()){ TreeNodenode=queue.poll(); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } } 在大多数情况下我们遍历使用DFS，BFS主要使用在层序遍历和最短路径(无权)上 二叉树的前,中,后序遍历 classSolution{ publicListpreorderTraversal(TreeNoderoot){ Listlist=newArrayList(); preOrder(root,list); returnlist; } //前序 publicstaticvoidpreOrder(TreeNoderoot,Listlist){ if(root==null){ return; } list.add(root.val); preOrder(root.left,list); preOrder(root.right,list); } //中序 publicstaticvoidmid(TreeNoderoot,Listlist){ if(root==null){ return; } mid(root.left,list); list.add(root.val); mid(root.right,list); } //后序 publicstaticvoidafter(TreeNoderoot,Listlist){ if(root==null){ return; } after(root.left,list); after(root.right,list); list.add(root.val); } } 二叉树的最大深度 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

3 /\ 920 /\ 157 它的最大深度为3  //DFS //自底向上 classSolution{ publicintmaxDepth(TreeNoderoot){ if(root==null){ return0; } intleftlen=maxDepth(root.left); intrightlen=maxDepth(root.right); returnMath.max(leftlen,rightlen)+1; } } //BFS //自顶向下 classSolution{ publicintmaxDepth(TreeNoderoot){ if(root==null){ return0; } Queuequeue=newLinkedList(); queue.offer(root); intans=0; //判断当前层 while(!queue.isEmpty()){ intsize=queue.size(); //将当前层的节点加入队列 while(size>0){ TreeNodenode=queue.poll(); if(node.left!=null){ queue.offer(node.left); } if(node.right!=null){ queue.offer(node.right); } size--; } //每循环一层，深度+1 ans++; } returnans; } } 对称二叉树 1 /\ 22 /\/\ 3443 如果是一颗对称二叉树说明，他要么是一颗空树，要么是一颗满二叉树而且左右子树的根节点不为空且相等，满足左子树左子节点等于右子树的右子节点，左子树的右子节点等于右子树的左子节点 classSolution{ publicbooleanisSymmetric(TreeNoderoot){ //空树必是对称 if(root==null){ returntrue; } returncheck(root.left,root.right); } publicstaticbooleancheck(TreeNodeleft,TreeNoderight){ //只有一个根节点，没有子节点，对称 if(left==null&&right==null){ returntrue; } //只有左子树或右子树为空，不对称 if(left==null||right==null){ returnfalse; } //值不相等，不对称 if(left.val!=right.val){ returnfalse; } returncheck(left.left,right.right)&&check(left.right,right.left); } } 二叉树的层序遍历 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。

（即逐层地，从左到右访问所有节点）。

示例：二叉树：[3,9,20,null,null,15,7], 3 /\ 920 /\ 157 返回其层序遍历结果： [ [3], [9,20], [15,7] ] 解题思路： 层序遍历的核心是一个队列Queue 代码中最重要的是两个循环 while循环控制的是层的遍历 for循环遍历每一层所有的节点 count 获取一层元素的个数，保证for循环遍历的是同一层元素 classSolution{ publicList>levelOrder(TreeNoderoot){ //首先判断是否为空树 if(root==null){ returnnewArrayList<>(); } Queuequeue=newLinkedList<>(); List>res=newArrayList<>(); //根节点入队 queue.add(root); while(!queue.isEmpty()){ //每层的节点数 intcount=queue.size(); //每层的节点值 Listvalue=newArrayList<>(); for(inti=0;iaverageOfLevels(TreeNoderoot){ //用于存储每层的结果 Listres=newArrayList<>(); if(root==null)returnres; Queuequeue=newLinkedList(); queue.add(root); while(!queue.isEmpty()){ intcount=queue.size(); doublelevel=0; //计算每层的和 for(inti=0;ilargestValues(TreeNoderoot){ //用于存储每层的结果 Listres=newArrayList<>(); if(root==null)returnres; Queuequeue=newLinkedList(); queue.add(root); while(!queue.isEmpty()){ intcount=queue.size(); intmax=Integer.MIN_VALUE; //计算每层的最大值 for(inti=0;i2):和为3(1-->3):和为4不存在sum=5的根节点到叶子节点的路径。

classSolution{ publicbooleanhasPathSum(TreeNoderoot,inttargetSum){ if(root==null){ returnfalse; } //用于存放当前节点 Queuenode=newLinkedList(); //用于存放当前节点的值 Queuevalue=newLinkedList(); //首先存入根节点及其值 node.add(root); value.add(root.val); while(!node.isEmpty()){ TreeNodenow=node.poll(); inttemp=value.poll(); //找到叶子节点，判断从根节点到当前叶子节点这条路径和是否等于所给的值 if(now.left==null&&now.right==null){ if(temp==targetSum){ returntrue; } continue; } if(now.left!=null){ node.add(now.left); value.add(now.left.val+temp); } if(now.right!=null){ node.add(now.right); value.add(now.right.val+temp); } } returnfalse; } } BFS遍历，层序遍历，最短路径(无权)三者之间实际上是层层递进的关系。

在BFS遍历的基础上区分遍历的每一层，就得到了层序遍历。

在层序遍历的基础上记录层数，就得到了最短路径。

whlie(true){learn} 关注 关注 0 点赞 踩 0 评论 0 收藏 一键三连 扫一扫，分享海报 专栏目录 BFS、DFS区别，详解 BackToMe的博客 08-18 4万+ BFS、DFS区别，详解写在最前的三点： 1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。

2、实现bfs和dfs都需要解决的一个问题就是如何存储图。

一般有两种方法：邻接矩阵和邻接表。

这里为简单起 见，均采用邻接矩阵存储，说白了也就是二维数组。

3、本文章的小测试部分的测试实例是下图： 一、深度优先搜索遍历 1、从顶点v出发深度遍历图G的算法 ①访问v ②依次 【C/C++面试必备】bfs和dfs的区别 Linux猿 07-30 1772 ????作者：Linux猿 ????简介：CSDN博客专家????，C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！ ????关注专栏：C/C++面试通关集锦（优质好文持续更新中……）???? 目录 一、什么是bfs? 1.1搜索方式 二、什么是dfs? 2.1搜索方式 三、bfs和dfs的区别 3.1数据结构 3.2访问节点的方式 3.3应用 大家对bfs和dfs应该都有了解，都是很常用的搜索算法，本文结合实例来讲解下这两者的不同。

参与评论 请先登录后发表评论~ 插入表情 代码片 HTML/XML objective-c Ruby PHP C C++ JavaScript Python Java CSS SQL 其它 bfs与dfs的用途与区别 瑶の博客 05-18 6465 1.BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。

这个时候不适宜使用DFS，因为DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。

（当然这个DFS的不足，可以使用迭代加深搜索ID-DFS去弥补） 2.空间优劣上，DFS是有优势 dfs和bfs差别_BFS和DFS之间的区别 culing2941的博客 09-15 1955 HereyouwilllearnaboutdifferencebetweenBFSandDFSalgorithmorBFSvs.DFS. 在这里，您将了解BFS和DFS算法或BFS与DFS之间的区别。

BreadthFirstSearch(BFS)andDepthFirstSearch(DFS)aretwopopularalgorithms... 了解BFS和DFS之间的区别 zsx0728的博客 03-11 506 文章目录宽度优先搜索深度优先搜索BFSvsDFS什么是二叉树的BFS和DFS？在额外空间方面有什么区别吗？如何选择？参考文档 宽度优先搜索     BFS代表BreadthFirstSearch，是一种基于顶点的技术，用于在图中查找最短路径。

它使用先进先出的队列数据结构。

在BFS中，一次选中并标记一个顶点，然后其相邻顶点被访问并存储在队列中。

它比DFS慢。

A /\ BC //\ DEF     输出为： A, DFS与BFS的区别 pjh88的博客 04-04 206 DFS与BFS的区别 只有DFS不可以找到最短路径吗 DFS当然也可以找到最短路径，但是时间复杂度也是O(n)，但是实际上比BFS低效的很多，DFS是依靠递归的堆栈记录走过的路径的，要找到路径必须把二叉树中的所有叉都走完，然后才可以找出最短路径，但是BFS是一步步起头并进的，可以在没有遍历完整棵树的情况下就可以找出最短路径，这其实就是层序遍历，形象的来说DFS是线，BFS是面，BFS是集体行动，DFS是线 BFS与DFS的使用场景 BFS虽然可以找到最短距离但是空间复杂度高，而DFS的空间复杂度较低 还看刚 DFS和BFS谁更合适呢 最新发布 qq_51070956的博客 12-25 83 DFS和BFS156:LETTERS BFS是向（能走的方向拓展），第一次拓展到达终点时，这条路就是起点到终点的最短路径， DFS是从起始点出发往深处走，能走多深走多深，可以分开每一条道路并比较所有的路的情况 BFS虽然很快找到离终点最近的路，但也许题目所求的未必是直接这条路，而是满足条件的结果，比如鸣人与佐助那题，虽然找到到终点最短的路，但未必是查克拉消耗最少的路。

也就是，题目要求的不一定是路径最短，而是另一个量的最值。

156:LETTERS 156:LETTERS 一开始读错了题意，以为像算水坑个 BFS和DFS的区别与分析 TTA_ATT的博客 10-28 201 BFS和DFS 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。

要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历（我们前面使用的是先序遍历）。

具体说明如下： 先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。

中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。

后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。

广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往 bfs与dfs的最简单区别 yangmin5416的博客 08-29 417 bfs与bfs区别 1.二者大多数情况可以共用。

2.bfs一般用来搜索最短路径。

3.dfs一般用来看能否到达目的地。

bfs和DFS的区别 qq_44879626的博客 09-06 76 所有题目，材料均来自于www.acwing.com bfs和dfs的区别？ github_38818603的博客 07-30 4593 参考： https://blog.csdn.net/yishuige/article/details/51769997     实现方法 基本思想 解决问题 N规模 DFS 栈/递归 回溯法，一次访问一条路，更接近人的思维方式, 所有解问题，或连通性问题 不能太大,<=200 BFS 队列 分治限界法，一次访问多条路，... DFS(深度优先搜索)与BFS(广度优先搜索) Joywy的专栏 07-28 1164 写在最前的三点： 1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。

2、实现bfs和dfs都需要解决的一个问题就是如何存储图。

一般有两种方法：邻接矩阵和邻接表。

这里为简单起见，均采用邻接矩阵存储，说白了 也就是二维数组。

3、本文章的小测试部分的测试实例是下图： 一、深度优先搜索遍历 1、从顶点v出发深度遍历图G的算法 ①访 图论中DFS与BFS的区别、用法、详解？ weixin_33739646的博客 11-11 177 2019独角兽企业重金招聘Python工程师标准>>> ... 搜索算法阶段性总结 07-27 173 搜索算法阶段性总结By1011shuo BFS与DFS的讨论：BFS：这是一种基于队列这种数据结构的搜索方式，它的特点是由每一个状态可以扩展出许多状态，然后再以此扩展，直到找到目标状态或者队列中头尾指针相遇，即队列中所有状态都已处理完毕。

DFS：基于递归的搜索方式，它的特点是由 广度/宽度优先搜索(BFS) 一米阳光 12-26 2455 raphealguo’blog：http://rapheal.sinaapp.com/2012/08/30/bfs/ 【算法入门】广度/宽度优先搜索(BFS) 发表于 30 八月,2012 由 raphealguo 1.前言 广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历策略。

因为它的思想是从一个顶点V0开始，辐射状 DFS与BFS的区别、用法、详解？ FLAB_Vincent的博客 01-14 710 写在最前的三点： 1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。

2、实现bfs和dfs都需要解决的一个问题就是如何存储图。

一般有两种方法：邻接矩阵和邻接表。

这里为简单起 见，均采用邻接矩阵存储，说白了也就是二维数组。

3、本文章的小测试部分的测试实例是下图： 一、深度优先搜索遍历 1、从顶点v出发深度遍历图G的算法 ①访 简述dfs,bfs,Dijkstra思想及区别 热门推荐 hxshine的博客 05-24 1万+ 在做pat的时候，用dfs写了一道题的解超时，看别人的解法时，发现别人用了Dijkstra算法，瞬间自己就混乱了，因为之前也看过Dijkstra，bfs算法，但是当时居然都傻傻分不清楚了，所以决定写一篇总结一下。

一：广度优先算法(BFS)     先搜索邻居，搜完邻居再搜邻居的邻居。

其中俩个思想：1.双端队列不为空则循环 图论中DFS与BFS的区别、用法、详解… 全栈空间 05-04 1167 DFS与BFS的区别、用法、详解？ 写在最前的三点： 1、所谓图的遍历就是按照某种次序访问图的每一顶点一次仅且一次。

2、实现bfs和dfs都需要解决的一个问题就是如何存储图。

一般有两种方法：邻接矩阵和邻接表。

这里为简单起 见，均采用邻接矩阵存储，说白了也就是二维数组。

3、本文章的小测试部分的测试实例是下图：   一、深度优先搜索遍历 1、从顶点v出发深度遍历图G的 DFS与BFS Qianzshuo的博客 10-21 119 题目描述 求图的DFS序列及BFS序列。

图的顶点数＜＝20，边数＜＝100。

输入 图用邻接表存储。

图中的顶点用一个结构体数组存储，结构体定义如下： typedefstructtnode {intvexdata; structnode*firstarc; }TD; 图中各顶点后接一个单链表，存储与顶点连接有边的邻接顶点信息，邻接顶点信息用结构体存储，定义如下： typedefstructnode {intadjvex; structnode*next; }JD; 程序运行时 ©️2021CSDN 皮肤主题:像素格子 设计师:CSDN官方博客 返回首页 whlie(true){learn} CSDN认证博客专家 CSDN认证企业博客 码龄1年 高校学生 148 原创 6487 周排名 1万+ 总排名 3万+ 访问 等级 1517 积分 411 粉丝 22 获赞 6 评论 39 收藏 私信 关注 热门文章 数组拷贝的四种方法 3494 特殊回文数 3079 迷宫（2017省赛） 2036 1-100之间随机产生10个整数，存入数组，排序，最大值，平均值，查找 1974 坦克大战第一版 1635 分类专栏 练习 27篇 项目 11篇 蓝桥杯 22篇 Java基础 35篇 算法 24篇 数据结构 24篇 Java编程思想 5篇 最新评论 房屋出租系统(链表实现) qq_59861241: 写太好了。

房屋出租系统(链表实现) qq_59864449: 还得是我王哥啊 Udp网络编程 qq_29750103: 非常不错 门牌制作（2020省赛） 三笠つ: 太对了哥 二叉树的前，中，后序遍历，查找，删除 、Dong: 博主写的清晰啊，思路不错 您愿意向朋友推荐“博客详情页”吗？ 强烈不推荐 不推荐 一般般 推荐 强烈推荐 提交 最新文章 计挑赛决赛试题(2021(Java组) 多用户通信系统---客户端+服务器 多用户即时通信系统---公用类+工具类 2021年148篇 目录 目录 分类专栏 练习 27篇 项目 11篇 蓝桥杯 22篇 Java基础 35篇 算法 24篇 数据结构 24篇 Java编程思想 5篇 实付元 使用余额支付 点击重新获取 扫码支付 钱包余额 0 抵扣说明： 1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。

2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。

余额充值