DFS - Búsqueda en Profundidad

¿Qué es DFS?

DFS (Depth-First Search) es un algoritmo que explora un grafo yendo lo más profundo posible antes de retroceder.

Características

• Usa recursión o una pila (stack)
• Útil para detectar ciclos, componentes, y propiedades estructurales
• Complejidad: O(V + E)

Implementación recursiva

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

const int MAXN = 100005;
vector<int> adj[MAXN];
bool visitado[MAXN];

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

    for (int v : adj[u]) {
        if (!visitado[v]) {
            dfs(v);
        }
    }
}

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

Útil cuando la recursión es muy profunda:

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

    while (!s.empty()) {
        int u = s.top();
        s.pop();

        if (visitado[u]) continue;
        visitado[u] = true;

        cout << u << " ";

        for (int v : adj[u]) {
            if (!visitado[v]) {
                s.push(v);
            }
        }
    }
}

Tiempos de entrada y salida

Los tiempos de descubrimiento y finalización son útiles para muchos algoritmos:

int tiempoEntrada[MAXN], tiempoSalida[MAXN];
int tiempo = 0;

void dfs(int u, int padre = -1) {
    tiempoEntrada[u] = ++tiempo;
    visitado[u] = true;

    for (int v : adj[u]) {
        if (!visitado[v]) {
            dfs(v, u);
        }
    }

    tiempoSalida[u] = ++tiempo;
}

Propiedad de ancestro

El nodo u es ancestro de v si y solo si:

tiempoEntrada[u] < tiempoEntrada[v] && tiempoSalida[u] > tiempoSalida[v]

DFS en matriz (grid)

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

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

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

    visitado[x][y] = true;

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

Contar componentes conexas

int contarComponentes(int n) {
    int componentes = 0;

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

    return componentes;
}

Tamaño de componente

int tamanoComponente;

void dfs(int u) {
    visitado[u] = true;
    tamanoComponente++;

    for (int v : adj[u]) {
        if (!visitado[v]) {
            dfs(v);
        }
    }
}

// Uso
tamanoComponente = 0;
dfs(inicio);
cout << "Tamaño: " << tamanoComponente << endl;

Verificar si es bipartito

int color[MAXN];  // -1 = sin color, 0 y 1 = colores

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

    for (int v : adj[u]) {
        if (color[v] == -1) {
            if (!dfsBipartito(v, 1 - c)) return false;
        } else if (color[v] == c) {
            return false;  // Mismo color = no bipartito
        }
    }

    return true;
}

bool esBipartito(int n) {
    memset(color, -1, sizeof(color));

    for (int i = 1; i <= n; i++) {
        if (color[i] == -1) {
            if (!dfsBipartito(i, 0)) return false;
        }
    }

    return true;
}

Detectar ciclo en grafo no dirigido

bool tieneCiclo = false;

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

    for (int v : adj[u]) {
        if (!visitado[v]) {
            dfsCiclo(v, u);
        } else if (v != padre) {
            tieneCiclo = true;
        }
    }
}

Encontrar camino entre dos nodos

vector<int> camino;
bool encontrado = false;

void dfsCamino(int u, int destino) {
    if (encontrado) return;

    visitado[u] = true;
    camino.push_back(u);

    if (u == destino) {
        encontrado = true;
        return;
    }

    for (int v : adj[u]) {
        if (!visitado[v]) {
            dfsCamino(v, destino);
            if (encontrado) return;
        }
    }

    camino.pop_back();  // Backtrack
}

DFS con profundidad

int profundidad[MAXN];

void dfs(int u, int padre = -1, int prof = 0) {
    visitado[u] = true;
    profundidad[u] = prof;

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

Template completo

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

const int MAXN = 100005;
vector<int> adj[MAXN];
bool visitado[MAXN];
int tiempoEntrada[MAXN], tiempoSalida[MAXN];
int padre[MAXN], profundidad[MAXN];
int tiempo = 0;

void dfs(int u, int p = -1, int prof = 0) {
    visitado[u] = true;
    padre[u] = p;
    profundidad[u] = prof;
    tiempoEntrada[u] = ++tiempo;

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

    tiempoSalida[u] = ++tiempo;
}

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

    // DFS desde nodo 1
    dfs(1);

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

    cout << "Componentes: " << componentes << "\n";

    return 0;
}

BFS vs DFS

Ejercicios recomendados

1. CSES - Counting Rooms
2. CSES - Building Teams
3. CSES - Round Trip
4. Codeforces - Connected Components
5. LeetCode - Number of Islands