Algoritmo de búsqueda en amplitud (BFS) con EJEMPLO

¿Qué es el algoritmo BFS (búsqueda primero en amplitud)?

La búsqueda en amplitud (BFS) es un algoritmo que se utiliza para graficar datos o buscar árboles o recorrer estructuras. La forma completa de BFS es búsqueda en amplitud.

El algoritmo visita y marca de manera eficiente todos los nodos clave de un gráfico de manera precisa y en toda su amplitud. Este algoritmo selecciona un solo nodo (punto inicial o de origen) en un gráfico y luego visita todos los nodos adyacentes al nodo seleccionado. Recuerde que BFS accede a estos nodos uno por uno.

Una vez que el algoritmo visita y marca el nodo de inicio, se desplaza hacia los nodos no visitados más cercanos y los analiza. Una vez visitados, se marcan todos los nodos. Estas iteraciones continúan hasta que se hayan visitado y marcado con éxito todos los nodos del grafo.

¿Qué son los recorridos de gráficos?

Un recorrido de gráfico es una metodología comúnmente utilizada para localizar la posición del vértice en el gráfico. Es un algoritmo de búsqueda avanzada que puede analizar el gráfico con rapidez y precisión además de marcar la secuencia de los vértices visitados. Este proceso le permite visitar rápidamente cada nodo de un gráfico sin quedar atrapado en un bucle infinito.

La arquitectura del algoritmo BFS

Architectura del algoritmo BFS

  1. En los distintos niveles de datos, puede marcar cualquier nodo como nodo inicial o inicial para comenzar a recorrer. El BFS visitará el nodo, lo marcará como visitado y lo colocará en la cola.
  2. Ahora el BFS visitará los nodos más cercanos y no visitados y los marcará. Estos valores también se agregan a la cola. La cola funciona en el modelo FIFO.
  3. De manera similar, los nodos restantes más cercanos y no visitados en el gráfico se analizan, se marcan y se agregan a la cola. Estos elementos se eliminan de la cola a medida que se reciben y se imprimen como resultado.

¿Por qué necesitamos el algoritmo BFS?

Existen numerosas razones para utilizar el algoritmo BFS para realizar búsquedas en su conjunto de datos. Algunos de los aspectos más importantes que hacen de este algoritmo su primera opción son:

  • BFS es útil para analizar los nodos en un gráfico y construir el camino más corto para atravesarlos.
  • BFS puede recorrer un gráfico en el menor número de iteraciones.
  • La arquitectura del algoritmo BFS es simple y robusta.
  • El resultado del algoritmo BFS tiene un alto nivel de precisión en comparación con otros algoritmos.
  • Las iteraciones de BFS son fluidas y no hay posibilidad de que este algoritmo quede atrapado en un problema de bucle infinito.

¿Cómo funciona el algoritmo BFS?

El recorrido del gráfico requiere que el algoritmo visite, verifique y/o actualice cada nodo no visitado en una estructura similar a un árbol. Los recorridos de gráficos se clasifican según el orden en que visitan los nodos del gráfico.

El algoritmo BFS inicia la operación desde el primer nodo o nodo inicial de un gráfico y lo recorre en profundidad. Una vez que recorre con éxito el nodo inicial, se visita y marca el siguiente vértice no recorrido del gráfico.

Por lo tanto, se puede decir que todos los nodos adyacentes al vértice actual se visitan y recorren en la primera iteración. Se utiliza una metodología de cola simple para implementar el funcionamiento de un algoritmo BFS, que consta de los siguientes pasos:

Paso 1)

Funcionamiento del algoritmo BFS

Se conoce cada vértice o nodo del gráfico. Por ejemplo, puede marcar el nodo como V.

Paso 2)

Funcionamiento del algoritmo BFS

En caso de que no se acceda al vértice V, agregue el vértice V a la cola BFS

Paso 3)

Funcionamiento del algoritmo BFS

Inicie la búsqueda BFS y, una vez completada, marque el vértice V como visitado.

Paso 4)

Funcionamiento del algoritmo BFS

La cola BFS aún no está vacía, por lo tanto, elimine el vértice V del gráfico de la cola.

Paso 5)

