深度优先DFS和广度优先BFS

wade

发布于 2020-04-24 10:00:07

7280

发布于 2020-04-24 10:00:07

文章被收录于专栏：coding个人笔记coding个人笔记

之前在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')));