理解深度优先遍历与广度优先遍历

理解深度优先遍历与广度优先遍历持续创作,加速成长!这是我参与「掘金日新计划 · 6 月更文挑战」的第2天,点击查看活动详情 什么是深度优先遍历 深度优先遍历就是当我们搜索一个树的分支时,遇到一个节点,我们会优先遍历它的子节点…

持续创作,加速成长!这是我参与「掘金日新计划 · 6 月更文挑战」的第2天,点击查看活动详情

深度优先遍历广度优先遍历,不刷算法题不知道这两个概念,虽然平时业务也有写过这种场景,但是一遇到这两词就感觉高大上了

什么是深度优先遍历

深度优先遍历就是当我们搜索一个的分支时,遇到一个节点,我们会优先遍历它的子节点,直到最后根节点为止,最后再遍历兄弟节点,从兄弟子节点寻找它的子节点,直到搜索到最后结果,然后结束。

首先我们从上面一段话中,我们知道遍历的对象是树,树是一种数据结构,我们在js中可以模拟它,具体我们画一个图 理解深度优先遍历与广度优先遍历 以上就是一个基本的树结构,在js中我们可以用以下结构去描述

const root = {
  name'1',
  children: [
    {
      name'2-1',
      children: [
        {
            name'3-1',
            children: [
              {
                  name'4-2',
                  childrennull
              },
              {
                name'4-1',
                childrennull
              }
            ]
        },
        {
            name'3-2',
            childrennull
        }
      ]
    },
    {
      name'2-2',
      childrennull
    }
  ]
}

我们理解上面那句话,深度优先遍历,就是当我搜索一个树分支,遇到一个节点,我就搜索她的子节点,直到搜索完了,再去搜索兄弟节点,我们用代码来验证一下

// 深度优先遍历
const deepDFS = (root, nodeList = []) => {
  if (root) {
      nodeList.push(root.name);
      // 递归root.children,找root的子节点
      root.children && root.children.forEach(v => deepDFS(v, nodeList))
  }
  return nodeList;
}
const result = deepDFS(root, []);
console.log(JSON.stringify(result, null2))
/** [   "1",   "2-1",   "3-1",   "4-2",   "4-1",   "3-2",   "2-2" ] */

理解深度优先遍历与广度优先遍历

从结果上来看发现从最开始的分支,从第一个分支开始,找到一个节点就一直找到最深的那个节点为止,然后再找父级兄弟节点,最后再从根子节点的兄弟节点去寻找子节点。

什么是广度优先遍历

搜索树分支时,从根节点开始,当访问子节点时,先遍历找到兄弟节点,再寻找对应自己的子节点

我们用一个图来还原一下搜索过程 理解深度优先遍历与广度优先遍历 对应的代码如下

// 广度优先遍历
const deepBFS = (root, nodeList = []) => {
  const queue = [root];
  // 循环判断队列的长度是否大于0
  while(queue.length > 0) {
      // 取出队列添加的节点
      const p = queue.shift();
      nodeList.push(p.name);
      // 根据节点是否含有children,如果有子节点则添加到队列中
      p.children && p.children.forEach(v => queue.push(v))
  }
  return nodeList;
}
console.time('BFS-start')
const result = deepBFS(root, []);
console.log(JSON.stringify(result, null2));
console.timeEnd('BFS-start')
/* [   "1",   "2-1",   "2-2",   "3-1",   "3-2",   "4-2",   "4-1" ] */

广度优先遍历的主要思想是将一个树放到一个队列中,我们循环这个队列,判断该队列的长度是否大于0,我们不断循环队列,shift出队列操作,然后判断节点children,循环children,然后将子节点添加到队列中,一旦队列的长度为0,那么就终止循环了。

我们测试一下两者哪种搜索时间效率更高

// BFS 广度优先遍历
console.time('BFS-start')
const result = deepBFS(root, []);
console.log(JSON.stringify(result, null2));
console.timeEnd('BFS-start');
// DFS 深度优先遍历
console.time('DFS-start');
console.log(JSON.stringify(deepDFS(root, []), null2));
console.timeEnd('DFS-start')

最后发现 理解深度优先遍历与广度优先遍历 理解深度优先遍历与广度优先遍历 广度优先遍历的时间明显比深度优先的时间效率要高,广度优先遍历是用队列记录了每一个节点的位置,所以会占用内存更多点,由于深度优先遍历是从根节点往子节点依次递归查询,当子节点查询完了,就从根的节点的兄弟节点依次往下搜索,所以比较耗时,搜索效率上广度优先遍历更高。

总结

1、理解深度优先遍历广度优先遍历是什么

深度优先遍历就是从上到下,当我们搜索一个树时,我们从根开始,遇到一个节点,就先查询的它的子节点,如果子节点还有子节点就继续往下寻找直到最后没有为止,再从根子节点的兄弟节点开始依次向下寻找节点。

广度优先遍历遍历就是从根节点开始,寻找子节点,先遍历寻找兄弟节点,依次从上往下,按层级依次搜索。

2、用具体代码实现深度优先遍历广度优先遍历

3、深度优先遍历比广度优先遍历更耗时

4、本文示例代码 code example[1]

最后,看完觉得有收获的,鼓励下作者,点个赞,在看,转发,收藏等于学会,专注前端web技术,分享web技术,关注公众号Web技术学苑,好好学习,天天向上!

参考资料

[1] code example: github.com/maicFir/les…

今天的文章理解深度优先遍历与广度优先遍历分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/22092.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注