Saltar al contenido

Algoritmo BFS – javatpoint

octubre 16, 2021
breadth first search algorithm

En esta parte del tutorial discutiremos las técnicas mediante las cuales podemos atravesar todos los vértices del gráfico.

Atravesar el gráfico significa examinar todos los nodos y vértices del gráfico. Hay dos métodos estándar mediante los cuales podemos recorrer los gráficos. Analicemos cada uno de ellos en detalle.

  • Primera búsqueda de amplitud
  • Primera búsqueda en profundidad

Algoritmo de búsqueda primero en amplitud (BFS)

La primera búsqueda de 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. El algoritmo sigue el mismo proceso para cada uno de los nodos más cercanos hasta que encuentra el objetivo.

El algoritmo de la primera búsqueda en amplitud se muestra a continuación. El algoritmo comienza examinando el nodo A y todos sus vecinos. En el siguiente paso, se exploran los vecinos del nodo más cercano de A y el proceso continúa en los pasos posteriores. El algoritmo explora todos los vecinos de todos los nodos y garantiza que cada nodo se visite exactamente una vez y que ningún nodo se visite dos veces.

Algoritmo

  • Paso 1: SET STATUS = 1 (estado listo)
    para cada nodo en G
  • Paso 2: Poner en cola el nodo inicial A
    y establezca su ESTADO = 2
    (estado de espera)
  • Paso 3: Repita los pasos 4 y 5 hasta
    COLA está vacía
  • Paso 4: Retirar de la cola un nodo N. Procesarlo
    y establezca su ESTADO = 3
    (estado procesado).
  • Paso 5: Poner en cola a todos los vecinos de
    N que están en estado listo
    (cuyo ESTADO = 1) y establecer
    su ESTADO = 2
    (estado de espera)
    [END OF LOOP]
  • Paso 6: SALIDA

Ejemplo

Considere el gráfico G que se muestra en la siguiente imagen, calcule la ruta mínima p desde el nodo A al nodo E. Dado que cada borde tiene una longitud de 1.

Algoritmo de búsqueda primero en amplitud

Solución:

La ruta mínima P se puede encontrar aplicando el algoritmo de búsqueda de amplitud primero que comenzará en el nodo A y terminará en E. El algoritmo usa dos colas, a saber COLA1 y COLA2. COLA1 contiene todos los nodos que se van a procesar mientras COLA2 contiene todos los nodos que se procesan y eliminan de COLA1.

Comencemos a examinar el gráfico del Nodo A.

1. Agregue A a QUEUE1 y NULL a QUEUE2.

2. Elimine el Nodo A de QUEUE1 e inserte todos sus vecinos. Inserte el nodo A en QUEUE2

3. Elimine el nodo B de QUEUE1 e inserte todos sus vecinos. Inserte el nodo B en QUEUE2.

4. Elimine el nodo D de QUEUE1 e inserte todos sus vecinos. Dado que F es el único vecino que se ha insertado, no lo volveremos a insertar. Inserte el nodo D en QUEUE2.

5. Elimine el nodo C de QUEUE1 e inserte todos sus vecinos. Agregue el nodo C a QUEUE2.

6. Elimine F de QUEUE1 y agregue todos sus vecinos. Dado que ya se han agregado todos sus vecinos, no los volveremos a agregar. Agregue el nodo F a QUEUE2.

7. Elimine E de QUEUE1, todos los vecinos de E ya se han agregado a QUEUE1, por lo que no los volveremos a agregar. Se visitan todos los nodos y el nodo de destino, es decir, E se encuentra en QUEUE2.

Ahora, retroceda de E a A, utilizando los nodos disponibles en QUEUE2.

El camino mínimo será A → B → C → E.

close