Algoritmo de búsqueda en amplitud (BFS) con EJEMPLO
sarah chen
⚡ Resumen inteligente
La búsqueda en amplitud (BFS, por sus siglas en inglés) es un algoritmo que recorre un grafo nivel por nivel, visitando todos los vecinos de un nodo antes de profundizar. Utiliza una cola FIFO y encuentra el camino más corto en grafos no ponderados sin bucles infinitos.
¿Qué es el algoritmo BFS (búsqueda primero en amplitud)?
La búsqueda en anchura (BFS, por sus siglas en inglés) es un algoritmo que se utiliza para graficar datos, buscar en árboles o recorrer estructuras. Las siglas BFS significan búsqueda en anchura.
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
- En los distintos niveles de los datos, se puede marcar cualquier nodo como el nodo inicial para comenzar el recorrido. El algoritmo 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 del grafo 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 la búsqueda 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, 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, agréguelo 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 aún no está vacía, por lo tanto, elimine el vértice V del gráfico de la cola.
Paso 5)
Recupera todos los vértices restantes del grafo que sean adyacentes al vértice V.
Paso 6)
Para cada vértice adyacente, digamos V1, en caso de que aún no haya sido visitado, agregue V1 a la cola BFS.
Paso 7)
BFS visitará V1, lo marcará como visitado y lo eliminará de la cola.
Ejemplo de algoritmo BFS
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)
0 se visita, se marca y se inserta en la estructura de datos de la cola.
Paso 4)
Los nodos restantes adyacentes a 0 y los nodos no visitados se visitan, se marcan y se insertan en la cola.
Paso 5)
Las iteraciones de recorrido se repiten hasta que se visitan todos los nodos.
Reglas del algoritmo BFS
A continuación se presentan reglas importantes para el uso del algoritmo BFS:
- Una cola (FIFO – Primero en entrar, primero en salir) estructura de datos es utilizado por BFS.
- Se marca cualquier nodo del gráfico como la raíz y se comienza a recorrer los datos desde ese nodo.
- BFS recorre todos los nodos del grafo y mantiene el dropping ellos como terminados.
- 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 itera hasta que todos los vértices del grafo se hayan recorrido correctamente y se hayan marcado 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ínima para visitar todos los vértices del grafo en el menor tiempo posible con alta precisión.
- Redes P2P: El algoritmo BFS se puede implementar para localizar todos los nodos más cercanos o vecinos en una red peer-to-peer. Esto permitirá encontrar los datos necesarios con mayor rapidez.
- 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.
