DFS

Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 15 de la Ruta de Aprendizaje.

El problema: explorar todas las conexiones

Tenemos estaciones unidas por pasillos en ambos sentidos. Queremos saber cuáles son alcanzables desde A y cuántos grupos separados hay. Representamos las estaciones como vértices y los pasillos como aristas de un grafo. Una componente conexa es un grupo donde puedes ir de cualquier vértice a cualquier otro.

DFS, búsqueda en profundidad, sigue un camino mientras encuentre vértices nuevos. Cuando ya no puede avanzar, vuelve al punto anterior y prueba otra salida. Para leer su implementación necesitas arreglos y recursión; la función conserva pendiente el trabajo de cada llamada mientras explora una vecina.

Avanzar y regresar

En este grafo hay conexiones A–B, A–C, B–D y C–D. E está aislada. Desde A elegiremos B antes que C. En D elegiremos B antes que C.

ABDCEEntrar: A → B → D → CRegresar: C → D → B → A; E queda sin visitar

Si el diagrama no cabe, deslízalo horizontalmente.

AcciónLlamadas que siguen abiertas, de abajo hacia arriba
Entrar en A y marcarlaA
Desde A entrar en B y marcarlaA, B
Desde B entrar en D; A ya estaba marcadaA, B, D
Desde D entrar en C; B ya estaba marcadaA, B, D, C
C solo tiene vecinas marcadas: regresar a DA, B, D
D no tiene más trabajo: regresar a BA, B
B termina: regresar a AA
A encuentra C ya marcada: terminarvacía

El orden de descubrimiento es A, B, D, C. Regresar no desmarca el vértice: queremos recordar que ya exploramos esa estación. E no aparece porque no existe un camino desde A. El conjunto de llamadas pendientes se llama pila de llamadas; la última llamada que entra es la primera que termina.

Por qué hay que marcar al entrar

Si esperáramos hasta regresar, B vería a A todavía sin marcar y volvería a llamarla; A llamaría otra vez a B. Marcar al entrar corta ese ciclo inmediatamente. La propiedad que conservamos es que cada vértice se explora como nuevo una sola vez.

Todo vértice alcanzable acaba visitado: si faltara uno, en un camino desde A habría una primera arista desde un vértice visitado hacia uno no visitado. Al revisar esa arista, DFS habría entrado en él. Esto contradice que quedara fuera.

Implementación y preparación de los datos

vector<vector<int>> g;
vector<bool> visitado;
 
void dfs(int u) {
    visitado[u] = true;                  // marcar ANTES de bajar: evita ciclos infinitos
    for (int v : g[u])
        if (!visitado[v]) dfs(v);
}
 
// contar componentes conexas: cada arranque nuevo es una componente
int componentes(int n) {
    visitado.assign(n, false);
    int c = 0;
    for (int u = 0; u < n; u++)
        if (!visitado[u]) { c++; dfs(u); }
    return c;
}

El código usa índices 0…n−1. Numera A…E como 0…4 y asigna g = {{1,2}, {0,3}, {0,3}, {1,2}, {}}. Cada conexión aparece en las listas de sus dos extremos. g[u] contiene los vecinos de u.

Para explorar solo desde A, primero ejecuta visitado.assign(5, false) y luego dfs(0). Quedarán marcadas las posiciones 0, 1, 2 y 3. Para contar todos los grupos llama componentes(5): inicializa las marcas, explora el grupo de A y después arranca otra búsqueda desde E. Devuelve 2.

g debe tener n listas, y todos los vecinos deben ser índices válidos. Las variables globales guardan el grafo y las marcas; el bloque necesita los encabezados de C++ y using namespace std; en el programa que lo use.

Costos y límites

Cada vértice se marca una vez y cada lista de vecinos se recorre una vez: O(V + E) en tiempo y O(V) de memoria adicional para marcas y llamadas. Un grafo vacío tiene cero componentes; para llamar a dfs sí debe existir el origen.

Una cadena larga produce tantas llamadas anidadas como vértices. El límite de pila depende del entorno; para entradas grandes considera una implementación iterativa con stack, que guarda explícitamente el trabajo pendiente, o BFS.

El conteo de componentes de arriba es para grafos no dirigidos. En un grafo dirigido, seguir salidas no equivale a calcular componentes fuertemente conexas: para eso existe SCC (Tarjan). DFS tampoco garantiza caminos mínimos: en el dibujo llega a C por A–B–D–C aunque existe A–C.

Práctica y modelado de grafos en 15 - Grafos I - BFS y DFS.