Búsqueda en Profundidad (DFS)

¿Qué es DFS?

DFS (Depth-First Search o Búsqueda en Profundidad) es un algoritmo para explorar grafos que avanza lo más profundo posible antes de retroceder.

Es como explorar un laberinto: sigues un camino hasta que llegas a un callejón sin salida, luego regresas y pruebas otra ruta.

💡 Característica principal: DFS usa recursión (o una pila) y es excelente para problemas de conectividad, ciclos y backtracking.

Visualización

Grafo:
    1 --- 2 --- 5
    |     |
    3 --- 4

DFS desde nodo 1:
1 → 2 → 5 (retrocede) → 4 → 3 (retrocede a 4) (retrocede a 2) (retrocede a 1)

Orden: 1 → 2 → 5 → 4 → 3

Implementación recursiva

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[100005];
bool visitado[100005];

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

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

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);
    }

    dfs(1);

    return 0;
}

Implementación iterativa (con pila)

Útil cuando la recursión puede causar stack overflow:

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 << " ";

        // Agregar vecinos en orden inverso para mantener el orden
        for (int i = adj[nodo].size() - 1; i >= 0; i--) {
            if (!visitado[adj[nodo][i]]) {
                pila.push(adj[nodo][i]);
            }
        }
    }
}

Complejidad

DFS vs BFS

Aplicaciones de DFS

1. Contar componentes conexas

int contarComponentes(int n) {
    int componentes = 0;
    fill(visitado, visitado + n + 1, false);

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

    return componentes;
}

2. Detectar ciclos en grafo no dirigido

bool tieneCiclo(int nodo, int padre) {
    visitado[nodo] = true;

    for (int vecino : adj[nodo]) {
        if (!visitado[vecino]) {
            if (tieneCiclo(vecino, nodo)) {
                return true;
            }
        } else if (vecino != padre) {
            // Encontramos un nodo visitado que no es el padre
            return true;
        }
    }

    return false;
}

bool grafoCiclo(int n) {
    fill(visitado, visitado + n + 1, false);

    for (int i = 1; i <= n; i++) {
        if (!visitado[i]) {
            if (tieneCiclo(i, -1)) {
                return true;
            }
        }
    }

    return false;
}

3. Detectar ciclos en grafo dirigido

Usamos tres colores: blanco (no visitado), gris (en proceso), negro (terminado).

int color[100005];  // 0 = blanco, 1 = gris, 2 = negro

bool tieneCicloDirigido(int nodo) {
    color[nodo] = 1;  // Gris - en proceso

    for (int vecino : adj[nodo]) {
        if (color[vecino] == 1) {
            // Encontramos un nodo en proceso (ciclo)
            return true;
        }
        if (color[vecino] == 0) {
            if (tieneCicloDirigido(vecino)) {
                return true;
            }
        }
    }

    color[nodo] = 2;  // Negro - terminado
    return false;
}

4. Ordenamiento topológico

Ordena los nodos de un DAG (grafo dirigido acíclico) de forma que para cada arista u→v, u aparece antes que v.

vector<int> ordenTopologico;

void dfsTopologico(int nodo) {
    visitado[nodo] = true;

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

    ordenTopologico.push_back(nodo);  // Agregar al terminar
}

vector<int> topSort(int n) {
    fill(visitado, visitado + n + 1, false);
    ordenTopologico.clear();

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

    reverse(ordenTopologico.begin(), ordenTopologico.end());
    return ordenTopologico;
}

5. Encontrar componentes fuertemente conexas (Kosaraju)

En un grafo dirigido, una SCC es un conjunto maximal de nodos donde puedes llegar de cualquier nodo a cualquier otro.

vector<int> adj[100005];      // Grafo original
vector<int> adjRev[100005];   // Grafo transpuesto
bool visitado[100005];
stack<int> orden;
int componente[100005];

void dfs1(int nodo) {
    visitado[nodo] = true;
    for (int vecino : adj[nodo]) {
        if (!visitado[vecino]) {
            dfs1(vecino);
        }
    }
    orden.push(nodo);
}

void dfs2(int nodo, int comp) {
    componente[nodo] = comp;
    for (int vecino : adjRev[nodo]) {
        if (componente[vecino] == 0) {
            dfs2(vecino, comp);
        }
    }
}

