11 - Búsqueda en profundidad (DFS)

DFS (depth-first search - búsqueda en profundidad) explora un camino hasta el fondo antes de retroceder. Resulta clave para detectar ciclos, obtener orden topológico y clasificar aristas.

11.1 Concepto general

Se parte de un vértice origen, se marca como visitado y se recorre recursiva o iterativamente cada vecino no visitado antes de regresar. El proceso se repite para cubrir todos los componentes.

11.2 DFS recursivo

def dfs_rec(g, u, visitado):
  visitado[u] = True
  print(u, end=" ")
  for v, _ in g[u]:
    if not visitado[v]:
      dfs_rec(g, v, visitado)

def dfs(g, origen):
  visitado = {v: False for v in g}
  dfs_rec(g, origen, visitado)

11.3 DFS iterativo con pila

def dfs_iterativo(g, origen):
  visitado = {v: False for v in g}
  pila = [origen]
  while pila:
    u = pila.pop()
    if visitado[u]:
      continue
    visitado[u] = True
    print(u, end=" ")
    for v, _ in g[u]:
      if not visitado[v]:
        pila.append(v)

11.4 Comparación entre ambas versiones

• Recursivo: código compacto, usa la pila del sistema; puede desbordarse en grafos muy profundos.
• Iterativo: controla la pila manualmente y evita desbordes, útil para grafos grandes o restricciones de stack.

11.5 Aplicaciones de DFS en grafos

• Orden topológico en digrafos acíclicos.
• Detección de ciclos y puntos de articulación.
• Clasificación de componentes fuertemente conexas (Kosaraju/Tarjan).
• Coloreo y verificación de bipartición en no dirigidos.

11.6 Árbol DFS y clasificación de aristas

Durante DFS se puede registrar el padre y el tiempo de descubrimiento de cada vértice para clasificar aristas en:

• Aristas de árbol: las que se recorren la primera vez que se llega a un vértice nuevo.
• Aristas de retroceso: conectan un nodo con un ancestro y revelan ciclos.
• Aristas de avance: van de un nodo a un descendiente ya descubierto (en digrafos).
• Aristas cruzadas: conectan nodos sin relación ancestro/descendiente en ese orden de visita.

11.7 Aplicación completa para probar en VSCode

Programa autocontenido que construye un grafo pequeño y ejecuta DFS recursivo e iterativo.

def dfs_rec(g, u, visitado):
  visitado[u] = True
  print(u, end=" ")
  for v, _ in g[u]:
    if not visitado[v]:
      dfs_rec(g, v, visitado)

def dfs(g, origen):
  visitado = {v: False for v in g}
  dfs_rec(g, origen, visitado)

def dfs_iterativo(g, origen):
  visitado = {v: False for v in g}
  pila = [origen]
  while pila:
    u = pila.pop()
    if visitado[u]:
      continue
    visitado[u] = True
    print(u, end=" ")
    for v, _ in g[u]:
      if not visitado[v]:
        pila.append(v)

def main():
  g = {
    0: [(1, 1), (2, 1)],
    1: [(0, 1), (3, 1)],
    2: [(0, 1), (4, 1)],
    3: [(1, 1), (4, 1)],
    4: [(2, 1), (3, 1)]
  }

  print("DFS recursivo desde 0: ", end="")
  dfs(g, 0)
  print()

  print("DFS iterativo desde 0: ", end="")
  dfs_iterativo(g, 0)
  print()

if __name__ == "__main__":
  main()

Ejecuta para comparar el orden de visita entre DFS recursivo e iterativo. Modifica las aristas para ver cómo cambian los recorridos. Con el grafo definido y empujando vecinos en el orden en que aparecen, una salida posible es:

DFS recursivo desde 0: 0 2 4 1 3
DFS iterativo desde 0: 0 1 3 4 2

El orden de la versión iterativa cambia según la pila y el orden en que se apilan los vecinos; si se invierte la inserción en la pila puede igualarse al orden recursivo.

Abrir visualizador DFS interactivo