Einführung in die JavaScript-Algorithmen Depth-First-Traversal (DFS) und Breite-First-Traversal (BFS).

Dieser Artikel bietet Ihnen eine Einführung in die JavaScript-Algorithmen „Depth-First Traversal“ (DFS) und „Breadth-First Traversal“ (BFS). Ich hoffe, dass er für Freunde hilfreich ist Du hast geholfen.

Hintergrund: Bei der Entwicklung von Seiten stoßen wir manchmal auf die folgende Notwendigkeit: Durchlaufen Sie einen bestimmten Dom-Knoten auf der Seite, um den Ziel-Dom-Knoten zu finden. Unser normaler Ansatz besteht darin, den Selektor document.getElementById() und document.getElementsByName zu verwenden () oder document.getElementsByTagName(), aber in diesem Artikel suchen wir aus algorithmischer Sicht nach Dom-Knoten und verstehen gleichzeitig die Prinzipien der Tiefendurchquerung (DFS) und der Breitendurchquerung (BFS).

Vorbereitung

Angenommen, die Dom-Struktur auf der Seite ist wie folgt:

<div>
    <ul>
        <li>
            <a>
                <img  alt="Einführung in die JavaScript-Algorithmen Depth-First-Traversal (DFS) und Breite-First-Traversal (BFS)." >
            </a>
        </li>
        <li>
            <span></span>
        </li>
        <li>
        </li>
    </ul>
    <p></p>
    <button></button>
</div>

Lassen Sie uns diese Dom-Struktur in einen Baum umwandeln

Danach scheint die Dom-Struktur viel klarer zu sein.

Tiefensuche

Diese Methode durchläuft den DOM-Baum in einer vertikalen Dimension, beginnend bei einem DOM-Knoten und durchläuft seine untergeordneten Knoten, bis alle seine untergeordneten Knoten durchlaufen wurden. seine Geschwisterknoten werden durchlaufen. Wie in der Abbildung gezeigt (die Durchlaufreihenfolge ist die rote Schlossmarkierung):

js-Implementierung des Algorithmuscodes (rekursive Version):

function deepFirstSearch(node,nodeList) {  
    if (node) {    
        nodeList.push(node);    
        var children = node.children;    
        for (var i = 0; i <p>Nein -rekursive 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 akzeptiert zwei Parameter. Der erste Parameter ist das im Knoten gespeicherte Array und gibt die Reihenfolge zurück Elemente des Arrays ist die Durchlaufreihenfolge

Diese Methode ist eine horizontale Durchquerung des DOM-Baums, beginnend mit dem ersten untergeordneten Knoten des Knotens, durchläuft alle seine Geschwisterknoten und durchläuft dann die untergeordneten Knoten des ersten Knotens. Nach Abschluss der Durchquerung werden wir nicht darauf eingehen Tiefe vorerst und beginnen Sie mit der Durchquerung seiner Geschwisterknoten. Wie in der Abbildung gezeigt (die Durchlaufreihenfolge ist die rote Schlossmarkierung):

Code des js-Implementierungsalgorithmus (rekursive Version):

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

Die rekursive Version Der Grund für BFS ist: Wenn die Ebene zu tief ist, führt dies zu einem Stapelüberlauf: Die maximale Aufrufstapelgröße wurde überschritten, aber es gibt immer noch kein Problem mit der Durchlaufreihenfolge. Sie können Operationen während des Durchlaufvorgangs ausführen, ohne das durchquerte Array zurückzugeben.

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

Konsolenausgabe:

Zusammenfassung: BFS und DFS sind beide Diagrammalgorithmen. Die in beschriebene Version Dieser Artikel ist relativ einfach und stellt ein ungerichtetes und nicht verbundenes Diagramm dar. Weitere JavaScript-basierte Algorithmen werden in Zukunft aktualisiert.

Dieser Artikel ist hier zu Ende. Weitere spannende Inhalte finden Sie in der Spalte

JavaScript-Video-Tutorial

auf der chinesischen PHP-Website!

Das obige ist der detaillierte Inhalt vonEinführung in die JavaScript-Algorithmen Depth-First-Traversal (DFS) und Breite-First-Traversal (BFS).. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!