Cuando se trata de aprender, generalmente hay dos enfoques que uno puede tomar: puede ir amplio y tratar de cubrir la mayor cantidad posible del espectro de un campo, o puede profundizar y tratar de ser realmente muy específico con el tema que está aprendiendo. La mayoría de los buenos estudiantes saben que, hasta cierto punto, todo lo que aprendes en la vida, desde algoritmos hasta habilidades básicas para la vida, implica una combinación de estos dos enfoques.

Lo mismo ocurre con la informática, la resolución de problemas, y estructuras de datos. La semana pasada, nos sumergimos profundamente en la búsqueda en profundidad y aprendimos lo que significa realmente atravesar un árbol de búsqueda binaria. Ahora que hemos profundizado, tiene sentido que ampliemos y comprendamos la otra estrategia común de recorrido de árbol.

En otras palabras, es el momento que todos han estado esperando: es el momento para desglosar los conceptos básicos de la búsqueda primero en amplitud.

Una de las mejores formas de entender qué es exactamente la búsqueda en amplitud (BFS) es entendiendo lo que no es. Es decir, si comparamos BFS con DFS, será mucho más fácil para nosotros mantenerlos claros en nuestra cabeza. Entonces, refresquemos nuestra memoria de la búsqueda en profundidad antes de continuar.

Sabemos que la búsqueda en profundidad es el proceso de atravesar una rama de un árbol hasta llegar a una hoja, y luego regresar al «tronco» del árbol. En otras palabras, implementar un DFS significa atravesar los subárboles de un árbol de búsqueda binaria.

De acuerdo, entonces ¿cómo funciona la amplitud primero ¿La búsqueda se compara con eso? Bueno, si lo pensamos bien, la única alternativa real a viajar por una rama de un árbol y luego por otra es viajar por el árbol sección por sección, o nivel por nivel. Y eso es exactamente lo que es BFS !

La búsqueda en amplitud implica la búsqueda en un árbol de un nivel a la vez.

Nosotros atraviesa primero un nivel completo de nodos secundarios, antes de pasar a atravesar los nodos nietos. Y atravesamos todo un nivel de nodos de nietos antes de pasar a atravesar nodos de bisnietos.

Muy bien, eso parece bastante claro. ¿Qué más diferencia los dos tipos diferentes de algoritmos de recorrido de árbol? Bueno, ya hemos cubierto las diferencias en los procedimientos de estos dos algoritmos. Pensemos en el otro aspecto importante del que aún no hemos hablado: la implementación.

Primero, comencemos con lo que sabemos. ¿Cómo implementamos la búsqueda en profundidad la semana pasada? Tal vez recuerde que aprendimos tres métodos diferentes (en orden, postorder y preorden) de buscar en un árbol usando DFS. Sin embargo, había algo genial en lo similares que eran estas tres implementaciones; cada uno de ellos podría emplearse mediante la recursividad. También sabemos que, dado que DFS se puede escribir como una función recursiva, pueden hacer que la pila de llamadas crezca hasta ser tan grande como la ruta más larga del árbol.

Sin embargo, había una cosa que dejé La semana pasada parece bueno mencionarlo ahora (¡y tal vez incluso sea un poco obvio!): la pila de llamadas realmente implementa una estructura de datos de pila. ¿Recuerdas esos? Aprendimos acerca de las pilas hace un tiempo, pero aquí están de nuevo, ¡apareciendo por todas partes!

Lo realmente interesante de implementar la búsqueda en profundidad usando una pila es que, a medida que atravesamos los subárboles de una árbol de búsqueda binaria, cada uno de los nodos que «revisamos» o «visitamos» se agrega a la pila. Una vez que llegamos a un nodo hoja, un nodo que no tiene hijos, comenzamos a sacar los nodos de la parte superior de la pila. Terminamos en el nodo raíz nuevamente, y luego podemos continuar recorriendo el siguiente subárbol.

En el ejemplo del árbol DFS anterior, notará que los nodos 2, 3 y 4 se agregan a la parte superior de la pila. Cuando llegamos al «final» de ese subárbol, es decir, cuando llegamos a los nodos hoja de 3 y 4, comenzamos a sacar esos nodos de nuestra pila de «nodos para visitar».Puede ver lo que eventualmente sucederá con el subárbol correcto: los nodos a visitar serán empujados a la pila de llamadas, los visitaremos y los sacaremos sistemáticamente de la pila.

Eventualmente, una vez que hemos visitado los subárboles izquierdo y derecho, estaremos de regreso en el nodo raíz sin nada más que verificar, y nuestra pila de llamadas estará vacía.

Entonces, deberíamos poder usar un estructura de pila y hacer algo similar con nuestra implementación de BFS… ¿verdad? Bueno, no sé si funcionará, pero creo que será útil al menos comenzar dibujando el algoritmo que queremos implementar y ver hasta dónde podemos llegar con él.

Probemos:

Bien, tenemos un gráfico a la izquierda en el que implementamos DFS la semana pasada. ¿Cómo podríamos usar un algoritmo BFS en su lugar?

