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.

Ciudades y carreteras1234Lista de aristas(1, 2)(1, 3)(3, 4)Listas de adyacenciaady[1] = {2, 3}ady[2] = {1}ady[3] = {1, 4}ady[4] = {3}Matriz de adyacencia123410110210003100140010Mismas conexiones; cambia la forma de encontrarlas en memoria.

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 4

La 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 listaArista
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 uady[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ídaPrimera inserciónSegunda inserción
1–2ady[1] pasa a {2}ady[2] pasa a {1}
1–3ady[1] pasa a {2, 3}ady[3] pasa a {1}
3–4ady[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 / hacia1234
10110
21000
31001
40010

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 recursoLista de aristasLista de adyacenciaMatriz de adyacencia
Memoria para guardar las conexionesO(m)O(n + m)O(n²)
¿Existe la arista u–v?O(m)O(grado(u)), buscando en la listaO(1)
Recorrer vecinos de uO(m)O(grado(u))O(n)
Recorrer todas las aristasO(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:

NodoVecinos 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 extremo

Aquí 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?

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ónLlamadas pendientes, de la primera a la actual
Entrar en 11
Desde 1, entrar en 21, 2
2 solo tiene a 1, ya marcado: regresar1
Continuar con el siguiente vecino de 1: entrar en 31, 3
3 omite a 1 y entra en 41, 3, 4
4 no tiene vecinos nuevos: regresar; luego terminan 3 y 1vací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:

123456componente 1: {1, 2, 3, 4}componente 2: {5, 6}ady[u] = vecinos de uady[1] = {2, 3}ady[2] = {1, 4}ady[3] = {1, 4}ady[4] = {2, 3}ady[5] = {6}ady[6] = {5}2m entradas en total

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.

11º22º36º43º54º67º75ºDFS desde 1: 1 2 4 5 7 3 6capa 0capa 1capa 2capa 311º22º33º44º55º66º77ºBFS desde 1: 1 2 3 4 5 6 7el número es el orden de visita; los dos tocan cada nodo una vez, pero en otro orden

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.

abcxa, b y c salen de la colay cada uno mira a xmarcar al encolar ✅cola: … xa lo encola y lo marca; b y c ya lo ven marcadomarcar al sacar ❌cola: … x x xentra tres veces: en grafos densos el BFS 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.

El mismo mapa de la entrada: 3 × 511221133Mismo número = misma habitación. Oscuro = muro.Solo conectamos vecinas libres por un lado;las diagonales no conectan habitaciones.3 habitaciones = 3 componentes conexas

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.

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.

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.

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):

#ProblemaFaseQué practica
1Viaje a la playaNacional 2022BFS en grilla con aristas condicionadas
2Ociman y su pogo stickNacional 2018BFS con saltos de vecindario grande
3Por una ciudad más caminableNacional 2021BFS acotado sumando por arista
4⭐ FigurasNacional 2023BFS con varios orígenes (se adelanta al 16) + una observación bonita

Más aplicaciones (en inglés)

#ProblemaDificultadQué practica
1Counting Rooms (CSES 1192)★★ (—)flood fill puro
2Building Roads (CSES 1666)★★ (—)componentes conexas
3The Lakes (1829E)★★ (1100)flood fill acumulando valores
4Ice 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?

ABCDInicio en AB y C pueden descubrir el mismo D.

Si el diagrama no cabe, deslízalo horizontalmente.


← 14 - Programación dinámica I · Ruta de Aprendizaje · 16 - Distancias en grafos →