Introduction aux algorithmes JavaScript de parcours en profondeur d'abord (DFS) et de parcours en largeur en premier (BFS)

Cet article vous présente une introduction aux algorithmes JavaScript de traversée en profondeur (DFS) et en largeur (BFS). Il a une certaine valeur de référence. Les amis dans le besoin pourront s'y référer. vous avez aidé.

Contexte : lors du développement d'une page, nous rencontrons parfois cette exigence : parcourir un certain nœud dom sur la page pour trouver le nœud dom cible. Notre approche normale consiste à utiliser le sélecteur document.getElementById() , document. getElementsByName() ou document.getElementsByTagName(), mais dans cet article, nous recherchons les nœuds dom d'un point de vue algorithmique et comprenons en même temps les principes du parcours en profondeur d'abord (DFS) et du parcours en largeur d'abord (BFS).

Préparation

Supposons que la structure dom sur la page soit la suivante :

<div>
    <ul>
        <li>
            <a>
                <img  alt="Introduction aux algorithmes JavaScript de parcours en profondeur d'abord (DFS) et de parcours en largeur en premier (BFS)" >
            </a>
        </li>
        <li>
            <span></span>
        </li>
        <li>
        </li>
    </ul>
    <p></p>
    <button></button>
</div>

Convertissons cette structure dom en arbre

Après avoir fait cela, la structure dom semble être beaucoup plus claire.

Recherche en profondeur

Cette méthode parcourt l'arborescence DOM dans une dimension verticale, en commençant par un nœud DOM et en parcourant ses nœuds enfants jusqu'à ce que tous ses nœuds enfants aient été parcourus, ses nœuds frères sont traversés. Autrement dit, comme le montre la figure (l'ordre de parcours est la marque de verrouillage rouge) :

code js pour implémenter cet algorithme (version récursive) :

function deepFirstSearch(node,nodeList) {  
    if (node) {    
        nodeList.push(node);    
        var children = node.children;    
        for (var i = 0; i <p>Version non récursive : </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 accepte deux paramètres, le premier paramètre est le nœud qui doit être traversé, le second est le tableau stocké dans le nœud et renvoie le tableau après traversée, l'ordre des éléments du tableau C'est la séquence de traversée, méthode d'appel :

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

Résultat de sortie de la console

Traversée en largeur en premier (traversée en largeur)

Cette méthode parcourt l'arborescence DOM dans une dimension horizontale, en commençant par le premier nœud enfant du nœud, en traversant tous ses nœuds frères, puis en traversant les nœuds enfants du premier nœud. Après avoir terminé la traversée, nous n'entrerons pas dans les détails pour le moment. Commence à parcourir les nœuds enfants de ses nœuds frères. Comme le montre la figure (l'ordre de parcours est la marque de verrouillage rouge) :

Code de l'algorithme d'implémentation js (version récursive) :

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

récursif version Parce que le niveau de BFS est trop profond, cela entraînera un débordement de pile : taille maximale de la pile d'appels dépassée, mais l'ordre de parcours ne pose toujours pas de problème. Vous pouvez opérer pendant le processus de parcours sans renvoyer le tableau parcouru.

Version non récursive :

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>Sortie de la console : </p><p><img src="https://img.php.cn/upload/image/727/585/757/1553909199320348.png" title="1553909199320348.png" alt="Introduction aux algorithmes JavaScript de parcours en profondeur dabord (DFS) et de parcours en largeur en premier (BFS)"></p><p   style="max-width:90%">Résumé : BFS et DFS sont tous deux des algorithmes graphiques. Premièrement, le La version décrite dans cet article est relativement simple et constitue un graphe non orienté et non connecté. D'autres algorithmes basés sur JavaScript seront mis à jour à l'avenir. </p><p style="white-space: normal;">Cet article est terminé ici. Pour d'autres contenus passionnants, vous pouvez prêter attention à la colonne <a href="http://www.php.cn/course/list/17.html" target="_blank">Tutoriel vidéo JavaScript</a> du site Web PHP chinois ! </p><p></p>

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!