专栏首页coding个人笔记深度优先DFS和广度优先BFS

深度优先DFS和广度优先BFS

之前在HTML渲染过程这篇分享有人在评论问我,这个过程是DFS还是BFS,发现自己好水,确实不知道渲染过程是什么优先,到现在都不知道。

BFS:

Breadth First Search宽度搜索优先,是一种简便图的搜索算法之一,在前端里,一般用来遍历节点和对象等。该方法以纵向的维度对DOM进行遍历,从一个节点开始,一直遍历到子节点,直到所有子节点遍历完成再遍历兄弟节点。

DFS:

Depths First Search深度搜索优先,也是图算法一种,开发早期爬虫使用较多的一种算法。同样的,在前端里也是用来遍历节点或者对象。这个方法以横向维度进行遍历,先从兄弟节点遍历,再从兄弟节点的第一个子节点遍历,一直到最后。

以这样的DOM节点为例子:

<div id="app">
 <p>
  <span></span>
 </p>
 <ul>
  <li>
   <a href=""><span></span></a>
  </li>
 </ul>
</div>

深度优先:

function deepFirstSearch(node, nodeList = []) {
 if (node) {
  nodeList.push(node);
  var children = node.children;
  for (var i = 0; i < children.length; i++)
   deepFirstSearch(children[i], nodeList);
 }
 return nodeList;
}
console.log(deepFirstSearch(document.getElementById('app')));

广度优先遍历:

function breadthFirstSearch(node, nodeList = []) {
 if (node) {
  var list = [node];
  while (list.length != 0) {
   var item = list.shift();
   nodeList.push(item);
   var children = item.children;
   for (var i = 0; i < children.length; i++){
    list.push(children[i]);
   }
  }
 }
 return nodeList;
}
console.log(breadthFirstSearch(document.getElementById('app')));

深度和广度优先分别有递归和非递归的算法,这边只是想分享这两个概念,在开发中确实也很少很少使用,其实前端涉及算法的也很少。有兴趣的可以自行去好好研究。

(完)

本文分享自微信公众号 - coding个人笔记(gh_2ce38b49dae1),作者:wade

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 阮一峰快速排序

    本打算学一波快速排序,查了查资料,吓一大跳,说阮一峰大神的快排是不对的,以此开始了一大波大神针对这个问题的各种观点。感兴趣的可以看看知乎这篇帖子:

    wade
  • localStorage和sessionStorage

    在以前,想要存储数据在本地中只有cookie,而cookie又被限制了大小,在不同浏览器只能存储4k左右的cookie。于是H5新增了本地存储localStor...

    wade
  • Node的安装

    在这个前端技术爆炸的时代,前端的变化是如此之快。想想前两年,都还是jQuery的天下,现在再看看Github上星号最多的JavaScript技术列表,最短的也就...

    wade
  • 排序|优先队列不知道,先看看堆排序吧

    在个人的专栏中,其他排序陆陆续续都已经写了,而堆排序迟迟没有写,趁着国庆假期的尾声,把堆排序也写一写。

    bigsai
  • leetcode:104二叉树的最大深度

    思路:用深度优先遍历。 深度优先遍历是尽可能深的遍历这棵树。 怎么做? 新建一个变量记录每一个节点的层级,找到最大的层级即可。

    用户7873631
  • CAN知识集合

    1.隐性和显性位 显性数值表示逻辑0,隐性数值表示逻辑1 CAN总线为隐性(逻辑1)时,CAN_H和CAN_L的电平都为2.5V(电位差为0V);

    心跳包
  • L2-006. 树的遍历

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    指点
  • 前序遍历中序遍历求后序遍历-数组篇

    如果已知前序遍历和中序遍历,那么肯定能够求出后序遍历。正常的思路就是,根据前序遍历和中序遍历,我们把二叉树的结构给描述出来,然后再使用后序遍历。

    chain
  • 剑指offer 33——二叉搜索树的后序遍历序列

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

    健程之道
  • 【图解数据结构】 一组动画彻底理解二叉树遍历

    定义:二叉树的遍历是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券