怎么理解DFS和BFS
当遇到列举所有的情况之类的,要联想到DFS和BFS! 就像看到直角三角形想到勾股定理,十之八九的要用到!
TL;DR
列举所有的情况常常使用两个思想:
- DFS(Deep First Search - 深度优先搜索): 不撞南墙不回头,撞了南墙那就回头重新走。一般和二叉树的先序遍历紧密相关,用递归实现,本质是栈结构,后进先出
- BFS(Breath First Search - 广度优先搜索): 雷达扫描式前进,看到新路就记着,走过的路就舍弃。一般和二叉树的层序遍历紧密相关,用队列实现,先进先出
DFS
DFS: 贯彻了“不撞南墙不回头”的原则,你在一个迷宫里,只要没有碰壁,就决不选择其它的道路,而是坚持向当前道路的深处挖掘,像这样将“深度”作为前进的第一要素的搜索方法,就是所谓的“深度优先搜索”。
深度优先搜索的核心思想,是试图穷举所有的完整路径。
网络异常,图片无法展示
|
- A-B-C,C 南墙,退到 B
- A-B-D,D 南墙,退到 B
- A-B-E-F,F 南墙,退到 E
- A-B-E-G-H,H 南墙,退到 G
- A-B-E-G-I,成功出口
深度优先搜索的过程可以转化为一系列的入栈、出栈操作,往往使用递归来模拟入栈、出栈的逻辑。
DFS 紧密相关:二叉树的先序遍历
网络异常,图片无法展示
|
{ val:'A', left:{ val:'B', left:{ val:'C' } } }
先序遍历:
// 所有遍历函数的入参都是树的根结点对象 function preorder(root) { // 递归边界,root 为空 if (!root) { return; } // 输出当前遍历的结点值 console.log("当前遍历的结点值是:", root.val); // 递归遍历左子树 preorder(root.left); // 递归遍历右子树 preorder(root.right); }
在这个递归函数中,递归式用来先后遍历左子树、右子树(分别探索不同的道路),递归边界在识别到结点为空时会直接返回(撞到了南墙)。
可以认为,递归式就是我们选择道路的过程,而递归边界就是死胡同。 二叉树的先序遍历正是深度优先搜索思想的递归实现。
为啥还说深度优先搜索的本质是栈呢?
两个角度来理解这个事情:
- 首先,递归的本质就是调用函数,而调用函数就会用到系统栈。
- 其次,DFS 作为一种思想,不是肯定会用到递归,有时候需要手动写栈结构
BFS
网络异常,图片无法展示
|
- A-B 走到 A,看到 B
- B-C-D-E 走到 B,舍弃 A,看到 CDE
- C-D-E 走到 C,舍弃 B,没看到啥
- D-E 走到 D,舍弃 D,没看到啥
- E-F-G 走到 E,舍弃 D,看到 FG
- F-G 走到 F,舍弃 E,没看到啥
- G-H-I 走到 G,舍弃 F,看到 HI
- H-I 走到 H,舍弃 G,没看到啥
- I-出口 走到 I,舍弃 H,看到出口
- 出口 走到出口,舍弃 I,问题解决
- 空 走出出口,问题解决
在分层遍历的过程中,两个规律:
- 每访问完毕一个坐标,其在后续遍历中就不需要了,可以被丢弃掉。
- 站在某个确定坐标的位置上,可直接抵达的坐标,是需要被记录下来的,因为后续的遍历还要用到它们。
丢弃已访问的坐标、记录新观察到的坐标,这个顺序毫无疑问符合了“先进先出”的原则,因此整个 BFS 算法的实现过程,和队列有着密不可分的关系。
伪代码表示上面的逻辑:
function BFS(入口坐标) { // 初始化队列queue const queue = [] // 入口坐标首先入队 queue.push(入口坐标) // 队列不为空,说明没有遍历完全 while(queue.length) { // 取出队头元素 const top = queue[0] // 此处是一些和 top 相关的逻辑,比如记录它对应的信息、检查它的属性等等 访问 top // 注意这里也可以不用 for 循环,视题意而定 for(检查 top 元素出发能够遍历到的所有元素) { queue.push(top能够直接抵达的元素) } // 访问完毕。将队头元素出队 queue.shift() } }
BFS 紧密相关:二叉树的层序遍历
网络异常,图片无法展示
|
二叉树的层序遍历,其实就是 BFS 的思想:
const root = { val: "A", left: { val: "B", left: { val: "D", }, right: { val: "E", }, }, right: { val: "C", right: { val: "F", }, }, }; function BFS(root) { let queue = []; // 根结点首先入队 queue.push(root); // 队列不为空,说明没有遍历完全 while (queue.length) { // 这里队列前面不断被更新 const top = queue[0]; // 输出值 console.log(top.val); // 将可到达的点 入队 top.left && queue.push(top.left); top.right && queue.push(top.right); // 访问完毕,队头元素出队 queue.shift(); } } BFS(root);