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.
Si el diagrama no cabe, deslízalo horizontalmente.
| Acción | Llamadas que siguen abiertas, de abajo hacia arriba |
|---|---|
| Entrar en A y marcarla | A |
| Desde A entrar en B y marcarla | A, B |
| Desde B entrar en D; A ya estaba marcada | A, B, D |
| Desde D entrar en C; B ya estaba marcada | A, B, D, C |
| C solo tiene vecinas marcadas: regresar a D | A, B, D |
| D no tiene más trabajo: regresar a B | A, B |
| B termina: regresar a A | A |
| A encuentra C ya marcada: terminar | vací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.
¿Qué cambiaría si A explorara C antes que B?
El orden sería A, C, D, B, pero seguirían visitándose las mismas cuatro estaciones y el número de componentes seguiría siendo 2. El orden depende de las listas; la conectividad no.
Práctica y modelado de grafos en 15 - Grafos I - BFS y DFS.