美文网首页
JS算法之深度优先遍历(DFS)和广度优先遍历(BFS

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS

作者: 皇甫贝 | 来源:发表于2019-08-05 12:03 被阅读0次

背景

在开发页面的时候,我们有时候会遇到这种需求:在页面某个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结构

这样之后,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;  
}

控制台输出结果:

结果.jpg

相关文章

  • 无向图DFS和BFS

    基本结构 DFS深度优先遍历 BFS广度优先遍历 符号图

  • leecode岛屿数量

    题目描述可用解法DFS 深度优先遍历BFS 广度优先遍历算法思路:下列代码用BFS,循环遍历输入的二维列表如果遇到...

  • 【数据结构】广度优先搜索算法BFS

    对于广度优先遍历算法DFS可以参考前一篇文章【数据结构】深度优先搜索算法DFS 广度优先遍历 广度优先遍历(Bre...

  • 算法-二叉树的遍历实现

    简述 二叉树的遍历分 DFS【深度优先遍历】 和 BFS【广度优先遍历】 两类,其中 DFS 又分为前序遍历,中序...

  • 基本数据结构

    一.图二.树 一.图 1.图的遍历: 通过深度优先遍历DFS和广度优先遍历BFS两种方式。深度优先遍历0 1 2 ...

  • BFS和DFS

    BFS:广度优先搜索 DFS:深度优先搜索 树的遍历 BFS:A B C D E F G H I DFS: A ...

  • 刷题7 剑指 Offer — DFS

    树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS);常见的 DFS : 先序遍历、中序遍历、...

  • 74_图的遍历(BFS)

    关键词:MatrixGraph和ListGraph的选择方式、图的遍历概念、广度优先(BFS)、深度优先(DFS)...

  • 数据结构基础--栈和队列

    目录 基本性质 栈和队列的基本操作 双端队列和优先级队列 深度优先遍历(DFS)和广度优先遍历(BFS) 递归函数...

  • 1.5 二叉树(4)

    二叉树相关问题解题套路 广度优先遍历(BFS:Breath First Search)、深度优先遍历(DFS:De...

网友评论

      本文标题:JS算法之深度优先遍历(DFS)和广度优先遍历(BFS

      本文链接:https://www.haomeiwen.com/subject/iinpdctx.html