Hola, soy Miguel y en esta ocasión les traigo este tutorial.
Me encontré con este interesante problema algorítmico del mundo real recientemente y me asombró la cantidad de respuestas incorrectas e irrelevantes que encontré en toda la web.
La ejecución de una búsqueda de «DOM
de búsqueda en profundidad primero» o «DOM de búsqueda primero en amplitud» reveló una gran cantidad de información tangencial y enfoques abstractos en pseudocódigo.
Algunos de ellos incluso habían sido votados como la respuesta «correcta» y en realidad estaban equivocados o producían resultados incorrectos. ¡Así que decidí llegar al fondo de esto! (Punny, ¿eh?)
Echemos un vistazo a estos dos métodos para atravesar el DOM
y realmente veamos las similitudes y diferencias:
Búsqueda / recorrido DOM
en profundidad primero
Comencemos con un árbol DOM
básico (en realidad es un subárbol, ya que el document
es el nodo raíz real):
<div class="a"> <div class="aa"> <div class="aaa"></div> <div class="aab"></div> </div> <div class="ab"> <div class="aba"></div> <div class="abb"></div> </div> </div><div id="results"></div>
Tenga en cuenta que tenemos un div de resultados al final para registrar nuestro resultado y verificar el orden correcto.
Primero, averigüemos qué produciría un recorrido en profundidad en este caso. Por clase, nuestro recorrido debe estar en este orden:
a, aa, aaa, aab, ab, aba, abb
Frio. Ahora, ¿cómo hacemos (realmente) eso? Primero, anotemos algunas consideraciones / enfoque:
- Necesitaremos alguna estructura de datos para almacenar los nodos que necesitamos visitar.
- Necesitaremos alguna estructura de datos para almacenar los nodos que ya hemos visitado, por lo que no hay duplicados (la profundidad primero sigue el lado más a la izquierda hasta abajo, luego se repite para cada subárbol / hijo).
- Tendremos que caminar todo el camino hasta
aab
antes de visitarab
.
Muy bien, veamos un código:
function dfs() { const nodesToVisit = []; const visitedNodes = []; nodes.push(document.getElementsByClassName("a")[0]); const log = document.getElementById("results"); // Do work here... }
Este es un buen comienzo. Por ya visitedNodes
, usamos una matriz simple, porque solo necesitamos verificar si existe un nodo actual en la matriz.
Sin embargo, para nodesToVisit
en un recorrido de profundidad primero, necesitaremos una pila.
Bien, entonces … ¿qué es una pila de nuevo? A veces también se la conoce como cola LIFO o cola de “último en entrar, primero en salir”.
Pero no necesitamos usar ninguna estructura de datos sofisticada o clase extendida en Javascript para que nuestra matriz normal funcione como una pila.
Tenemos estos métodos disponibles para usar para colocar nodos y sacarlos de nuestra matriz:
-
Array.prototype.push(item)
– Este método «empujará» elementos al final / cola (lado derecho, índice más alto) de la matriz. -
Array.prototype.unshift(item)
– Este método «empujará» elementos al frente / cabeza (lado izquierdo, índice más bajo) de la matriz. -
Array.prototype.pop()
– Este método «sacará» un elemento del final / cola (lado derecho, índice más alto) de la matriz. -
Array.prototype.shift()
– Este método «sacará» un elemento de la parte frontal / encabezado (lado izquierdo, índice más bajo) de la matriz.
Como puede ver, estos cuatro métodos en el Array nos permitirán usar una única estructura de datos ya sea como una cola LIFO, una cola FIFO o una Deque (Cola de Doble Final – pronunciada “cubierta”), que se ajusta a cualquier propósito que necesitemos.
Para implementar una pila, necesitaremos .push()
nuestros nodos en la pila y luego .pop()
ellos afuera.
Bien, pongámonos a trabajar en el recorrido:
1. Comencemos un ciclo while
, que continúa hasta que la pila está vacía:
// var declarations, etc...while (nodesToVisit.length > 0) // visit nodes, do something with each...
2. Tome un nodo de la pila y configúrelo como currentNode
:
// var declarations, etc... while (nodesToVisit.length > 0) { let currentNode = nodesToVisit.pop(); // from the end! if (currentNode && !visitedNodes.includes(currentNode)) { // we have an unvisited node! let's log it!... } }
3. Marque el nodo como visitado y regístrelo:
// var declarations, etc...while (nodesToVisit.length > 0) { let currentNode = nodesToVisit.pop(); // from the end!if (currentNode && !visitedNodes.includes(currentNode)) { visitedNodes.push(currentNode); if (currentNode.nodeType == 1) { let logItem = document.createElement("p"); let logText = document.createTextNode(currentNode.className); logItem.appendChild(logText); log.appendChild(logItem); } // Now, we'll need to get the next nodes onto the stack... } }
De acuerdo, aquí están pasando un poco. La mayor parte está relacionada con el registro del className
de los divs
en el contenedor de resultados para que podamos verificar el orden.
Tenga en cuenta que estamos presionando currentNode
en la formación visitedNodes
.
Las siguientes líneas de código son:
- Comprobando el
currentNode
para sunodeType
. Cuando examina unDOM
, encontrará que los saltos de línea, los espacios, todos los caracteres y símbolos que componen el marcado original, todos encuentran su camino hacia elDOM
. No queremos registrar nuestros saltos de línea y otros elementos no semánticos. losnodeType
para nuestros elementos semánticos será1
, por lo que probamos eso y omitimos elementos que tienen un tipo diferente. - Luego hacemos algo de manipulación
DOM
creando nuevos elementos para ponerlos en el registro de resultados y agregarlos al padre<div id="results">
.
4. Por último, necesitamos incluir a los niños en la pila:
// var declarations, etc... while (nodesToVisit.length > 0) { let currentNode = nodesToVisit.pop(); // from the end! if (currentNode && !visitedNodes.includes(currentNode)) { visitedNodes.push(currentNode); if (currentNode.nodeType == 1) { let logItem = document.createElement("p"); let logText = document.createTextNode(currentNode.className); logItem.appendChild(logText); log.appendChild(logItem); } [].slice.call(currentNode.childNodes).reverse() .forEach(function(node) { nodesToVisit.push(node); }) } }
Repasemos la última línea agregada aquí:
-
[].slice.call(currentNode.childNodes)
– Si solo llamamoscurrentNode.childNodes()
devolverá un objeto de tipoNodeList
que no tiene muchas de las propiedades y métodos de un Array, por lo que usamos esta convención de JavaScript para convertir el resultado en un Array. -
.reverse()
– ¿Por qué invertimos aquí? Pensemos. Si tomamos los resultados dechildNodes
, en orden, se colocarán en nuestra cola como“aa, ab, ...”
y cuando los saquemos, primero obtendremos los niños en la parte inferior. Entonces invertimos los niños antes de ponerlos en la pila. - Finalmente, para cada nodo hijo, lo colocamos en la pila para ser visitado.
Nuestra final Función transversal de DOM en profundidad parece:
function dfs() { const nodesToVisit = []; const visitedNodes = []; nodes.push(document.getElementsByClassName("a")[0]); const log = document.getElementById("results"); while (nodesToVisit.length > 0) { let currentNode = nodesToVisit.pop(); // from the end! if (currentNode && !visitedNodes.includes(currentNode)) { visitedNodes.push(currentNode); if (currentNode.nodeType == 1) { let logItem = document.createElement("p"); let logText = document.createTextNode(currentNode.className); logItem.appendChild(logText); log.appendChild(logItem); } [].slice.call(currentNode.childNodes).reverse() .forEach(function(node) { nodesToVisit.push(node); }) } } }
Y produce los resultados:
a aa aaa aab ab aba abb
¡Funciona! Está bien, muuuuy … ¿qué pasa con Recorridos DOM en amplitud primero?
Recorrido / búsqueda de DOM
primero en amplitud
Y si te dijera que ¡¿El 97%
del código anterior se puede reutilizar para hacer un recorrido primero en amplitud ?!
Para los recorridos en amplitud primero, necesitamos un cola en lugar de un pila.
Si lo pensamos bien, ¡lo único que debe cambiar es el orden en el que se colocan los nodos y se extraen de la matriz!
Esto es lo que cambiaremos:
- No revertiremos el orden de los
childNodes
antes de colocarlos en la cola. - Lo haremos
shift()
elementos del frente de la cola en lugar de sacarlos al final.
Lo que produce esta función final para Recorrido DOM en amplitud primero:
function bfs() { const nodesToVisit = []; const visitedNodes = []; nodes.push(document.getElementsByClassName("a")[0]); const log = document.getElementById("results"); while (nodesToVisit.length > 0) { let currentNode = nodesToVisit.shift(); // from the front! if (currentNode && !visitedNodes.includes(currentNode)) { visitedNodes.push(currentNode); if (currentNode.nodeType == 1) { let logItem = document.createElement("p"); let logText = document.createTextNode(currentNode.className); logItem.appendChild(logText); log.appendChild(logItem); } [].slice.call(currentNode.childNodes) .forEach(function(node) { nodesToVisit.push(node); }) } } }
Lo que produce este resultado:
a aa ab aaa aab aba abb
¡Funciona!
- Las búsquedas y el recorrido
DOM
en profundidad primero usan unLIFO pila
. Asegúrese de invertir el orden de loschildNodes
de cadacurrentNode
antes de ponerlos en la pila, o saldrán fuera de orden. - Las búsquedas / recorridos
DOM
en amplitud primero usan unFIFO
cola. No es necesario invertir loschildNodes
de cadacurrentNode
antes de colocarlos en la cola. - Utilice una matriz o un hash para realizar un seguimiento de los nodos ya visitados.
- ¡Que te diviertas!
Gracias por leer este tutorial.
Añadir comentario