Búsqueda primero en amplitud: una guía transversal de gráficos BFS con 3 ejemplos de códigos de lectura

Breadth First Search (BFS) es uno de los algoritmos más populares para buscar o recorrer una estructura de datos de árbol o gráfico. En este tutorial, aprenderemos brevemente cómo funciona BFS y exploraremos un patrón básico que puede usarse para resolver algunos problemas medios y fáciles en Leetcode.

Empecemos, ¿de acuerdo?

¿Qué es Breadth First Search?

Entonces, todos sabemos que una gráfica es un conjunto de vértices y aristas: G = {V, E}. Atravesar un gráfico significa visitar cada vértice y cada borde exactamente una vez de manera ordenada.

En BFS, estamos obligados a recorrer el gráfico a lo ancho o a nivel. Esto significa que primero nos moveríamos horizontalmente y visitaríamos todos los nodos de la capa actual antes de pasar a la siguiente.

Por lo tanto, siempre que se nos pida que hagamos algún recorrido de orden de nivel, podemos usar la técnica BFS.

En BFS, comenzaríamos a atravesar desde 1 (el nodo raíz) y visitaríamos sus nodos secundarios 8, 5 y 2. Los almacenaríamos en el orden en que fueron visitados. Esto nos permitiría visitar los nodos secundarios de 8 primero (es decir, 6, 4 y 3), luego de 5 (es decir, nulo), y luego de 2 (es decir, 9) y así sucesivamente.

Implementación

Para implementar BFS, se utiliza una estructura de datos de cola . La cola almacena el nodo y lo marca como 'visitado' hasta que se marcan todos sus vértices adyacentes.

La cola sigue el método Primero en entrar, primero en salir (FIFO). Esto significa que los vecinos del nodo serán visitados en el orden en que fueron insertados.

Hechizo mágico BFS:

  1. Agregar un nodo a la cola
  2. Quitar nodo
  3. Recuperar vecinos no visitados del nodo eliminado, agregarlos a la cola
  4. Repita los pasos 1, 2 y 3 siempre que la cola no esté vacía.

Ahora veamos algunos problemas de Leetcode y apliquemos lo que hemos aprendido.

102. Desplazamiento de orden a nivel de árbol binario (dificultad: media)

La pregunta nos pide que recorramos el gráfico e imprimamos los nodos de cada nivel en una lista vinculada. Para resolver este, ¡todo lo que tenemos que hacer es aplicar nuestro hechizo mágico!

Asegúrese de comprender bien el código, ya que esta es la plantilla básica que usaremos para resolver varios problemas. Así que repasemos esto.

En el código anterior, primero insertamos el nodo raíz en la cola. Si bien la cola no está vacía, hemos eliminado este nodo de la cola e insertado su hijo izquierdo y derecho en la cola.

Pero antes de eso, verificamos si cada uno de sus hijos es nulo o no. Si es nulo, habríamos obtenido una excepción de puntero nulo.

El proceso se repite nuevamente con los siguientes elementos que quedan en la cola. El bucle forse mantiene para darnos la lista de nodos en cada nivel en listas vinculadas separadas.

637. Promedio de niveles en un árbol binario (dificultad: fácil)

Esta pregunta nos dice que encontremos el valor promedio de los nodos en cada nivel de un árbol binario en una matriz. Esto sigue el mismo procedimiento que nuestro problema anterior con un pequeño ajuste.

Como puede ver, todo lo que hicimos fue copiar y pegar el código de la plantilla. Luego, simplemente colocamos una variable de suma dentro del ciclo for que puede darnos la suma de los valores de los nodos en cada nivel. Esto es lo que usaremos para calcular nuestro promedio deseado.

429. Cruce de orden a nivel de árbol n-ario (dificultad: media)

Un árbol en el que cada nodo no tiene más de N número de hijos se llama árbol N-ario.

Esto sigue exactamente el mismo procedimiento que el recorrido de un árbol binario, excepto por el hecho de que aquí insertamos todos los hijos de un nodo en la cola. Recuerde que al resolver problemas relacionados con el árbol binario, solo hemos insertado los hijos izquierdo y derecho de cualquier nodo dado en la cola.

¡Eso es todo! Espero que esto te haya ayudado a comprender mejor BFS y que hayas disfrutado del tutorial. ¡Recomiende esta publicación si cree que puede ser útil para otra persona!