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

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>

Let us convert this dom structure into a tree

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):

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

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=[])

Console output result

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):

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

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="http://www.php.cn/course/list/17.html" target="_blank">JavaScript Video Tutorial</a> column on the PHP Chinese website! </p><p></p>

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!