BFS和DFS

深度优先搜索的本质——栈结构广度优先搜索思想——队列结构

深度优先搜索的本质——栈结构

💡

一条路走到底，然后换下个路口，直到走到终点

从 A 出发（A入栈），经过了B（B入栈），接下来面临 C、D、E三条路。这里按照从上到下的顺序来走（你也可以选择其它顺序），先走C（C入栈）。

发现 C是死胡同，后退到最近的岔路口 B（C出栈），尝试往D方向走（D入栈）。

发现D 是死胡同，，后退到最近的岔路口 B（D出栈），尝试往E方向走（E入栈）。

E 是一个岔路口，眼前有两个选择：F 和 G。按照从上到下的顺序来走，先走F（F入栈）。

发现F 是死胡同，后退到最近的岔路口 E（F出栈），尝试往G方向走（G入栈）。

G 是一个岔路口，眼前有两个选择：H 和 I。按照从上到下的顺序来走，先走H（H入栈）。

发现 H 是死胡同，后退到最近的岔路口 G（H出栈），尝试往I方向走（I入栈）。

I 就是出口，成功走出迷宫。

类似二叉树遍历


// 所有遍历函数的入参都是树的根结点对象
function preorder(root) {
    // 递归边界，root 为空
    if(!root) {
        return 
    }
     
    // 输出当前遍历的结点值
    console.log('当前遍历的结点值是：', root.val)  
    // 递归遍历左子树 
    preorder(root.left)  
    // 递归遍历右子树  
    preorder(root.right)
}

广度优先搜索思想——队列结构

💡

走完整一层后换下一层，扫描

初始化，先将入口A入队（queue里现在只有A）。

访问入口A（第一层），访问完毕后将A出队。发现直接能抵达的坐标只有B，于是将B入队（queue里现在只有B）。

访问B（第二层），访问完毕后将B出队。发现直接能抵达的坐标变成了C、D和E，于是把这三个坐标记为下一层的访问对象，也就是把它们全部入队（queue里现在是C、D、E）

访问第三层。这里我按照从上到下的顺序（你也可以按照其它顺序），先访问 C（访问完毕后C出队）和D（访问完毕后D出队），然后访问E（访问完毕后E出队）。访问C处和D处都没有见到新的可以直接抵达的坐标，所以不做额外的动作。但是在E处我们见到了可以直接抵达的F和G，因此把F和G记为下一层（第四层）需要访问的对象，F、G依次入队（queue里现在是 F、G）。

访问第五层。第五层按照从上到下的顺序，先访问的是H（访问完毕后H出队），发现从H出发没有可以直接抵达的坐标，因此不作额外的操作。接着访问I（访问完毕后I出队），发现I就是出口，问题得解（此时 queue 队列已经被清空）。

在这个过程里，我们其实循环往复地做了以下事情：依次访问队列里已经有的坐标，将其出队；记录从当前坐标出发可直接抵达的所有坐标，将其入队。

以上逻辑用伪代码表述如下：


function BFS(入口坐标) {
    const queue = [] // 初始化队列queue
    // 入口坐标首先入队
    queue.push(入口坐标)
    // 队列不为空，说明没有遍历完全
    while(queue.length) {
        const top = queue[0] // 取出队头元素  
        
        访问 top // 此处是一些和 top 相关的逻辑，比如记录它对应的信息、检查它的属性等等
        
        // 注意这里也可以不用 for 循环，视题意而定
        for(检查 top 元素出发能够遍历到的所有元素)  {
            queue.push(top能够直接抵达的元素)
        }
        
        queue.shift() // 访问完毕。将队头元素出队
    }
}

🧐

BFS实战

🪀

DBS实战