Saltar al contenido principal

Depth-First Search (DFS)

DFS es un algoritmo para recorrer o buscar en grafos o árboles que explora los nodos profundamente, siguiendo cada camino hasta llegar a un nodo sin vecinos no visitados, antes de retroceder.

  • Se llama Depth-First porque prioriza la profundidad sobre la amplitud.
  • Utiliza una pila (implícita con recursión o explícita) para recordar los nodos pendientes de explorar.
  • Es útil para explorar componentes conectadas, detectar ciclos, o realizar recorridos topológicos.

Algoritmo​

  1. Comenzar desde un nodo inicial y marcarlo como visitado.
  2. Explorar uno de sus vecinos no visitados y marcarlo como visitado.
  3. Repetir este proceso profundizando por cada vecino hasta que no haya más nodos por visitar en ese camino.
  4. Retroceder al nodo anterior y continuar con los vecinos restantes.
  5. Continuar hasta que todos los nodos alcanzables desde el nodo inicial estén visitados.

Paso a paso con un ejemplo​

Grafo (no dirigido), representado visualmente:

Lista de adyacencia conceptual:

A: B, C
B: D
C: E
D: -
E: F
F: -

Queremos recorrer el grafo comenzando en A.

Paso 1: Empezar en A

  • Marcamos A como visitado.
  • Elegimos un vecino no visitado, por ejemplo B.
  • Orden de visita parcial: [A]

Paso 2: Explorar B

  • Marcamos B como visitado.
  • Vecino no visitado de B: D.
  • Orden de visita parcial: [A, B]

Paso 3: Explorar D

  • Marcamos D como visitado.
  • D no tiene vecinos no visitados → retrocedemos a B.
  • Orden de visita parcial: [A, B, D]

Paso 4: Retroceder a A y explorar C

  • Marcamos C como visitado.
  • Vecino no visitado de C: E.
  • Orden de visita parcial: [A, B, D, C]

Paso 5: Explorar E

  • Marcamos E como visitado.
  • Vecino no visitado de E: F.
  • Orden de visita parcial: [A, B, D, C, E]

Paso 6: Explorar F

  • Marcamos F como visitado.
  • F no tiene vecinos no visitados → retrocedemos a E, luego a C, luego a A.
  • Orden final de visita: [A, B, D, C, E, F]

Cómo funciona internamente​

  • DFS profundiza por un camino hasta el final antes de retroceder.
  • La estructura de la pila (explícita o implícita) recuerda los nodos pendientes mientras se exploran los caminos.
  • El orden de visita puede variar según el vecino elegido primero, pero siempre se exploran completamente los caminos antes de pasar a otros.

Características clave​

  • Puede implementarse recursivamente o usando una pila explícita.
  • Tiempo de ejecución: proporcional a número de nodos + número de aristas.
  • Útil para:
    • Explorar componentes conectadas
    • Detectar ciclos
    • Recorridos topológicos en grafos dirigidos acíclicos