En este artículo, discutiremos el algoritmo BFS en la estructura de datos. La búsqueda en amplitud es un algoritmo de recorrido de gráfico que comienza a recorrer el gráfico desde el nodo raíz y explora todos los nodos vecinos. Luego, selecciona el nodo más cercano y explora todos los nodos inexplorados. Al utilizar BFS para el recorrido, cualquier nodo del gráfico puede considerarse como el nodo raíz.

Hay muchas formas de recorrer el gráfico, pero entre ellas, BFS es el método más utilizado. Es un algoritmo recursivo para buscar todos los vértices de una estructura de datos de árbol o gráfico. BFS coloca cada vértice del gráfico en dos categorías: visitados y no visitados. Selecciona un solo nodo en un gráfico y, luego, visita todos los nodos adyacentes al nodo seleccionado.

Aplicaciones del algoritmo BFS

Las aplicaciones del algoritmo de amplitud primero se dan de la siguiente manera:

• BFS se puede utilizar para encontrar ubicaciones vecinas desde una ubicación de origen determinada.
• En una red peer-to-peer, el algoritmo BFS se puede utilizar como método transversal para encontrar todos los nodos vecinos. La mayoría de los clientes de torrents, como BitTorrent, uTorrent, etc., emplean este proceso para encontrar 'semillas' y 'pares' en la red.
• BFS se puede utilizar en rastreadores web para crear índices de páginas web. Es uno de los principales algoritmos que se pueden utilizar para indexar páginas web. Comienza a recorrer desde la página de origen y sigue los enlaces asociados con la página. Aquí, cada página web se considera como un nodo en el gráfico.
• BFS se utiliza para determinar la ruta más corta y el árbol de expansión mínimo.
• BFS también se utiliza en la técnica de Cheney para duplicar la recolección de basura.
• Se puede utilizar en el método Ford-Fulkerson para calcular el flujo máximo en una red de flujo.

Algoritmo

Los pasos involucrados en el algoritmo BFS para explorar un gráfico se detallan a continuación:

Paso 1: SET STATUS = 1 (estado listo) para cada nodo en G

Paso 2: Ponga en cola el nodo inicial A y establezca su ESTADO = 2 (estado de espera)

Paso 3: Repita los pasos 4 y 5 hasta que la COLA esté vacía

si no, golpe

Etapa 4: Retire de la cola un nodo N. Procéselo y establezca su ESTADO = 3 (estado procesado).

Paso 5: Ponga en cola todos los vecinos de N que están en estado listo (cuyo ESTADO = 1) y establezca

su ESTADO = 2

(estado de espera)

igualdad de objetos java

[FIN DEL BUCLE]

Paso 6: SALIDA

Ejemplo de algoritmo BFS

Ahora, comprendamos el funcionamiento del algoritmo BFS usando un ejemplo. En el ejemplo que se muestra a continuación, hay un gráfico dirigido que tiene 7 vértices.

En el gráfico anterior, la ruta mínima 'P' se puede encontrar utilizando el BFS que comenzará en el Nodo A y terminará en el Nodo E. El algoritmo utiliza dos colas, a saber, QUEUE1 y QUEUE2. QUEUE1 contiene todos los nodos que se van a procesar, mientras que QUEUE2 contiene todos los nodos que se procesan y eliminan de QUEUE1.

conversión de int a cadena

Ahora, comencemos a examinar el gráfico a partir del Nodo A.

Paso 1 - Primero, agregue A a la cola1 y NULL a la cola2.

 QUEUE1 = {A} QUEUE2 = {NULL} 

Paso 2 - Ahora, elimine el nodo A de la cola1 y agréguelo a la cola2. Inserte todos los vecinos del nodo A en la cola1.

 QUEUE1 = {B, D} QUEUE2 = {A} 

Paso 3 - Ahora, elimine el nodo B de la cola1 y agréguelo a la cola2. Inserte todos los vecinos del nodo B en la cola1.

 QUEUE1 = {D, C, F} QUEUE2 = {A, B} 

Etapa 4 - Ahora, elimine el nodo D de la cola1 y agréguelo a la cola2. Inserte todos los vecinos del nodo D en la cola1. El único vecino del Nodo D es F ya que ya está insertado, por lo que no se volverá a insertar.

 QUEUE1 = {C, F} QUEUE2 = {A, B, D} 

Paso 5 - Elimine el nodo C de la cola1 y agréguelo a la cola2. Inserte todos los vecinos del nodo C en la cola1.

 QUEUE1 = {F, E, G} QUEUE2 = {A, B, D, C} 

Paso 5 - Elimine el nodo F de la cola1 y agréguelo a la cola2. Inserte todos los vecinos del nodo F en la cola1. Como todos los vecinos del nodo F ya están presentes, no los insertaremos nuevamente.

 QUEUE1 = {E, G} QUEUE2 = {A, B, D, C, F} 

Paso 6 - Eliminar el nodo E de la cola1. Dado que todos sus vecinos ya han sido agregados, no los insertaremos nuevamente. Ahora, se visitan todos los nodos y el nodo objetivo E se encuentra en la cola2.

 QUEUE1 = {G} QUEUE2 = {A, B, D, C, F, E} 

Complejidad del algoritmo BFS

La complejidad temporal de BFS depende de la estructura de datos utilizada para representar el gráfico. La complejidad temporal del algoritmo BFS es O(V+E) , ya que en el peor de los casos, el algoritmo BFS explora cada nodo y borde. En un gráfico, el número de vértices es O(V), mientras que el número de aristas es O(E).

La complejidad espacial de BFS se puede expresar como O(V) , donde V es el número de vértices.

Implementación del algoritmo BFS.

Ahora, veamos la implementación del algoritmo BFS en Java.

cómo abrir un archivo con java

En este código, estamos usando la lista de adyacencia para representar nuestro gráfico. La implementación del algoritmo Breadth-First Search en Java hace que sea mucho más fácil lidiar con la lista de adyacencia, ya que solo tenemos que recorrer la lista de nodos adjuntos a cada nodo una vez que el nodo se retira del encabezado (o inicio) de la cola.

En este ejemplo, el gráfico que estamos usando para demostrar el código se muestra a continuación:

 import java.io.*; import java.util.*; public class BFSTraversal { private int vertex; /* total number number of vertices in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { vertex = v; adj = new LinkedList[vertex]; 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[vertex]; 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(10); graph.insertedge(0, 1); 2); 3); graph.insertedge(1, graph.insertedge(2, 4); graph.insertedge(3, 5); 6); graph.insertedge(4, 7); graph.insertedge(5, graph.insertedge(6, graph.insertedge(7, 8); system.out.println('breadth first traversal is:'); graph.bfs(2); pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/64/bfs-algorithm-3.webp" alt="Breadth First Search Algorithm"> <h3>Conclusion</h3> <p>In this article, we have discussed the Breadth-first search technique along with its example, complexity, and implementation in java programming language. Here, we have also seen the real-life applications of BFS that show it the important data structure algorithm.</p> <p>So, that&apos;s all about the article. Hope, it will be helpful and informative to you.</p> <hr></v;>