Bueno, para empezar, sabemos que primero queremos verificar el nodo raíz. Ese es el único nodo al que tendremos acceso inicialmente, por lo que estaremos «apuntando» al nodo f.

Muy bien, ahora tendremos que verificar los hijos de este nodo raíz.

Queremos comprobar un hijo tras otro, así que vayamos primero al hijo de la izquierda: el nodo d es el nodo al que estamos «apuntando» ahora (y el único nodo al que tenemos acceso).

A continuación, queremos ir al nodo hijo correcto.

Uh oh. ¡Espera, el nodo raíz ni siquiera está disponible para nosotros! ¡Y no podemos movernos a la inversa, porque los árboles binarios no tienen enlaces inversos! ¿Cómo vamos a llegar al nodo hijo correcto? Y … oh no, el nodo hijo izquierdo d y el nodo hijo derecho k no están vinculados en absoluto. Entonces, eso significa que es imposible para nosotros saltar de un niño a otro porque no tenemos acceso a nada excepto a los niños del nodo d.

Oh, cielos. No llegamos muy lejos, ¿verdad? Tendremos que encontrar un método diferente para resolver este problema. Necesitamos encontrar alguna forma de implementar un recorrido de árbol que nos permita caminar por el árbol en orden de nivel. Lo más importante que debemos tener en cuenta es esto:

Debemos mantener una referencia a todos los nodos secundarios de cada nodo que visitamos. De lo contrario, nunca podremos volver a ellos más tarde y visitarlos.

Cuanto más lo pienso, más ganas tengo es como si quisiéramos mantener una lista de todos los nodos que aún necesitamos verificar, ¿no es así? Y en el momento en que quiero mantener una lista de algo, mi mente salta inmediatamente a una estructura de datos en particular: ¡una cola, por supuesto!

Veamos si las colas pueden ayudarnos con nuestra implementación de BFS.

¡Colas al rescate!

Resulta que una gran diferencia entre la búsqueda en profundidad y la búsqueda en amplitud es la estructura de datos utilizada para implementar estos dos algoritmos muy diferentes.

Mientras que DFS usa una estructura de datos de pila, BFS se apoya en la estructura de datos de cola. Lo bueno de usar colas es que resuelve el mismo problema que descubrimos anteriormente: nos permite mantener una referencia a los nodos a los que queremos volver, aunque no los hayamos revisado / visitado todavía.

Agregamos nodos que hemos descubierto, pero que aún no hemos visitado, a nuestra cola y volvemos a ellos más tarde.

Un término común para los nodos que agregamos a nuestra cola es nodos descubiertos; un nodo descubierto es uno que agregamos a nuestra cola, cuya ubicación conocemos, pero que aún no hemos visitado. De hecho, esto es exactamente lo que hace que una cola sea la estructura perfecta para resolver el problema de BFS.

En el gráfico de la izquierda, comenzamos agregando el nodo raíz a nuestra cola, ya que ese es el único nodo que hemos tener acceso (al menos, inicialmente) en un árbol. Esto significa que el nodo raíz es el único nodo descubierto para comenzar.

Una vez que tenemos al menos un nodo en cola, podemos comenzar el proceso de visitar los nodos y agregar referencias a sus nodos secundarios en nuestra cola.

Bien, todo esto puede sonar un poco confuso. ¡Y eso está bien! Creo que será mucho más fácil de entender si lo dividimos en pasos más simples.

Para cada nodo en nuestra cola, siempre comenzando con el nodo raíz, queremos hacer tres cosas:

1. Visite el nodo, lo que generalmente solo significa imprimir su valor.
2. Agregue el elemento secundario izquierdo del nodo a nuestra cola.
3. Agregue el elemento secundario derecho del nodo child a nuestra cola.

Una vez que hacemos estas tres cosas, podemos eliminar el nodo de nuestra cola, ¡porque ya no lo necesitamos!Básicamente, tenemos que seguir haciendo esto repetidamente hasta que lleguemos al punto en el que nuestra cola esté vacía.

¡Bien, veamos esto en acción!

En el gráfico a continuación, comenzamos con el nodo raíz, nodo f, como el único nodo descubierto. ¿Recuerdas nuestros tres pasos? Hagámoslos ahora:

1. Visitaremos el nodo f e imprimiremos su valor.
2. Pondremos una referencia a su hijo izquierdo, el nodo d.
3. Pondremos en cola una referencia a su hijo derecho, el nodo k.

¡Y luego, eliminaremos el nodo f de nuestra cola!

El siguiente nodo al principio de la cola es el nodo d. Nuevamente, los mismos tres pasos aquí: imprima su valor, agregue su hijo izquierdo, agregue su hijo derecho y luego elimínelo de la cola.

Nuestra cola ahora tiene referencias a los nodos k, b y e . Si seguimos repitiendo este proceso sistemáticamente, notaremos que en realidad estamos atravesando el gráfico e imprimiendo los nodos en orden de nivel. ¡Hurra! Eso es exactamente lo que queríamos hacer en primer lugar.

