¿Qué es BFS?

La búsqueda en amplitud (BFS) se basa en atravesar nodos agregando los vecinos de cada nodo a la cola transversal comenzando desde el nodo raíz. El BFS de un gráfico es similar al de un árbol, con la excepción de que los gráficos pueden tener ciclos. A diferencia de la búsqueda en profundidad, todos los nodos vecinos a una profundidad determinada se investigan antes de pasar al siguiente nivel.

Algoritmo BFS

Los siguientes son los pasos necesarios para emplear la búsqueda en amplitud para explorar un gráfico:

1. Tome los datos para la matriz de adyacencia o la lista de adyacencia del gráfico.
2. Crea una cola y llénala con elementos.
3. Active el nodo raíz (lo que significa que obtenga el nodo raíz al comienzo de la cola).
4. Retire el encabezado de la cola (o elemento inicial) y luego ponga en cola todos los nodos cercanos de la cola de izquierda a derecha. Simplemente retire el cabezal de la cola y reanude la operación si un nodo no tiene nodos cercanos que deban investigarse. (Nota: si surge un vecino que ha sido investigado previamente o está en la cola, no lo ponga en cola; en su lugar, omítalo).
5. Continúe de esta manera hasta que la cola esté vacía.

Aplicaciones BFS

Debido a la flexibilidad del algoritmo, la búsqueda primero en amplitud es bastante útil en el mundo real. Estos son algunos de ellos:

1. En una red peer-to-peer, se descubren nodos peer. La mayoría de los clientes de torrents, como BitTorrent, uTorrent y qBittorent, emplean este proceso para encontrar 'semillas' y 'pares' en la red.
2. El índice se construye utilizando técnicas de recorrido de gráficos en el rastreo web. El procedimiento comienza con la página de origen como nodo raíz y continúa hasta todas las páginas secundarias que están vinculadas a la página de origen (y este proceso continúa). Debido a la profundidad reducida del árbol de recursividad, la búsqueda primero en amplitud tiene una ventaja inherente aquí.
3. El uso de sistemas de navegación GPS que utilizan el GPS, realizan una búsqueda en amplitud para localizar sitios cercanos.
4. La técnica de Cheney, que emplea el concepto de búsqueda en amplitud, se utiliza para recolectar basura.

Ejemplo de recorrido BFS

Para empezar, veamos un ejemplo sencillo. Comenzaremos con 0 como nodo raíz y avanzaremos hacia abajo en el gráfico.

Paso 1: Poner en cola(0)

Cola

Paso 2: Quitar de cola (0), Poner en cola (1), Poner en cola (3), Poner en cola (4)

Cola

Paso 3: Quitar de cola(1), Poner en cola(2)

Cola

Etapa 4: Quitar de cola(3), Poner en cola(5). No volveremos a agregar 1 a la cola porque 0 ya ha sido explorado.

Cola

Paso 5: Quitar de la cola(4)

Cola

Paso 6: Quitar de cola(2)

Cola

Paso 7: Quitar de la cola(5)

Cola

La cola está vacía ahora, así que detendremos el proceso.

Programa Java de búsqueda en amplitud

Hay varios enfoques para tratar el código. Principalmente discutiremos los pasos involucrados en la implementación de una búsqueda amplia en Java. Se puede utilizar una lista de adyacencia o una matriz de adyacencia para almacenar gráficos; cualquier método es aceptable. La lista de adyacencia se utilizará para representar nuestro gráfico en nuestro código. Al implementar el algoritmo Breadth-First Search en Java, es mucho más fácil lidiar con la lista de adyacencia ya que solo tenemos que viajar a través de la lista de nodos adjuntos a cada nodo una vez que el nodo se retira de la cola del encabezado (o inicio) del cola.

El gráfico utilizado para demostrar el código será idéntico al utilizado en el ejemplo anterior.

BFSTraversal.java

 import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[node]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>