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

roadtogeek 发布于2019-08-23 16:33 / 1339人阅读

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

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

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

准备

假设页面上的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;  
}

控制台输出结果：

总结

BFS和DFS都是图的算法之一，本文所阐述的版本较为简单，为无向且非连通图，在日后会更新更多基于JavaScript的算法。

云服务器 GPU云服务器广度优先遍历广度优先搜索算法代码广度优先搜索 python广度优先

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103144.html

js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。树的简介栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...

Yuanf 2019-08-23 11:38 评论0 收藏0
js版本的BFS&DFS

摘要：队列栈队列是先进先出，后进后出，常用的操作是取第一个元素尾部加入一个元素。栈是后进先出，就像一个垃圾桶，后入的垃圾先被倒出来。遍历中间过程，每一个节点入栈的时候是灰色的，出栈的时候是黑色的。 0. 前言广度优先搜索(BFS)和深度优先搜索(DFS)，大家可能在oj上见过，各种求路径、最短路径、最优方法、组合等等。于是，我们不妨动手试一下js版本怎么玩。 1.队列、栈队列是先进先出，...

刘福 2019-08-22 16:49 评论0 收藏0
Javascript的数据结构与算法(三)

摘要：存在好几种方式来表示这种数据结构。下面的示意图展示了邻接表数据结构。在关联矩阵中矩阵的行表示顶点列表示边。广度优先搜索算法和深度优先搜索算法基本上是相同的只有一点不同那就是待访问顶点列表的数据结构。 1 树一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点。位于树顶部的节点叫作根节点(11)。它没有父节点。树中的每个元素都叫作...

MasonEast 2019-08-21 11:24 评论0 收藏0
DOM树遍历之JS实现DFS&BFS

摘要：对于上面例子遍历结果应为则总是先遍历当前层级的所有节点，只有当当前层级所有节点都遍历结束后才会进入下一层级。我们一般可以采用DFS（深度优先遍历）和BFS（广度优先遍历）来遍历DOM树介绍 DFS & BFS 我们来结合具体例子进行分析，给出HTML代码片段如下： DFS总是先进入下一...

imccl 2019-08-20 15:52 评论0 收藏0
DOM树遍历之JS实现DFS&BFS

摘要：对于上面例子遍历结果应为则总是先遍历当前层级的所有节点，只有当当前层级所有节点都遍历结束后才会进入下一层级。我们一般可以采用DFS（深度优先遍历）和BFS（广度优先遍历）来遍历DOM树介绍 DFS & BFS 我们来结合具体例子进行分析，给出HTML代码片段如下： DFS总是先进入下一...

fengxiuping 2019-08-01 16:40 评论0 收藏0