La clave para que esto funcione tan bien es la naturaleza misma de la estructura de la cola. Las colas siguen el principio de primero en entrar, primero en salir (FIFO), lo que significa que lo que se colocó primero en la cola es el primer elemento que se leerá y eliminará de la cola.

Por último, ya que estamos en el tema de las colas, vale la pena mencionar que la complejidad espacio-temporal de un algoritmo BFS también está relacionada con la cola que usamos para implementarlo, quién sabía que las colas volverían para ser tan útil, ¿verdad?

La complejidad de tiempo de un algoritmo BFS depende directamente de cuánto tiempo lleva visitar un nodo. Dado que el tiempo que lleva leer el valor de un nodo y poner en cola a sus hijos no cambia según el nodo, podemos decir que visitar un nodo lleva un tiempo constante, o tiempo O (1). Dado que solo visitamos cada nodo en un recorrido de árbol BFS exactamente una vez, el tiempo que nos tomará leer cada nodo realmente depende de cuántos nodos hay en el árbol. Si nuestro árbol tiene 15 nodos, nos llevará O (15); pero si nuestro árbol tiene 1500 nodos, nos llevará O (1500). Por lo tanto, la complejidad temporal de un algoritmo de búsqueda de amplitud primero requiere tiempo lineal, o O (n), donde n es el número de nodos en el árbol.

La complejidad del espacio es similar a esto, hacer con cuánto crece y se reduce nuestra cola a medida que agregamos los nodos que necesitamos verificar. En el peor de los casos, podríamos estar poniendo en cola todos los nodos en un árbol si todos son hijos entre sí, lo que significa que posiblemente podríamos estar usando tanta memoria como nodos hay en el árbol. Si el tamaño de la cola puede crecer hasta ser el número de nodos en el árbol, la complejidad del espacio para un algoritmo BFS también es tiempo lineal, u O (n), donde n es el número de nodos en el árbol.

Todo esto está muy bien, pero ¿sabes lo que realmente me gustaría hacer ahora mismo? ¡Me gustaría escribir uno de estos algoritmos! Por fin, pongamos en práctica toda esta teoría.

Codificando nuestro primer algoritmo de búsqueda en amplitud

¡Lo logramos! Finalmente vamos a codificar nuestro primer algoritmo BFS. Hicimos un poco de esto la semana pasada con algoritmos DFS, así que intentemos escribir también una implementación de búsqueda en amplitud.

Puede recordar que escribimos esto en JavaScript vanilla la semana pasada, así que nos quedaremos con eso de nuevo por el bien de la coherencia. En caso de que necesite un repaso rápido, decidimos mantenerlo simple y escribir nuestros objetos de nodo como Objetos de JavaScript antiguos simples (POJO), así:

node1 = {
data: 1,
left: referenceToLeftNode,
right: referenceToRightNode
};

Está bien, genial. Un paso hecho.

Pero ahora que conocemos las colas y estamos seguros de que necesitaremos usar una para implementar este algoritmo … probablemente deberíamos averiguar cómo hacer eso en JavaScript, ¿verdad? Bueno, resulta que es muy fácil crear un objeto similar a una cola en JS.

Podemos usar una matriz, que hace el truco bastante bien:

Si quisiéramos hacer esto un poco más elegante, probablemente también podríamos crear un objeto Queue, que puede tener una función útil como top o isEmpty; pero, por ahora, confiaremos en una funcionalidad muy simple.

Bien, ¡escribamos este cachorro! Crearemos una función levelOrderSearch, que incluye un objeto rootNode.

¡Genial! En realidad, esto es … bastante simple. O al menos, mucho más simple de lo que esperaba. Todo lo que estamos haciendo aquí es usar un bucle while para continuar con esos tres pasos de verificar un nodo, agregar su hijo izquierdo y agregar su hijo derecho.Continuamos iterando a través de la matriz queue hasta que todo se haya eliminado y su longitud sea 0.

Asombroso. ¡Nuestra experiencia en algoritmos se ha disparado en solo un día! No solo sabemos cómo escribir algoritmos de recorrido de árbol recursivo, sino que ahora también sabemos cómo escribir algoritmos iterativos. ¡Quién diría que las búsquedas algorítmicas podrían ser tan poderosas!

Recursos

Todavía hay mucho que aprender sobre la búsqueda en amplitud y cuándo puede ser útil. Afortunadamente, hay toneladas de recursos que cubren información que no pude incluir en esta publicación. Echa un vistazo a algunos de los realmente buenos a continuación.

1. Algoritmos DFS y BFS que usan pilas y colas, profesor Lawrence L. Larmore
2. El algoritmo de búsqueda primero en amplitud, Khan Academy
3. Estructura de datos: primer recorrido en amplitud, TutorialsPoint
4. Árbol binario: recorrido en orden de nivel, mycodeschool
5. Recorrido en primer lugar en amplitud de un árbol, Departamento de Informática de Universidad de Boston