如何优雅的解释 BFS/DFS
What is that ?
-----------------------
维基百科是这样描述它们的。
深度优先搜索算法（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算 法会尽可能深的搜索树的分支。当节点所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。
下一个..... 来咯.... （脑补一下某佳琦音)
广度优先搜索算法（Breadth-First Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
--------我是一个面无表情的分割线--------
其实写了一大堆文字，可能还不如一句大白话来的直接：
BFS , 广度优先搜索，把离自己最近的周围作为目标；
DFS, 深度优先搜索，把某一个方向先作为目标走到底，
也就是 一路向西（除非遇到墙）。
How to code ?
-----------------------
在代码面前 语言总是那么的苍白无力，下面我们用代码演示一下:
// BFSfunction BFS(root) {const queue = [root]while(queue.length) {const node = queue.shift()node.left && queue.push(node.left)node.right && queue.push(node.right)console.log(node.val)}}
// DFSfunction DFS(root) {const stack = [root]while(stack.length) {const node = stack.pop()node.left && stack.push(node.left)node.right && stack.push(node.right)console.log(node.val)}}
可以发现在代码实现上只有很细微的差异
Its interesting ?
-----------------------
有的同学可能觉得这样还不够直观，那么下面我们来演示一下：
首先绘制一个 100 * 100 的地图网，然后设置从起点坐标到终点坐标逐步搜索，
用延时动画的形式更直观的表达出来。
参数: start [20,20] -> end [90,90]
DFS 动画
BFS
// 核心代码const queue = [start]while(queue.length) {const [x, y] = way === 'BFS' ?queue.shift() :queue.pop();// console.log(x, y)if(x === end[0] && y === end[1])return true;// 上下左右insert(x, y - 1)insert(x, y + 1)insert(x - 1, y)insert(x + 1, y)}
提示：后台回复 搜索动画 ，可获取源代码
------------------------------
一只前端小菜鸟 | 求知若渴 | 梦想与爱皆不可辜负
-----------------------------
如果对前端内容感兴趣， 请关注此公众号
或者添加好友，加入wx 群一起学习进步