怎么理解DFS和BFS

简介: 怎么理解DFS和BFS

怎么理解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);

引用

目录
相关文章
|
4月前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
5月前
|
存储 算法 Java
【DFS(深度优先搜索)详解】看这一篇就够啦
本文介绍了深度优先搜索(DFS)算法及其应用。DFS从某个顶点出发,深入探索图的每条路径,直到无法前进为止,然后回溯。文章详细解释了DFS的基本思想,并通过示例图展示了其执行过程。此外,文中还探讨了三种枚举方式:指数型枚举、排列型枚举和组合型枚举,并提供了具体的代码实现。最后,文章通过几道练习题帮助读者更好地理解和应用DFS算法。
3083 19
|
9月前
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(下)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
64 0
|
9月前
|
存储 人工智能
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(中)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
121 0
|
9月前
|
算法
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(上)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
162 0
|
9月前
八皇后问题与其深度优先搜索 (DFS) 解法
八皇后问题与其深度优先搜索 (DFS) 解法
95 1
|
9月前
|
算法
深度优先搜索(DFS)的基础理解与实现
深度优先搜索(DFS)的基础理解与实现
114 0
DFS(深度优先搜索)和BFS(宽度优先搜索)
DFS(深度优先搜索)和BFS(宽度优先搜索)
96 0
|
算法
浅谈递归回溯DFS和BFS
前言 我们在解题的过程中经常遇到各种题型的分类,其中有几类是经常交替出现或者同时出现的 递归 回溯 DFS BFS
|
算法
从三道leetcode掌握深度优先搜索(DFS)
前言 无论在算法面试还是刷题中,深度优先搜索(DFS)和广度优先搜索(BFS)都是一个绕不过去的坎。不同于数组的从左至右遍历,循环常用于一维数据结构的遍历。而DFS和BFS则常用于多维数据结构的遍历,最常见的莫过于嵌套结构的多叉树了。

热门文章

最新文章