int kosaraju(int n) {
    // Paso 1: DFS en orden de finalización
    fill(visitado, visitado + n + 1, false);
    for (int i = 1; i <= n; i++) {
        if (!visitado[i]) {
            dfs1(i);
        }
    }

    // Paso 2: DFS en grafo transpuesto
    fill(componente, componente + n + 1, 0);
    int numSCC = 0;

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

        if (componente[nodo] == 0) {
            numSCC++;
            dfs2(nodo, numSCC);
        }
    }

    return numSCC;
}

DFS en matrices

int n, m;
char grid[1005][1005];
bool visitado[1005][1005];

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool esValido(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m && grid[x][y] != '#';
}

void dfsMatriz(int x, int y) {
    visitado[x][y] = true;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (esValido(nx, ny) && !visitado[nx][ny]) {
            dfsMatriz(nx, ny);
        }
    }
}

Ejemplo: Contar islas

int contarIslas() {
    int islas = 0;
    memset(visitado, false, sizeof(visitado));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '.' && !visitado[i][j]) {
                dfsMatriz(i, j);
                islas++;
            }
        }
    }

    return islas;
}

DFS con tiempos de entrada y salida

Útil para determinar si un nodo es ancestro de otro:

int tiempoEntrada[100005];
int tiempoSalida[100005];
int tiempo = 0;

void dfsConTiempos(int nodo, int padre) {
    tiempoEntrada[nodo] = ++tiempo;

    for (int vecino : adj[nodo]) {
        if (vecino != padre) {
            dfsConTiempos(vecino, nodo);
        }
    }

    tiempoSalida[nodo] = ++tiempo;
}

// u es ancestro de v si:
// tiempoEntrada[u] <= tiempoEntrada[v] && tiempoSalida[u] >= tiempoSalida[v]
bool esAncestro(int u, int v) {
    return tiempoEntrada[u] <= tiempoEntrada[v] &&
           tiempoSalida[u] >= tiempoSalida[v];
}

DFS en árboles

Calcular profundidad y tamaño de subárbol

int profundidad[100005];
int tamano[100005];

void dfsArbol(int nodo, int padre, int prof) {
    profundidad[nodo] = prof;
    tamano[nodo] = 1;

    for (int hijo : adj[nodo]) {
        if (hijo != padre) {
            dfsArbol(hijo, nodo, prof + 1);
            tamano[nodo] += tamano[hijo];
        }
    }
}

Encontrar diámetro del árbol

El diámetro es el camino más largo entre dos nodos.

int maxDist, nodoMasLejano;

void dfsDiametro(int nodo, int padre, int dist) {
    if (dist > maxDist) {
        maxDist = dist;
        nodoMasLejano = nodo;
    }

    for (int vecino : adj[nodo]) {
        if (vecino != padre) {
            dfsDiametro(vecino, nodo, dist + 1);
        }
    }
}

int diametro(int n) {
    // Primer DFS desde cualquier nodo
    maxDist = 0;
    dfsDiametro(1, -1, 0);

    // Segundo DFS desde el nodo más lejano
    maxDist = 0;
    dfsDiametro(nodoMasLejano, -1, 0);

    return maxDist;
}

Backtracking con DFS

DFS es la base del backtracking para explorar todas las soluciones:

vector<int> solucion;

void backtrack(int nodo, int objetivo) {
    if (nodo == objetivo) {
        // Encontramos una solución
        for (int x : solucion) cout << x << " ";
        cout << endl;
        return;
    }

    for (int vecino : adj[nodo]) {
        solucion.push_back(vecino);
        backtrack(vecino, objetivo);
        solucion.pop_back();  // Deshacer
    }
}

Template completo

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
bool vis[MAXN];
int parent[MAXN];
int depth[MAXN];
int tin[MAXN], tout[MAXN];
int timer = 0;

void dfs(int u, int p = -1, int d = 0) {
    vis[u] = true;
    parent[u] = p;
    depth[u] = d;
    tin[u] = ++timer;

    for (int v : adj[u]) {
        if (!vis[v]) {
            dfs(v, u, d + 1);
        }
    }

    tout[u] = ++timer;
}

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    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);
    }

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

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

    return 0;
}

Resumen

Ejercicios recomendados

1. CSES - Counting Rooms
2. CSES - Round Trip
3. CSES - Course Schedule
4. CSES - Tree Diameter
5. LeetCode - Number of Islands
6. Codeforces - DFS Order