Home > Web Front-end > JS Tutorial > Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms

Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms

不言
Release: 2019-03-30 09:28:41
forward
7797 people have browsed it

This article brings you an introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms. It has certain reference value. Friends in need can refer to it. I hope it will be useful to you. helped.

Background: When developing pages, we sometimes encounter this need: traverse a certain dom node on the page to find the target dom node. Our normal approach is to use the selector document.getElementById() , document.getElementsByName() or document.getElementsByTagName(), but in this article, we look for dom nodes from an algorithmic perspective, and at the same time understand the principles of depth-first traversal (DFS) and breadth-first traversal (BFS).

Preparation

Assume that the dom structure on the page is as follows:

<div>
    <ul>
        <li>
            <a>
                <img  alt="Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms" >
            </a>
        </li>
        <li>
            <span></span>
        </li>
        <li>
        </li>
    </ul>
    <p></p>
    <button></button>
</div>
Copy after login

Let us convert this dom structure into a tree

Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms

After this, the dom structure seems to be much clearer.

Depth-First Search

This method traverses the dom tree in a vertical dimension, starting from a dom node and traversing its child nodes until all of its After all the child nodes have been traversed, its sibling nodes are traversed. As shown in the figure (the traversal order is the red lock mark):

Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms

js code to implement the algorithm (recursive version):

function deepFirstSearch(node,nodeList) {  
    if (node) {    
        nodeList.push(node);    
        var children = node.children;    
        for (var i = 0; i <p>Non-recursive version: </p><pre class="brush:php;toolbar:false">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;
}
Copy after login

deepFirstSearch accepts two parameters. The first parameter is the node that needs to be traversed. The second parameter is the array stored in the node, and returns the array after traversing. The order of the elements of the array is the traversal order. Calling method:

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

Console output result

Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms

Breadth-first traverse (breadth-first traverse)

This method is horizontal Dimensionally traverse the DOM tree, starting from the first child node of the node, traversing all its sibling nodes, and then traversing the child nodes of the first node. After completing the traversal, we will not go into depth for the time being and start traversing its sibling nodes. child node. That is, as shown in the figure (the traversal order is the red lock mark):

Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms

js implementation algorithm code (recursive version):

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;
}
Copy after login

The recursive version of BFS is due to If the level is too deep, it will cause stack overflow: Maximum call stack size exceeded, but there is still no problem with the order of traversal. You can perform operations during the traversal process without returning the traversed array.

Non-recursive version:

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 <p>Console output: </p><p><img src="https://img.php.cn/upload/image/727/585/757/1553909199320348.png" title="1553909199320348.png" alt="Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms"></p><p   style="max-width:90%">Summary: BFS and DFS are both graph algorithms. The version described in this article is relatively simple and is an undirected and non-connected graph. More JavaScript-based algorithms will be updated in the future. </p><p style="white-space: normal;">This article has ended here. For more other exciting content, you can pay attention to the <a href="//m.sbmmt.com/course/list/17.html" target="_blank">JavaScript Video Tutorial</a> column on the PHP Chinese website! </p><p></p>
Copy after login

The above is the detailed content of Introduction to JavaScript depth-first traversal (DFS) and breadth-first traversal (BFS) algorithms. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:segmentfault.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template