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

/* DFS recursivo sobre lista de adyacencia */
typedef struct Arista {
  int destino;
  struct Arista *sig;
} Arista;

typedef struct {
  int n;
  Arista **listas;
} Grafo;

void dfsRec(const Grafo *g, int u, int *visitado) {
  visitado[u] = 1;
  printf("%d ", u);
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (!visitado[v]) {
      dfsRec(g, v, visitado);
    }
  }
}

void dfs(const Grafo *g, int origen) {
  int *visitado = calloc(g->n, sizeof(int));
  dfsRec(g, origen, visitado);
  free(visitado);
}

11.3 DFS iterativo con pila

/* DFS iterativo usando pila */
typedef struct {
  int *datos;
  int tope;
} Pila;

Pila *crearPila(int n) {
  Pila *p = malloc(sizeof(Pila));
  p->datos = malloc(n * sizeof(int));
  p->tope = 0;
  return p;
}

int pilaVacia(const Pila *p) { return p->tope == 0; }
void apilar(Pila *p, int v) { p->datos[p->tope++] = v; }
int desapilar(Pila *p) { return p->datos[--p->tope]; }

void dfsIterativo(const Grafo *g, int origen) {
  int *visitado = calloc(g->n, sizeof(int));
  Pila *p = crearPila(g->n);
  apilar(p, origen);
  while (!pilaVacia(p)) {
    int u = desapilar(p);
    if (visitado[u]) continue;
    visitado[u] = 1;
    printf("%d ", u);
    for (Arista *it = g->listas[u]; it; it = it->sig) {
      int v = it->destino;
      if (!visitado[v]) apilar(p, v);
    }
  }
  free(visitado);
  free(p->datos);
  free(p);
}

11.4 Comparación entre ambas versiones

  • Recursivo: código compacto, apoya 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 CLion

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

#include <stdio.h>
#include <stdlib.h>

typedef struct Arista {
  int destino;
  struct Arista *sig;
} Arista;

typedef struct {
  int n;
  Arista **listas;
} Grafo;

typedef struct {
  int *datos;
  int tope;
} Pila;

Grafo *crearGrafo(int n) {
  Grafo *g = malloc(sizeof(Grafo));
  g->n = n;
  g->listas = calloc(n, sizeof(Arista *));
  return g;
}

void agregarArista(Grafo *g, int u, int v) {
  Arista *n = malloc(sizeof(Arista));
  n->destino = v;
  n->sig = g->listas[u];
  g->listas[u] = n;
}

Pila *crearPila(int n) {
  Pila *p = malloc(sizeof(Pila));
  p->datos = malloc(n * sizeof(int));
  p->tope = 0;
  return p;
}

int pilaVacia(const Pila *p) { return p->tope == 0; }
void apilar(Pila *p, int v) { p->datos[p->tope++] = v; }
int desapilar(Pila *p) { return p->datos[--p->tope]; }

void dfsRec(const Grafo *g, int u, int *visitado) {
  visitado[u] = 1;
  printf("%d ", u);
  for (Arista *it = g->listas[u]; it; it = it->sig) {
    int v = it->destino;
    if (!visitado[v]) dfsRec(g, v, visitado);
  }
}

void dfs(const Grafo *g, int origen) {
  int *visitado = calloc(g->n, sizeof(int));
  dfsRec(g, origen, visitado);
  free(visitado);
}

void dfsIterativo(const Grafo *g, int origen) {
  int *visitado = calloc(g->n, sizeof(int));
  Pila *p = crearPila(g->n);
  apilar(p, origen);
  while (!pilaVacia(p)) {
    int u = desapilar(p);
    if (visitado[u]) continue;
    visitado[u] = 1;
    printf("%d ", u);
    for (Arista *it = g->listas[u]; it; it = it->sig) {
      int v = it->destino;
      if (!visitado[v]) apilar(p, v);
    }
  }
  free(visitado);
  free(p->datos);
  free(p);
}

int main(void) {
  Grafo *g = crearGrafo(5);
  agregarArista(g, 0, 1);
  agregarArista(g, 0, 2);
  agregarArista(g, 1, 3);
  agregarArista(g, 2, 4);
  agregarArista(g, 3, 4);

  printf("DFS recursivo desde 0: ");
  dfs(g, 0);
  printf("\n");

  printf("DFS iterativo desde 0: ");
  dfsIterativo(g, 0);
  printf("\n");

  /* liberar */
  for (int u = 0; u < g->n; u++) {
    Arista *it = g->listas[u];
    while (it) {
      Arista *tmp = it;
      it = it->sig;
      free(tmp);
    }
  }
  free(g->listas);
  free(g);
  return 0;
}

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

Retornar