Algoritmo de búsqueda primero en amplitud: descripción general, importancia y aplicaciones

Los gráficos están a nuestro alrededor. Se puede pensar en un gráfico como una red interconectada de nodos y bordes. Tus amigos en Facebook, tus conexiones en LinkedIn o tus seguidores en Twitter/Instagram constituyen tu gráfico social. Del mismo modo, si desea ir del punto A al punto B, puede hacerlo a través de múltiples rutas, que se pueden visualizar en Google Maps.

Todas estas múltiples opciones de ruta desde el punto A hasta el punto B también constituyen un gráfico. Los gráficos se encuentran entre las estructuras de datos más comunes que encontramos en el mundo académico y en el mundo real porque son muy ubicuos. Y una de las operaciones más frecuentes que se pueden realizar en un gráfico es el recorrido de gráficos.

¿Qué es Graph Traversal?

Graph Traversal es un método para visitar cada nodo en un gráfico exactamente una vez con velocidad y precisión. Es un algoritmo avanzado de búsqueda de gráficos que le permite imprimir la secuencia de nodos visitados sin quedar atrapado en un bucle infinito. Hay muchos algoritmos de recorrido de gráficos como la búsqueda primero en profundidad, la búsqueda primero en amplitud , el algoritmo de Djikstra , el algoritmo A-Star y más.

Este artículo profundizará en el algoritmo de búsqueda Breadth First o BFS.

Estructura del gráfico

Antes de echar un vistazo detallado bajo el capó de BFS, familiaricémonos con algunas terminologías gráficas con la ayuda del gráfico anterior:

Nodo raíz : el nodo donde inicia el proceso transversal. Para simplificar, podemos considerar que A es el nodo raíz.

Niveles : un nivel es una colección de todos los nodos que son equidistantes del nodo raíz. Entonces, si consideramos que el nodo A está en el nivel 0, los nodos B y C están en el nivel 1, mientras que los nodos D, E y F están en el nivel 2. Una heurística simple para determinar el número de nivel de un nodo es contar el número de aristas entre dicho nodo y el nodo raíz. Tenga en cuenta que esto solo funciona si define que el nodo raíz esté en el nivel 0.

Nodo principal: el nodo principal de un nodo es el que está un nivel por encima y adyacente a él. Puede pensarse como el nodo del que se origina dicho nodo. A es el nodo padre de B y C.

Nodos secundarios/ secundarios: nodos que se ramifican y son adyacentes a un nodo principal. B y C son nodos secundarios de A

Leer: Las 10 mejores técnicas de visualización de datos

BFS es un algoritmo de recorrido de gráficos para explorar un árbol o un gráfico de manera eficiente. El algoritmo comienza con un nodo inicial (nodo raíz) y luego procede a explorar todos los nodos adyacentes a él, primero en amplitud, a diferencia de primero en profundidad, que desciende por una rama en particular hasta todos los nodos en esa rama. son visitados. En pocas palabras, atraviesa el gráfico por niveles, sin bajar un nivel hasta que todos los nodos de ese nivel hayan sido visitados y marcados.

Opera según el principio de primero en entrar, primero en salir (FIFO) y se implementa utilizando una estructura de datos de cola. Una vez que se visita un nodo, se inserta en una cola. Luego se graba y todos sus nodos secundarios se insertan en la cola. Este proceso continúa hasta que se visitan y registran todos los nodos del gráfico.

Veamos las operaciones de cola detalladas para el algoritmo BFS para el gráfico anterior:

() – denota cola

[]: indica salida impresa

1. Inserte A en la cola (a)
2. Imprime A, inserta B y C en la cola (cb)[a]
3. Imprima B, inserte sus nodos secundarios D y E en la cola (edc)[ba]
4. Imprima C, inserte su nodo secundario F en la cola (alimentado) [cba]
5. Imprima D, inserte su nodo secundario en la cola. No hay ninguno. (fe)[dcba]
6. Imprima E, cuyo nodo secundario F ya se ha insertado en la cola. (f)[edcba]
7. Imprimir F. [fedcba]

Qué hace que el algoritmo BFS sea importante

Existen innumerables razones para implementar BFS como un método para buscar rápidamente en grandes conjuntos de datos. Algunas de las características más destacadas que lo convierten en la opción preferida de los desarrolladores e ingenieros de datos son:

• BFS puede explorar efectivamente todos los nodos en el gráfico y encontrar la ruta más corta posible para explorarlos todos.
• El número de iteraciones requeridas para recorrer todo el gráfico es menor que otros algoritmos de búsqueda.
• Dado que se implementa mediante una cola, su arquitectura es robusta, confiable y elegante.
• En comparación con otros algoritmos, la salida de BFS es exacta y sin errores.
• Las iteraciones de BFS se realizan sin problemas, sin correr el riesgo de quedar atrapado en un bucle infinito.

Pago: Proyectos de visualización de datos que puede replicar

Aplicaciones del algoritmo BFS

Debido a su simplicidad y facilidad de configuración, el algoritmo BFS ha encontrado un uso generalizado en varias situaciones clave del mundo real. Veamos algunas aplicaciones destacadas:

Rastreadores de motores de búsqueda : intente imaginar un mundo sin Google o Bing. no puedes Los motores de búsqueda son la columna vertebral de Internet. Y el algoritmo BFS es la columna vertebral de los motores de búsqueda. Es el algoritmo principal utilizado para indexar páginas web. El algoritmo comienza su viaje desde la página de origen (nodo raíz) y luego sigue todos los enlaces en esa página de origen de manera amplia. Cada página web se puede considerar como un nodo independiente en el gráfico.

Recorridos de gráficos no ponderados : BFS puede identificar la ruta más corta y el árbol de expansión mínimo en un gráfico no ponderado. Encontrar la ruta más corta se trata simplemente de encontrar un camino con el menor número de aristas, para lo cual BFS es ideal. Puede hacer el trabajo visitando la menor cantidad de nodos.

Navegación GPS : BFS aprovecha los sistemas GPS para mostrar todas las ubicaciones vecinas posibles desde su punto de partida, ayudándole a navegar desde el punto A al B sin problemas.

Difusión : las redes de difusión utilizan paquetes como unidades para transportar señales y datos. El algoritmo BFS dirige estos paquetes para llegar a todos los nodos de la red a los que se supone que deben llegar.

Redes P2P : Torrents u otras redes de intercambio de archivos dependen de la comunicación P2P. BFS funciona excelente para encontrar los nodos más cercanos para que la transferencia de datos pueda ocurrir más rápido.

Lea también: Beneficios de la visualización de datos

Conclusión

Ergo, el algoritmo de búsqueda Breadth First es uno de los algoritmos más importantes de la Internet moderna. Con suerte, este blog servirá como un punto de partida útil en sus exploraciones de algoritmos de búsqueda.

Le recomendamos que elija el Diploma PG en ciencia de datos ofrecido por IIIT Bangalore alojado en upGrad porque aquí puede obtener sus consultas 1-1 con los instructores del curso. No solo se enfoca en el aprendizaje teórico, sino que le da importancia al conocimiento práctico, que es esencial para preparar a los alumnos para enfrentar proyectos del mundo real y brindarle el primer certificado NASSCOM de la India, que lo ayuda a obtener trabajos bien remunerados en Ciencia de datos.