前言深度优先搜索（简称DFS）和广度优先搜索（BreathFirstSearch）是图论的两种非常重要算法在生产中被广泛应用于拓扑排序、寻路（走迷宫）、搜索引擎、爬虫等，也经常出现在leetcode和高频面试题中。本文将从以下几个方面来描述深度优先遍历和广度优先遍历。相信大家看完后都会有所收获。深度优先遍历、广度优先遍历介绍练习DFS、BFS在搜索引擎中的应用然后从另一条路走到尽头……，递归重复这个过程，直到遍历完所有的顶点。它的特点是不撞南墙不回头，先走一条路，再换另一条路继续走。树是图的特例（连通无环图是树）。接下来我们看一下如何用深度优先遍历来遍历一棵树。1、我们从根节点1开始遍历，它的相邻节点是2、3、4，我们先遍历节点2，然后遍历2的子节点5，再遍历5的子节点9。2.上面的一行图路走到尽头了（9是叶子节点，已经没有可遍历的节点了），此时从9回滚到之前的节点5，查看节点5中是否有除9以外的节点，并且不继续回滚到2，2除了5没有其他节点，回滚到1，1除了2之外还有节点3，所以从节点3开始进行深度优先遍历，如下：3.同理，从10开始往回走6，6除了10没有其他子节点，然后回溯，发现3有一个除了6之外的子节点7，所以此时会遍历7。3、从7回溯到3、1，发现1有节点4还没有遍历过，所以此时沿着4和8遍历，遍历完成。完整节点的遍历顺序如下（用节点上的蓝色数字表示）：相信大家看到上面的遍历不难发现这是树的前序遍历。其实不管是前序遍历，还是中序遍历，也好，还是后序遍历，都属于深度优先遍历。那么如何实现深度优先遍历，有两种表现形式：递归和非递归。下面我们以一棵二叉树为例，看看如何分别用递归和非递归实现深度优先遍历。1.递归实现递归实现比较简单。因为是前序遍历，所以我们可以依次遍历当前节点、左节点、右节点。对于左右节点，我们可以依次遍历它们的左右节点，依次递归下去，直到叶子节点（递归终止条件），代码如下：publicclassSolution{privatestaticclassNode{/***节点值*/publicintvalue;/***左节点*/publicNodeleft;/***右节点*/publicNoderight;publicNode(intvalue,Nodeleft,Noderight){this.value=value;this.left=left;this.right=right;}}publicstaticvoiddfs(NodetreeNode){if(treeNode==null){return;}//遍历nodeprocess(treeNode)//遍历左节点dfs(treeNode.left);//遍历右节点dfs(treeNode.right);}}递归表达能力很强，也很容易理解，但是如果层次太深，很容易造成堆栈溢出。因此，让我们关注非递归实现。2.非递归实现仔细观察深度优先遍历的特点。对于二叉树，由于是前序遍历（先遍历当前节点，再遍历左节点，再遍历右节点），所以我们有以下思路：对于每个节点，例如先遍历当前节点，然后将右节点压入栈中，再将左节点压入栈中（这样出栈时，会先遍历左节点，满足深度优先遍历的要求）。弹出堆栈并获取堆栈顶部的节点。如果节点不为空，则重复步骤1。如果为空，则结束遍历。下面以二叉树为例，看看如何用栈实现DFS。整体动画如下：整体思路比较清晰。用栈压入要遍历的节点，出栈后检查该节点中是否还有未遍历的节点。),有了思路,不难写出如下用栈实现的二叉树深度优先遍历代码:/***用栈实现dfs*@paramroot*/publicstaticvoiddfsWithStack(Noderoot){if(root==null){return;}Stackstack=newStack<>();//先压根节点stack.push(root);while(!stack.isEmpty()){NodetreeNode=stack.pop();//遍历节点过程(treeNode)//先压右节点if(treeNode.right!=null){stack.push(treeNode.right);}//压左节点if(treeNode.left!=null){stack.push(treeNode.left);}}}可以看到使用栈实现深度优先遍历其实并不复杂，也不用担心太深导致的栈溢出问题递归。广度优先遍历广度优先遍历是指从图中一个未遍历的节点开始，先遍历该节点的相邻节点，然后依次遍历每个相邻节点的相邻节点。上述树的广度优先遍历动画如下，每个节点的值就是它们的遍历顺序。所以，广度优先遍历也叫层序遍历，先遍历第一层（节点1），再遍历第二层（节点2、3、4），第三层（5、6、7、8）和第四层（9、10）。深度优先遍历使用栈，而广度优先遍历使用队列实现。下面以二叉树为例，看看如何使用队列来实现广度优先遍历。动画如下：相信看完上面的动画，写出下面的代码就不难了：/***使用队列实现bfs*@paramroot*/privatestaticvoidbfs(Noderoot){if(root==null){return;}Queuestack=newLinkedList<>();stack.add(root);while(!stack.isEmpty()){Nodenode=stack.poll();System.out.println("价值=“+节点。价值”；Nodeleft=node.left;if(left!=null){stack.add(left);}Noderight=node.right;if(right!=null){stack.add(right);}}}接下来练习看一下leetcode中使用DFS和BFS解决问题的一些主题：leetcode104、111：给定一个二叉树，找到它的最大/最小深度。例如：给定一棵二叉树[3,9,20,null,null,15,7],3/\920/\157，其最小深度为2，最大深度为3。解题思路：本题比较简单，不过是深度优先遍历的一种变形。它只需要递归地找到左右子树的最大/最小深度。不难写出如下代码：/***leetcode104:求树的最大深度*@paramnode*@return*/publicstaticintgetMaxDepth(Nodenode){if(node==null){return0;}intleftDepth=getMaxDepth(node.left)+1;intrightDepth=getMaxDepth(node.right)+1;returnMath.max(leftDepth,rightDepth);}/***leetcode111:求树的最小深度*@paramnode*@return*/publicstaticintgetMinDepth(Nodenode){if(node==null){return0;}intleftDepth=getMinDepth(node.left)+1;intrightDepth=getMinDepth(node.right)+1;returnMath.min(leftDepth,rightDepth);}leetcode102:给你一棵二叉树，请你返回它遍历的节点值，按层级排序。（即逐层，从左到右访问所有节点）。例如，给定一个二叉树：[3,9,20,null,null,15,7]。3/\920/\157返回其层级遍历结果：[[3],[9,20],[15,7]]解题思路：很明显这道题是广度优先遍历的变种，只需要在广度优先遍历的过程中，只是将每一层的节点加入到同一个数组中即可。问题的关键在于，在遍历同层节点之前，必须提前计算出同层节点的个数（即队列中已有元素的个数），因为BFS是通过一个队列来实现的,左右子节点在遍历过程中会不断入队。记住这一点！动画如下：根据上面的动画思路，不难得到如下代码：Java代码/***leetcdoe102:二叉树的层序遍历，使用bfs*@paramroot*/privatestaticList>bfsWithBinaryTreeLevelOrderTraversal(Noderoot){if(root==null){//根节点为空，说明二叉树不存在，直接返回空数组returnArrays.asList();}//最后一层顺序遍历结果List>result=newArrayList<>();Queuequeue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){//记录每层Listlevel=newArrayList<>();intlevelNum=queue.size();//遍历当前层的节点for(inti=0;i>TRAVERSAL_LIST=newArrayList<>();/***leetcdoe102:Level二叉树的顺序遍历，使用dfs*@paramroot*@return*/privatestaticvoiddfs(Noderoot,intlevel){if(root==null){return;}if(TRAVERSAL_LIST.size()());}ListlevelList=TRAVERSAL_LIST.get(level);levelList。add(root.value);//遍历左节点dfs(root.left,level+1);//遍历右节点dfs(root.right,level+1);}搜索引擎中的DFS、BFS我们几乎每天都使用谷歌、百度等搜索引擎。你知道这些搜索引擎是如何工作的吗？简单来说就是三个步骤：1.网页爬取搜索引擎通过爬虫对网页进行爬取，获取页面的HTML代码。2、预处理索引程序对抓取的页面数据进行文本提取、中文分词、（倒排）索引等处理，供排名程序使用。3、排名用户输入关键词后，排名程序调用索引数据库数据，计算相关性，然后生成一定格式的搜索结果页面。让我们关注第一步，网络爬虫。这一步的一般操作如下：分配一组初始网页给爬虫。我们知道网页其实包含了很多超链接。爬虫爬取一个网页后，解析并提取该网页中的所有超链接，然后依次进行爬取。取出这些超链接，然后提取网页超链接。..，这样就可以根据超链接不断地重复提取网页。如下图所示：如上所示，最终形成了一个图，那么问题就转化为如何遍历这个图，显然可以采用深度优先或者广度优先的方式进行遍历。如果是广度优先遍历，先依次爬取第一层的初始网页，然后依次爬取每个网页中的超链接；如果是深度优先遍历，先抓取初始网页1，再抓取这个网页链接……抓取完后，抓取起始页2……其实爬虫同时使用了深度优先和广度优先两种策略一起。比如在起始页中，有些页面比较重要（权重高），那么先对这个网页做深度优先遍历，遍历完后再对其他（权重相同）起始页做广度优先遍历。综上所述，DFS和BFS是两个非常重要的算法，每个人都必须掌握。为了讲解方便，本文只对树做DFS和BFS。如果你使用图表，你可以尝试如何编写代码。原理其实是一样的，只是图和树的表示方式不同而已。DFS一般解决连通性问题，而BFS一般解决最短路径问题。后面我们一起学习搜索，Dijkstra，Prism算法等，敬请期待！
