Aplicaciones de Breadth First Traversal

Anteriormente hemos discutido el algoritmo transversal Breadth First para gráficos. También hemos discutido Aplicaciones de Profundidad Primero Traversal . En este artículo, se analizan las aplicaciones de Breadth First Search. 

1. Ruta más corta y árbol de expansión mínimo para gráfico no ponderado En un gráfico no ponderado, la ruta más corta es la ruta con el menor número de aristas. Con Breadth First, siempre alcanzamos un vértice desde una fuente determinada utilizando el número mínimo de aristas. Además, en el caso de gráficos no ponderados, cualquier árbol de expansión es un árbol de expansión mínimo y podemos usar el primer recorrido de profundidad o amplitud para encontrar un árbol de expansión. 
2. Redes punto a punto. En redes punto a punto como BitTorrent , Breadth First Search se utiliza para encontrar todos los Nodes vecinos. 
3. Rastreadores en motores de búsqueda: los rastreadores crean índices utilizando Breadth First. La idea es comenzar desde la página fuente y seguir todos los enlaces desde la fuente y seguir haciendo lo mismo. Depth First Traversal también se puede usar para rastreadores, pero la ventaja con Breadth First Traversal es que la profundidad o los niveles del árbol construido pueden ser limitados. 
4. Sitios Web de Redes Sociales: En las redes sociales, podemos encontrar personas dentro de una distancia dada ‘k’ de una persona utilizando Breadth First Search hasta niveles ‘k’. 
5. Sistemas de navegación GPS: Breadth First Search se utiliza para encontrar todas las ubicaciones vecinas. 
6. Difusión en la red: en las redes, un paquete difundido sigue la búsqueda primero en amplitud para llegar a todos los Nodes. 
7. En Garbage Collection: Breadth First Search se usa para copiar la recolección de basura utilizando el algoritmo de Cheney . Consulte esto y para más detalles. Se prefiere la búsqueda primero en amplitud a la búsqueda primero en profundidad debido a una mejor localidad de referencia: 
8. Detección de ciclos en gráficos no dirigidos: en gráficos no dirigidos, se puede usar la búsqueda primero en amplitud o la búsqueda primero en profundidad para detectar el ciclo. También podemos usar BFS para detectar el ciclo en un gráfico dirigido ,
9.  Algoritmo de Ford-Fulkerson En el algoritmo de Ford-Fulkerson, podemos usar primero la amplitud o primero la profundidad transversal para encontrar el flujo máximo. Se prefiere Breadth First Traversal ya que reduce la complejidad del tiempo en el peor de los casos a O(VE ² ). 
10. Para probar si un gráfico es bipartito , podemos usar primero la amplitud o primero la profundidad transversal. 
11. Búsqueda de caminos Podemos usar primero la amplitud o primero la profundidad transversal para encontrar si hay un camino entre dos vértices. 
12. Encontrar todos los Nodes dentro de un componente conectado: podemos usar Breadth First o Depth First Traversal para encontrar todos los Nodes accesibles desde un Node dado. 

Muchos algoritmos, como el árbol de expansión mínimo de Prim y la ruta más corta de origen único de Dijkstra, utilizan una estructura similar a Breadth First Search. 
Puede haber muchas más aplicaciones, ya que Breadth First Search es uno de los algoritmos centrales de Graphs.