Búsqueda en Profundidad (DFS)

La analogía: explorar un laberinto

Imagina que entras a un laberinto sin mapa. Tu estrategia: en cada bifurcación, siempre tomas el primer camino y sigues avanzando. Cuando llegas a un callejón sin salida, retrocedes a la última bifurcación y pruebas el siguiente camino. Eso es DFS (Depth-First Search): ir lo más profundo posible antes de regresar.

Otra forma de verlo: leer un libro donde cada capítulo tiene sub-capítulos. Lees el capítulo 1, luego su sub-capítulo 1.1, luego 1.1.1, hasta que no hay más sub-capítulos. Entonces regresas al 1.1, pasas a 1.2, y así sucesivamente.

BFS vs DFS

Implementación recursiva

La forma más natural de escribir DFS es con recursión:

#include <iostream>
#include <vector>
using namespace std;

vector<int> adj[100005]; // Lista de adyacencia
bool visitado[100005];

void dfs(int nodo) {
    visitado[nodo] = true;
    cout << nodo << " ";  // Procesar el nodo

    for (int vecino : adj[nodo]) {
        if (!visitado[vecino]) {
            dfs(vecino);  // Llamada recursiva
        }
    }
}

Línea por línea:

1. visitado[nodo] = true — Marcamos el nodo para no visitarlo otra vez.
2. for (int vecino : adj[nodo]) — Recorremos todos los vecinos.
3. if (!visitado[vecino]) — Si no hemos visitado al vecino…
4. dfs(vecino) — Nos sumergimos más profundo.

Implementación iterativa (con pila)

Si el grafo es muy profundo, la recursión podría causar stack overflow. Solución: usa una pila explícita.

void dfsIterativo(int inicio) {
    stack<int> pila;
    pila.push(inicio);

    while (!pila.empty()) {
        int nodo = pila.top();
        pila.pop();

        if (visitado[nodo]) continue;
        visitado[nodo] = true;
        cout << nodo << " ";

        for (int vecino : adj[nodo]) {
            if (!visitado[vecino]) {
                pila.push(vecino);
            }
        }
    }
}

Ejemplo visual

Grafo:

    1
   / \
  2   3
 / \   \
4   5   6

DFS desde 1: 1 → 2 → 4 → 5 → 3 → 6

Nota cómo va lo más profundo posible (1→2→4), retrocede (a 2), explora otra rama (5), retrocede (a 1), y sigue (3→6).

Aplicaciones clásicas

1. Contar componentes conexas

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int componentes = 0;
    for (int i = 1; i <= n; i++) {
        if (!visitado[i]) {
            dfs(i);
            componentes++;
        }
    }

    cout << "Componentes conexas: " << componentes << endl;
}

Cada vez que encontramos un nodo no visitado, iniciamos un DFS que visita toda su componente conexa.

2. Detectar ciclos en grafo no dirigido

bool tieneCiclo = false;

void dfsCiclo(int nodo, int padre) {
    visitado[nodo] = true;

    for (int vecino : adj[nodo]) {
        if (!visitado[vecino]) {
            dfsCiclo(vecino, nodo);
        } else if (vecino != padre) {
            tieneCiclo = true;  // ¡Encontramos un ciclo!
        }
    }
}

Si encontramos un vecino ya visitado que no es el padre del nodo actual, hay un ciclo.

3. DFS en cuadrícula (flood fill)

El clásico "rellenar una región" como en Paint:

int n, m;
char grid[1005][1005];
bool vis[1005][1005];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int tamano;  // Tamaño de la componente

void dfsGrid(int x, int y, char color) {
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (vis[x][y] || grid[x][y] != color) return;

    vis[x][y] = true;
    tamano++;

    for (int d = 0; d < 4; d++) {
        dfsGrid(x + dx[d], y + dy[d], color);
    }
}

Ejemplo: Contar cuántas "islas" hay en un mapa donde # es tierra y . es agua:

int islas = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        if (!vis[i][j] && grid[i][j] == '#') {
            tamano = 0;
            dfsGrid(i, j, '#');
            islas++;
            // tamano contiene el área de esta isla
        }
    }
}

4. Verificar si un grafo es bipartito

Un grafo es bipartito si puedes colorear sus nodos con 2 colores de modo que ninguna arista conecte dos nodos del mismo color.

int color[100005];  // -1 = sin color, 0 y 1 son los colores

bool dfsBipartito(int nodo, int c) {
    color[nodo] = c;

    for (int vecino : adj[nodo]) {
        if (color[vecino] == -1) {
            if (!dfsBipartito(vecino, 1 - c)) return false;
        } else if (color[vecino] == c) {
            return false;  // Conflicto: mismo color
        }
    }

    return true;
}

Complejidad

• Tiempo: $O(V + E)$ — visitamos cada nodo y arista una vez
• Espacio: $O(V)$ — para el arreglo de visitados y la pila de recursión
• En cuadrícula: $O(n \times m)$

Errores comunes

Ejercicio de práctica

Dada una cuadrícula de N×M con # (tierra) y . (agua), encuentra:

1. El número de islas (regiones de # conectadas horizontal/verticalmente).
2. El tamaño de la isla más grande.

Ejemplo:

4 5
. . # . .
# # . . .
. . . # #
. . . # .

Salida:

3
3

#include <iostream>
#include <cstring>
using namespace std;

int n, m;
char grid[1005][1005];
bool vis[1005][1005];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int tamano;

void dfs(int x, int y) {
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (vis[x][y] || grid[x][y] != '#') return;

    vis[x][y] = true;
    tamano++;

    for (int d = 0; d < 4; d++) {
        dfs(x + dx[d], y + dy[d]);
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> grid[i][j];

    int islas = 0, maxTam = 0;
    memset(vis, false, sizeof(vis));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!vis[i][j] && grid[i][j] == '#') {
                tamano = 0;
                dfs(i, j);
                islas++;
                maxTam = max(maxTam, tamano);
            }
        }
    }

    cout << islas << endl;
    cout << maxTam << endl;

    return 0;
}

Siguiente paso

Con BFS y DFS dominados, ya puedes explorar temas más avanzados de grafos como componentes conexas, árboles y caminos más cortos.