15 · Grafos I: BFS y DFS
Grafos y consultas · Ruta de Aprendizaje
Antes de empezar. Vectores y matrices: 03 - Arreglos y búsqueda lineal y 04 - Matrices; recursión para DFS: 09 - Recursión.
🎯 Objetivos
Al terminar este módulo sabes:
- Pasar de un dibujo a listas de aristas, listas de adyacencia y matrices.
- Elegir una representación y adaptarla a dirección y pesos.
- Recorrerlo con DFS y BFS, y contar componentes conexas.
- Ver la grilla de un problema como el grafo que realmente es (flood fill).
La pregunta guía es cómo pasar de un mapa de conexiones a un programa que lo recorra. Puedes leerlo en tres tramos: representar las conexiones, recorrerlas y aplicar el recorrido a una grilla.
📖 La lección
Recorrido de lectura: representar → DFS → BFS → grillas.
Del problema al grafo
Imagina cuatro ciudades y tres carreteras de doble sentido: 1–2, 1–3
y 3–4. Queremos saber a qué ciudades podemos llegar desde la ciudad 1.
Cada ciudad es un nodo (también llamado vértice) y cada carretera es una arista. Dos nodos son vecinos si una arista los conecta directamente. El nodo 1 tiene vecinos 2 y 3. Podemos llegar de 1 a 4 pasando por 3, pero 1 y 4 no son vecinos: un camino puede usar varias aristas.
El dibujo nos ayuda a pensar, pero el programa necesita guardar esos datos. La posición de los círculos en el papel no importa aquí: moverlos sin cambiar las conexiones conserva el mismo grafo. Tampoco los números indican cercanía; son identificadores de las ciudades.
Usaremos el mismo grafo en tres representaciones. Todas conservan sus conexiones; cambia cómo las organizan y qué preguntas responden fácilmente.
Si el diagrama no cabe, deslízalo horizontalmente.
La entrada: qué significan los números
En este ejemplo, la primera línea indica n nodos y m aristas. Después
vienen m líneas con los dos extremos de cada arista:
4 3
1 2
1 3
3 4La línea 1 3 describe una carretera, no el recorrido que debemos hacer.
Como es de doble sentido, permite ir de 1 a 3 y de 3 a 1, aunque aparezca
una sola vez en la entrada. Suponemos nodos numerados 1..n, sin aristas
repetidas ni conexiones de un nodo consigo mismo. Otros problemas pueden
usar convenciones distintas: se leen en el enunciado.
1. Lista de aristas: guardar las conexiones
Una opción directa es guardar cada línea como un par (u, v):
| Posición en la lista | Arista |
|---|---|
| 0 | (1, 2) |
| 1 | (1, 3) |
| 2 | (3, 4) |
En C++, pair<int, int> reúne los dos extremos: .first guarda el primero
y .second el segundo. El vector guarda todos esos pares. La sintaxis
se desarrolla en 06 - Conjuntos, mapas y pares.
int n, m;
vector<pair<int, int>> aristas;
void leer_aristas() {
cin >> n >> m;
aristas.clear();
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
aristas.push_back({u, v});
}
}Es cómoda para recorrer todas las aristas. Pero para encontrar los vecinos
del nodo 3 hay que revisar la lista completa: en (1, 3) aparece como segundo
extremo y en (3, 4) como primero. Sus vecinos son 1 y 4.
Guardamos también n: la lista por sí sola no nos diría que existe una ciudad
sin carreteras.
2. Lista de adyacencia: guardar los vecinos de cada nodo
Ahora organizamos la misma información por ciudad:
| Nodo u | ady[u]: vecinos directos de u |
|---|---|
| 1 | {2, 3} |
| 2 | {1} |
| 3 | {1, 4} |
| 4 | {3} |
ady es un vector de vectores. El vector exterior elige un nodo;
el interior contiene sus vecinos. ady[3] es la lista {1, 4} y
ady[3][0] vale 1: el primer vecino guardado del nodo 3. La posición interior
no es otro identificador de nodo. Si el nodo no tiene vecinos, su lista está vacía.
Veamos cómo se construye, empezando con todas las listas vacías:
| Carretera leída | Primera inserción | Segunda inserción |
|---|---|---|
| 1–2 | ady[1] pasa a {2} | ady[2] pasa a {1} |
| 1–3 | ady[1] pasa a {2, 3} | ady[3] pasa a {1} |
| 3–4 | ady[3] pasa a {1, 4} | ady[4] pasa a {3} |
int n, m;
vector<vector<int>> ady; // global: DFS y BFS usarán estas listas
void leer_grafo() {
cin >> n >> m;
ady.assign(n + 1, {}); // n+1 listas vacías; dejamos ady[0] sin usar
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
ady[u].push_back(v); // desde u podemos ir a v
ady[v].push_back(u); // desde v podemos ir a u
}
}La carretera es una, las entradas son dos. No duplicamos la carretera
real: guardamos cómo encontrarla desde cualquiera de sus extremos.
Por eso hay 2m números repartidos entre las listas. Reservar las listas
cuesta O(n) y guardar las conexiones O(m): memoria y construcción O(n + m).
Para imprimir los vecinos de 3 basta for (int v : ady[3]) cout << v << " ";:
el ciclo visita 1 y 4, sin revisar otras carreteras. El número de vecinos se
llama grado; ese recorrido cuesta O(grado(3)). Las listas conservan el
orden de inserción y no quedan necesariamente ordenadas por número.
3. Matriz de adyacencia: una casilla por pareja de nodos
La fila representa el nodo de salida y la columna el de llegada.
conecta[u][v] vale 1 si hay una arista directa de u a v, y 0 si no la hay:
| Desde / hacia | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 |
La fila 3 tiene unos en las columnas 1 y 4: son los mismos vecinos de
ady[3]. La casilla [1][4] vale 0 aunque podamos llegar pasando por 3:
esta matriz registra aristas, no todos los caminos posibles.
int n, m;
vector<vector<int>> conecta;
void leer_matriz() {
cin >> n >> m;
conecta.assign(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
conecta[u][v] = 1;
conecta[v][u] = 1;
}
}Dejamos la fila y columna 0 sin usar para conservar los identificadores 1..n.
La matriz es simétrica porque cada carretera permite ambos sentidos:
conecta[u][v] == conecta[v][u]. La diagonal es cero porque este ejemplo
no tiene aristas de un nodo a sí mismo.
Consultar si 1 y 4 son vecinos es leer una casilla: O(1). Encontrar todos los vecinos de 3 requiere revisar las n columnas de su fila: O(n), aunque tenga solo dos vecinos. Inicializar y guardar la matriz cuesta O(n²), incluso cuando hay muy pocas aristas.
¿Cuál conviene usar?
| Pregunta o recurso | Lista de aristas | Lista de adyacencia | Matriz de adyacencia |
|---|---|---|---|
| Memoria para guardar las conexiones | O(m) | O(n + m) | O(n²) |
| ¿Existe la arista u–v? | O(m) | O(grado(u)), buscando en la lista | O(1) |
| Recorrer vecinos de u | O(m) | O(grado(u)) | O(n) |
| Recorrer todas las aristas | O(m) | O(n + m) | O(n²) |
Con 100 000 nodos y 100 000 aristas, una matriz tendría 10 000 millones de casillas; las listas de adyacencia guardarían 100 000 listas y 200 000 vecinos. Un grafo con pocas aristas respecto de n² se llama disperso; uno con muchas se llama denso. La diferencia de memoria importa mucho en el primero.
Para DFS y BFS elegiremos listas de adyacencia, porque esos algoritmos preguntan repetidamente por los vecinos del nodo actual. Una matriz puede convenir si n es pequeño y consultamos muchas parejas concretas. Una lista de aristas es útil cuando el algoritmo trabaja carretera por carretera, como Kruskal (MST), que se estudia más adelante.
Los tres bloques de lectura son alternativas, no partes para pegar juntas.
Para probar una, pon sus variables y función antes de main, con
#include <bits/stdc++.h> y using namespace std; al principio. Desde
main llama a la función elegida. A partir de aquí usaremos leer_grafo().
¿Qué cambia si las calles tienen un solo sentido?
Un grafo dirigido distingue u → v de v → u. Si la entrada describe
1 → 2, 1 → 3 y 3 → 4, las listas de destinos son:
| Nodo | Vecinos a los que puede ir |
|---|---|
| 1 | {2, 3} |
| 2 | {} |
| 3 | {4} |
| 4 | {} |
En el código guardamos solo ady[u].push_back(v): quitamos la inserción
inversa. En la matriz escribimos solo conecta[u][v] = 1, así que ya no
necesita ser simétrica. En la lista de aristas, el orden del par indica
origen y destino. Desde 1 podemos llegar a 4; desde 4 no podemos volver a 1.
¿Y si cada carretera tiene un costo?
Un grafo con pesos asocia un dato a cada arista: por ejemplo, minutos de
viaje. Demos costos 7, 2 y 5 a las carreteras 1–2, 1–3 y 3–4.
En una lista de adyacencia, cada vecino se convierte en un par (destino, peso):
ady_peso[1] guardaría {(2, 7), (3, 2)}.
int n = 4;
vector<vector<pair<int, int>>> ady_peso(n + 1);
ady_peso[1].push_back({2, 7});
ady_peso[2].push_back({1, 7}); // la misma carretera, vista desde el otro extremoAquí ady_peso[1][0].first vale 2 (destino) y .second vale 7 (costo).
Las otras carreteras se agregan del mismo modo. Una lista de aristas puede
guardar tres datos (origen, destino, peso). En una matriz podemos guardar
el peso en cada casilla, pero necesitamos distinguir ausencia de arista
de una arista con peso cero, usando una marca especial o una matriz de presencia.
Dirección y peso son decisiones independientes: puede haber grafos dirigidos
con pesos o sin ellos, y no dirigidos con pesos o sin ellos. El camino
1 → 3 → 4 tiene dos aristas y costo 2 + 5 = 7. BFS contará aristas;
para minimizar costos no negativos estudiaremos Dijkstra.
Una comprobación con el mismo dibujo
Si quitamos la carretera 1–3, ¿qué cambia en cada representación?
Ver razonamiento
En la lista de aristas desaparece
(1, 3). En las listas de adyacencia, quitamos el 3 deady[1]y el 1 deady[3]. En la matriz, las casillas[1][3]y[3][1]pasan a cero. Los cuatro nodos siguen existiendo, pero quedan separados en dos grupos:{1, 2}y{3, 4}. Guardar o quitar una arista cambia conexiones; no elimina sus nodos.
Del dato guardado al recorrido
Volvamos al grafo inicial no dirigido y sin pesos. La representación
responde «¿a quién puedo ir directamente desde u?». DFS y BFS combinan esas
respuestas para descubrir también nodos a varios pasos de distancia.
En ambos aparecerá for (int v : ady[u]): ahora sabemos que significa
«para cada vecino v del nodo u».
DFS: profundizar hasta el fondo
La pregunta es qué nodos podemos alcanzar desde 1. En cada nodo, DFS lo marca y elige una vecina todavía no visitada. Explora todo lo que pueda desde ella antes de continuar con las otras vecinas. La llamada anterior queda esperando, como en el módulo de recursión.
Marcar al entrar impide volver a explorar un nodo ya descubierto. Incluso una sola carretera de doble sentido lo exige: al pasar de 1 a 2, la lista de 2 contiene otra vez a 1. Sin la marca podríamos rebotar indefinidamente.
// usa: ady // del bloque anterior
vector<bool> visitado; // global; visitado.assign(n + 1, false) antes del primer dfs
void dfs(int u) {
visitado[u] = true;
for (int v : ady[u])
if (!visitado[v]) dfs(v);
}El marcado evita volver a explorar lo que ya conocemos. Costo: O(n + m): cada nodo se descubre una vez y cada lista de vecinos se recorre una vez. (Ficha de referencia: DFS.)
Para ejecutar el ejemplo desde main, llama leer_grafo(), luego
visitado.assign(n + 1, false) y finalmente dfs(1) (con n ≥ 1).
En nuestro ejemplo, DFS visita 1, luego 2; al no encontrar vecinos nuevos,
vuelve al 1, visita 3 y desde allí llega al 4. El ciclo de vecinos usa
exactamente las listas que construimos antes:
| Acción | Llamadas pendientes, de la primera a la actual |
|---|---|
| Entrar en 1 | 1 |
| Desde 1, entrar en 2 | 1, 2 |
| 2 solo tiene a 1, ya marcado: regresar | 1 |
| Continuar con el siguiente vecino de 1: entrar en 3 | 1, 3 |
| 3 omite a 1 y entra en 4 | 1, 3, 4 |
| 4 no tiene vecinos nuevos: regresar; luego terminan 3 y 1 | vacía |
Regresar no borra las marcas: representan lo descubierto durante todo
el recorrido, no solo el camino de llamadas actual. Si agregamos un nodo 5 aislado,
ady[5] estará vacía y dfs(1) no lo alcanzará. Para contar todas las
componentes con el bloque siguiente, empieza otra vez con visitado en falso.
Componentes conexas: el primer superpoder
“¿Cuántas islas de nodos conectados hay?” — lanza un recorrido desde cada nodo aún no visitado y cuenta cuántas veces partiste:
// usa: dfs, visitado, n // de los bloques anteriores; visitado en false al partir
int componentes = 0;
for (int u = 1; u <= n; u++)
if (!visitado[u]) { componentes++; dfs(u); }Este otro grafo tiene seis nodos y dos componentes: el recorrido desde 1 no alcanza a 5 ni a 6. Las listas permiten ver ambos grupos:
Si el diagrama no cabe, deslízalo horizontalmente.
Muchos enunciados que no mencionan grafos son exactamente esto (¿quiénes quedan conectados?, ¿cuántos grupos de amigos?).
BFS: por capas
El BFS recorre lo mismo que el DFS, pero cambia el orden: en vez de hundirse por una rama, visita por niveles de cercanía (primero los vecinos, después los vecinos de los vecinos):
Para que se note la diferencia de orden, este dibujo usa otro grafo, un árbol de siete nodos. En ambos recorridos se elige primero la rama izquierda. Los números dentro de los círculos identifican nodos; los ordinales (1.º, 2.º…) indican cuándo se visitan.
Si el diagrama no cabe, deslízalo horizontalmente.
Y en vez de recursión usa una cola: la estructura donde el primero que entra es el primero que sale, como una fila de supermercado. Esa es la razón de las capas: todos los nodos a distancia 1 se encolan antes que los de distancia 2, y así sucesivamente.
En C++ la cola es `queue` y son tres operaciones:
q.push(x) encola, q.front() mira quién va primero, q.pop() lo saca.
// usa: ady, visitado // los mismos globales de arriba
void bfs(int origen) {
queue<int> q;
visitado[origen] = true; // ⚠️ se marca AL ENCOLAR, no al sacar
q.push(origen);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : ady[u])
if (!visitado[v]) {
visitado[v] = true;
q.push(v);
}
}
}Para probar BFS después de DFS, reinicia visitado.assign(n + 1, false)
y llama bfs(1): reutilizar las marcas anteriores impediría el recorrido.
En el grafo inicial 1–2, 1–3, 3–4, la cola empieza [1]. Sacar 1 deja [2,3]; sacar 2 deja [3]; sacar 3 agrega 4 y deja [4]; sacar 4 la vacía. El DFS había visitado también 1,2,3,4, pero con llamadas pendientes: [1] → [1,2] → [1] → [1,3] → [1,3,4]. Coincidir en el orden de este ejemplo no vuelve iguales los algoritmos: uno conserva una cola y el otro una pila de llamadas.
El ⚠️ es el error clásico: si marcas al sacar de la cola, un nodo con tres vecinos ya encolados entra tres veces y el recorrido se degrada.
Si el diagrama no cabe, deslízalo horizontalmente.
Mismo costo que el DFS, O(n + m). Para “¿están conectados?” o “¿cuántas componentes hay?” los dos sirven y eliges el que prefieras — la ventaja propia del BFS aparece en el módulo 16: recorrer por capas significa que la primera vez que llegas a un nodo llegaste por el camino más corto, así que la misma cola mide distancias gratis.
La grilla es un grafo disfrazado
El truco que resuelve media fase nacional: cada celda es un nodo y sus vecinos son arriba/abajo/izquierda/derecha. El DFS sobre celdas se llama flood fill (pintar una región):
int n;
int m;
vector<string> mapa; // globales: el mapa se lee en main, fila por fila
void inundar(int i, int j) {
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}; // abajo, arriba, der, izq
if (i < 0 || i >= n || j < 0 || j >= m) return; // fuera del mapa
if (mapa[i][j] != '.') return; // muro o ya pintado
mapa[i][j] = 'x';
for (int d = 0; d < 4; d++) inundar(i + dx[d], j + dy[d]);
}Para completar el programa, coloca lo siguiente dentro de main, después de las definiciones anteriores:
// usa: n, m, mapa, inundar
cin >> n >> m;
mapa.resize(n);
for (string& fila : mapa) cin >> fila;
int habitaciones = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (mapa[i][j] == '.') {
habitaciones++;
inundar(i, j);
}
cout << habitaciones << "\n";Con entrada 3 5 y filas ..#.., ..###, ###.., imprime 3. El primer recorrido pinta el grupo superior izquierdo; el segundo, el superior derecho; el tercero, el inferior derecho. El ciclo exterior encuentra cada habitación una sola vez porque las celdas pintadas ya no son puntos.
Si el diagrama no cabe, deslízalo horizontalmente.
Contar habitaciones de un laberinto = contar componentes en la grilla, y la ficha con el patrón completo es Flood fill. (Ojo con grillas de 1000×1000: la profundidad puede alcanzar un millón de llamadas y agotar la pila — la versión BFS con cola no tiene ese problema.)
🏋️ Práctica
Práctica directa: Del mapa a los vecinos
Hay cuatro ciudades y carreteras de doble sentido 1–2 y 2–4. Escribe las listas de vecinos y la fila 2 de la matriz de adyacencia, usando columnas 1..4.
Comprobar la representación
Las listas son {2}, {1,4}, {}, {2}; la fila 2 es
1 0 0 1. La ciudad 3 existe aunque no tenga carreteras. Hay dos carreteras y cuatro entradas en total en las listas, porque se pueden recorrer en ambos sentidos.
Aplicar el recorrido: Contar habitaciones
Usa el programa de grilla con entrada 3 5 / ..#.. / ..### / ###... Salida: 3.
En los ejemplos de entrada y salida, / separa líneas; no se escribe en el archivo.
Idea para comprobar tu solución
Cada celda libre no visitada inicia una habitación nueva. Cambia una pared para unir dos regiones y comprueba que el conteo baja a 2.
Variación: Un grupo aislado
Hay seis vértices 0..5 y aristas no dirigidas 0–1, 1–2 y 3–4. Cuenta los grupos conectados. Luego agrega 2–3 y vuelve a contar.
Una pista, si la necesitas
¿Qué ocurre con un vértice que no tiene vecinos?
Contrastar el razonamiento
Primero hay tres grupos: {0,1,2}, {3,4} y {5}. Después quedan dos. Inicia un recorrido en cada vértice aún no visitado; el vértice aislado también cuenta.
Aplicar en problemas
Los problemas siguientes requieren traducir un enunciado y pueden combinar otras ideas. Su procedencia e idioma no indican un orden obligatorio de dificultad.
Problemas OCI reales, en español (cada nota trae el link a su mirror):
| # | Problema | Fase | Qué practica |
|---|---|---|---|
| 1 | Viaje a la playa | Nacional 2022 | BFS en grilla con aristas condicionadas |
| 2 | Ociman y su pogo stick | Nacional 2018 | BFS con saltos de vecindario grande |
| 3 | Por una ciudad más caminable | Nacional 2021 | BFS acotado sumando por arista |
| 4 | ⭐ Figuras | Nacional 2023 | BFS con varios orígenes (se adelanta al 16) + una observación bonita |
Más aplicaciones (en inglés)
| # | Problema | Dificultad | Qué practica |
|---|---|---|---|
| 1 | Counting Rooms (CSES 1192) | ★★ (—) | flood fill puro |
| 2 | Building Roads (CSES 1666) | ★★ (—) | componentes conexas |
| 3 | The Lakes (1829E) | ★★ (1100) | flood fill acumulando valores |
| 4 | Ice Skating (217A) | ★★★ (1200) | inventar las aristas correctas |
| 5 | ⭐ Kefa and Park (580C) | ★★★★ (1500) | DFS con condición acumulada |
Para pensar: dos caminos hacia el mismo vértice
Un grafo no dirigido tiene aristas A–B, A–C, B–D y C–D.
BFS parte de A y encola B antes que C. ¿Qué ocurre con D si marcas los
vértices al encolarlos? ¿Y si esperas hasta sacarlos de la cola?
Si el diagrama no cabe, deslízalo horizontalmente.
Ver razonamiento
Después de procesar A, la cola es
[B, C]. B descubre D y deja[C, D]. Si D ya quedó marcado, C no lo vuelve a encolar: cada vértice entra una vez. Si se marca solo al salir, C todavía lo ve sin visitar y deja[D, D]. Se puede adaptar el algoritmo para ignorar duplicados al extraer, pero marcar al encolar evita ese trabajo y da la invariante más simple: todo vértice en la cola ya está descubierto.
← 14 - Programación dinámica I · Ruta de Aprendizaje · 16 - Distancias en grafos →