¿Qué Qué es el algoritmo BFS (búsqueda primero en amplitud)?
La búsqueda en amplitud primero (BFS) es un algoritmo que se utiliza para graficar datos o árboles de búsqueda o estructuras transversales. La forma completa de BFS es la búsqueda en amplitud primero.
El algoritmo visita y marca de manera eficiente todos los nodos clave en un gráfico de manera precisa a lo ancho. Este algoritmo selecciona un solo nodo (punto inicial o fuente) en un gráfico y luego visita todos los nodos adyacentes al nodo seleccionado. Recuerde, BFS accede a estos nodos uno por uno.
Una vez que el algoritmo visita y marca el nodo de inicio, se mueve 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 todos los nodos del gráfico se hayan visitado y marcado con éxito.
En este tutorial de algoritmos, aprenderá:
- ¿Qué es el algoritmo BFS (búsqueda primero en amplitud)?
- ¿Qué son los recorridos de Graph?
- La arquitectura del algoritmo BFS
- ¿Por qué necesitamos el algoritmo BFS?
- ¿Cómo funciona el algoritmo BFS?
- Ejemplo de algoritmo BFS
- Reglas del algoritmo BFS
- Aplicaciones del algoritmo BFS
¿Qué son los recorridos de gráficos?
Un recorrido de gráfico es una metodología comúnmente utilizada para ubicar 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 junto con marcar la secuencia de los vértices visitados. Este proceso le permite visitar rápidamente cada nodo en un gráfico sin estar bloqueado en un bucle infinito.
La arquitectura del algoritmo BFS
- En los distintos niveles de datos, puede marcar cualquier nodo como inicio o nodo inicial para comenzar a atravesar. El BFS visitará el nodo, lo marcará como visitado y lo colocará en la cola.
- 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.
- De manera similar, los nodos restantes más cercanos y no visitados en el gráfico se analizan marcados y se agregan a la cola. Estos elementos se eliminan de la cola cuando se reciben y se imprimen como resultado.
¿Por qué necesitamos el algoritmo BFS?
Existen numerosas razones para utilizar el algoritmo BFS para buscar 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 la ruta más corta para atravesarlos.
- BFS puede atravesar 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 BFS son perfectas 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 en forma de árbol. Los recorridos de gráficos se clasifican según el orden en el que visitan los nodos del gráfico.
El algoritmo BFS inicia la operación desde el primer nodo o el nodo inicial en un gráfico y lo recorre a fondo. Una vez que atraviesa con éxito el nodo inicial, se visita y marca el siguiente vértice no atravesado del gráfico.
Por lo tanto, puede decir que todos los nodos adyacentes al vértice actual se visitan y se recorren en la primera iteración. Se utiliza una metodología de cola simple para implementar el funcionamiento de un algoritmo BFS, y consta de los siguientes pasos:
Paso 1)
Se conoce cada vértice o nodo del gráfico. Por ejemplo, puede marcar el nodo como V.
Paso 2)
En caso de que no se acceda al vértice V, agregue el vértice V a la cola BFS
Paso 3)
Inicie la búsqueda BFS y, una vez finalizada, marque el vértice V como visitado.
Paso 4)
La cola BFS todavía está no vacío, por lo tanto, elimine el vértice V del gráfico de la cola.
Paso 5)
Recupera todos los vértices restantes en el gráfico adyacente al vértice V
Paso 6)
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)
BFS visitará la V1, la marcará como visitada y la eliminará de la cola.
Algoritmo BFS de ejemplo
Paso 1)
Tienes una gráfica de siete números que van del 0 al 6.
Paso 2)
Se ha marcado 0 o cero como nodo raíz.
Paso 3)
Se visita, marca e inserta 0 en la estructura de datos de la cola.
Paso 4)
Los 0 nodos adyacentes y no visitados restantes se visitan, marcan e insertan en la cola.
Paso 5)
Las iteraciones de desplazamiento se repiten hasta que se visitan todos los nodos.
Reglas del algoritmo BFS
Aquí están las reglas importantes para usar el algoritmo BFS:
- Una estructura de datos de cola (FIFO-First in First Out) 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 en el gráfico y los sigue descartando como completados.
- BFS visita un nodo no visitado adyacente, lo marca como hecho 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 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
Tomemos un observe algunas de las aplicaciones de la vida real en las que la implementación de un algoritmo BFS puede ser 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: BFS se puede implementar para ubicar todos los nodos más cercanos o vecinos en una red peer to peer. Esto encontrará los datos requeridos más rápido .
- Rastreadores web: los motores de búsqueda o los rastreadores web pueden crear fácilmente varios niveles de índices utilizando 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.
- Network Broadcast ing: un paquete transmitido es guiado por el algoritmo BFS para encontrar y llegar a todos los nodos para los que tiene la dirección.
Resumen
- Un recorrido de gráfico es un proceso único que requiere que el algoritmo visite, verifique y / o actualice cada nodo no visitado en un estructura en forma de árbol. El algoritmo BFS funciona con 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 atraviesa 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 en el gráfico primero se elimina primero y se imprime como resultado.
- El algoritmo BFS nunca puede quedar atrapado en un bucle infinito.
- Debido a la alta precisión y la implementación robusta, BFS se utiliza en múltiples soluciones de la vida real como redes P2P, Web Crawlers, y radiodifusión en red.