Saltar al contenido

Algoritmo DFS – javatpoint

octubre 18, 2021
depth first search algorithm

El algoritmo de primera búsqueda en profundidad (DFS) comienza con el nodo inicial del gráfico G, y luego va más y más hasta que encontramos el nodo objetivo o el nodo que no tiene hijos. Luego, el algoritmo retrocede desde el callejón sin salida hacia el nodo más reciente que aún no se ha explorado por completo.

La estructura de datos que se utiliza en DFS es pila. El proceso es similar al algoritmo BFS. En DFS, los bordes que conducen a un nodo no visitado se denominan bordes de descubrimiento, mientras que los bordes que conducen a un nodo ya visitado se denominan bordes de bloque.

Algoritmo

  • Paso 1: SET STATUS = 1 (estado listo) para cada nodo en G
  • Paso 2: Empuje el nodo inicial A en la pila y establezca su ESTADO = 2 (estado de espera)
  • Paso 3: Repita los pasos 4 y 5 hasta que la PILA esté vacía
  • Paso 4: Haga estallar el nodo superior N. Procese y establezca su ESTADO = 3 (estado procesado)
  • Paso 5: Empuje en la pila todos los vecinos de N que están en el estado listo (cuyo ESTADO = 1) y establezca su
    ESTADO = 2 (estado de espera)
    [END OF LOOP]
  • Paso 6: SALIDA

Ejemplo :

Considere el gráfico G junto con su lista de adyacencia, que se muestra en la siguiente figura. Calcule el orden para imprimir todos los nodos del gráfico a partir del nodo H, utilizando el algoritmo de búsqueda en profundidad (DFS).

Algoritmo de búsqueda de profundidad primero

Solucion:

Empuje H sobre la pila

POP el elemento superior de la pila, es decir, H, imprímalo y empuje a todos los vecinos de H a la pila que están en estado listo.

Haga estallar el elemento superior de la pila, es decir, A, imprímalo y empuje a todos los vecinos de A a la pila que están en estado listo.

Haga estallar el elemento superior de la pila, es decir, D, imprímalo y empuje a todos los vecinos de D a la pila que están en estado listo.

Haga estallar el elemento superior de la pila, es decir, F, imprímalo y empuje todos los vecinos de F a la pila que están en estado listo.

Haga estallar la parte superior de la pila, es decir, B y empuje a todos los vecinos

Haga estallar la parte superior de la pila, es decir, C y empuje a todos los vecinos.

Haga estallar la parte superior de la pila, es decir, G y empuje a todos sus vecinos.

Haga estallar la parte superior de la pila, es decir, E y empuje a todos sus vecinos.

Por lo tanto, la pila ahora se vacía y todos los nodos del gráfico se han atravesado.

La secuencia de impresión del gráfico será:

close