Funcionamiento del algoritmo BFS

Recupera todos los vértices restantes del gráfico que son adyacentes al vértice V

Paso 6)

Funcionamiento del algoritmo BFS

Para cada vértice adyacente, digamos V1, en caso de que aún no se haya visitado, agregue V1 a la cola BFS.

Paso 7)

Funcionamiento del algoritmo BFS

BFS visitará V1, lo marcará como visitado y lo eliminará de la cola.

Ejemplo de algoritmo BFS

Paso 1)

Ejemplo de algoritmo BFS

Tienes un gráfico de siete números que van del 0 al 6.

Paso 2)

Ejemplo de algoritmo BFS

Se ha marcado 0 o cero como nodo raíz.

Paso 3)

Ejemplo de algoritmo BFS

0 se visita, se marca y se inserta en la estructura de datos de la cola.

Paso 4)

Ejemplo de algoritmo BFS

Los 0 nodos adyacentes y no visitados restantes se visitan, marcan e insertan en la cola.

Paso 5)

Ejemplo de algoritmo BFS

Las iteraciones de recorrido se repiten hasta que se visitan todos los nodos.

Reglas del algoritmo BFS

A continuación se detallan reglas importantes para usar el algoritmo BFS:

  • Una cola (FIFO-Primero en entrar, primero en salir) estructura de datos es utilizado por BFS.
  • Marca cualquier nodo en el gráfico como raíz y comienza a recorrer los datos desde él.
  • BFS atraviesa todos los nodos del gráfico y los sigue eliminando hasta que se completan.
  • BFS visita un nodo adyacente no visitado, lo marca como finalizado y lo inserta en una cola.
  • Elimina el vértice anterior de la cola en caso de que no se encuentre ningún vértice adyacente.
  • El algoritmo BFS se itera hasta que todos los vértices del gráfico se atraviesan con éxito y se marcan como completados.
  • No hay bucles causados ​​por BFS durante el recorrido de datos desde cualquier nodo.

Aplicaciones del algoritmo BFS

Echemos un vistazo a algunas de las aplicaciones de la vida real en las que la implementación de un algoritmo BFS puede resultar muy eficaz.

  • Gráficos no ponderados: El algoritmo BFS puede crear fácilmente la ruta más corta y un árbol de expansión mínimo para visitar todos los vértices del gráfico en el menor tiempo posible con alta precisión.
  • Redes P2P: Se puede implementar BFS para localizar todos los nodos más cercanos o vecinos en una red peer to peer. Esto permitirá encontrar los datos necesarios más rápidamente.
  • Rastreadores web: Los motores de búsqueda o los rastreadores web pueden crear fácilmente múltiples niveles de índices empleando BFS. La implementación de BFS comienza desde la fuente, que es la página web, y luego visita todos los enlaces de esa fuente.
  • Sistemas de navegación: BFS puede ayudar a encontrar todas las ubicaciones vecinas desde la ubicación principal o de origen.
  • Transmisión en red: Un paquete difundido es guiado por el algoritmo BFS para encontrar y llegar a todos los nodos para los que tiene la dirección.

Resum

  • Un recorrido de gráfico es un proceso único que requiere que el algoritmo visite, verifique y/o actualice cada nodo no visitado en una estructura similar a un árbol. El algoritmo BFS funciona según un principio similar.
  • El algoritmo es útil para analizar los nodos en un gráfico y construir el camino más corto para atravesarlos.
  • El algoritmo recorre el gráfico en el menor número de iteraciones y en el menor tiempo posible.
  • BFS selecciona un solo nodo (punto inicial o de origen) en un gráfico y luego visita todos los nodos adyacentes al nodo seleccionado. BFS accede a estos nodos uno por uno.
  • BFS coloca los datos visitados y marcados en una cola. Una cola funciona por orden de llegada. Por lo tanto, el elemento colocado primero en el gráfico se elimina primero y se imprime como resultado.
  • El algoritmo BFS nunca puede quedar atrapado en un bucle infinito.
  • Debido a su alta precisión y su implementación robusta, BFS se utiliza en múltiples soluciones de la vida real, como redes P2P, rastreadores web y transmisión en red.