JavaScript深度优先遍历(DFS)和广度优先遍历(BFS）算法的介绍

来源：懂视网责编：小采时间：2020-11-27 19:26:52

JavaScript深度优先遍历(DFS)和广度优先遍历(BFS）算法的介绍

JavaScript深度优先遍历(DFS)和广度优先遍历(BFS）算法的介绍:本篇文章给大家带来的内容是关于JavaScript深度优先遍历(DFS)和广度优先遍历(BFS）算法的介绍，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。背景：在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom

推荐度：

点击下载本文 文档为doc格式

导读JavaScript深度优先遍历(DFS)和广度优先遍历(BFS）算法的介绍:本篇文章给大家带来的内容是关于JavaScript深度优先遍历(DFS)和广度优先遍历(BFS）算法的介绍，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。背景：在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom

本篇文章给大家带来的内容是关于JavaScript深度优先遍历(DFS)和广度优先遍历(BFS）算法的介绍，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

背景：在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom节点，我们正常做法是利用选择器document.getElementById()，document.getElementsByName()或者document.getElementsByTagName()，但在本文，我们从算法的角度去查找dom节点，同时理解一下深度优先遍历(DFS)和广度优先遍历(BFS)的原理。

准备

假设页面上的dom结构如下：

<div id="root">
 <ul>
 <li>
 <a href="">
 <img src="" alt="">
 </a>
 </li>
 <li>
 <span></span>
 </li>
 <li>
 </li>
 </ul>
 <p></p>
 <button></button>
</div>

让我们来把这个dom结构转化成树的样子

这样之后，dom结构似乎清楚了不少。

深度优先遍历（Depth-First Search）

该方法是以纵向的维度对dom树进行遍历，从一个dom节点开始，一直遍历其子节点，直到它的所有子节点都被遍历完毕之后在遍历它的兄弟节点。即如图所示（遍历顺序为红字锁标）：

js实现该算法代码(递归版本)：

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; 
}

非递归版本：

function deepFirstSearch(node) {
 var nodes = [];
 if (node != null) {
 var stack = [];
 stack.push(node);
 while (stack.length != 0) {
 var item = stack.pop();
 nodes.push(item);
 var children = item.children;
 for (var i = children.length - 1; i >= 0; i--)
 stack.push(children[i]);
 }
 }
 return nodes;
}

deepFirstSearch接受两个参数，第一个参数是需要遍历的节点，第二个是节点所存储的数组，并且返回遍历完之后的数组，该数组的元素顺序就是遍历顺序，调用方法：

let root = document.getElementById('root')
deepTraversal(root,nodeList=[])

控制台输出结果

广度优先遍历（breadth-first traverse）

该方法是以横向的维度对dom树进行遍历，从该节点的第一个子节点开始，遍历其所有的兄弟节点，再遍历第一个节点的子节点，完成该遍历之后，暂时不深入，开始遍历其兄弟节点的子节点。即如图所示（遍历顺序为红字锁标）：

js实现算法代码（递归版本）：

function breadthFirstSearch(node) {
 var nodes = [];
 var i = 0;
 if (!(node == null)) {
 nodes.push(node);
 breadthFirstSearch(node.nextElementSibling);
 node = nodes[i++];
 breadthFirstSearch(node.firstElementChild);
 }
 return nodes;
}

递归版本的BFS由于层级太深，会导致堆栈溢出：Maximum call stack size exceeded，但遍历的顺序依旧没有问题，可以在遍历过程中进行操作，不返回遍历数组即可。

非递归版本：

function breadthFirstSearch(node) { 
 var nodes = []; 
 if (node != null) { 
 var queue = []; 
 queue.unshift(node); 
 while (queue.length != 0) { 
 var item = queue.shift(); 
 nodes.push(item); 
 var children = item.children; 
 for (var i = 0; i < children.length; i++) 
 queue.push(children[i]); 
 } 
 } 
 return nodes; 
}

控制台输出结果：