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

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

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

准备

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

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

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

function deepFirstSearch(node,nodeList) {  
    if (node) {    
        nodeList.push(node);    
        var children = node.children;    
        for (var i = 0; i 
非递归版本：
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(&＃39;root&＃39;)
deepTraversal(root,nodeList=[])
控制台输出结果
 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 
控制台输出结果：
总结：BFS和DFS都是图的算法之一，本文所阐述的版本较为简单，为无向且非连通图，在日后会更新更多基于Javascript的算法。
本篇文章到这里就已经全部结束了，更多其他精彩内容可以关注PHP中文网的Javascript视频教程栏目！
以上就是Javascript深度优先遍历(DFS)和广度优先遍历(BFS）算法的介绍的详细内容，更多请关注 第一PHP社区 其它相关文章！