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

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

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

JavaScript-Video-Tutorial

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!