Sesión 33: Refuerzo y Evaluación de Grafos, BFS & Dijkstra#

Navegación rápida:

• ← Sesión 32: Evaluación — Árboles Binarios y BST
• Sesión 34: Simulacro de Entrevista FAANG Onsite Completo →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_33.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

En esta sesión evaluamos la capacidad de resolver problemas de optimización de redes sobre grafos implícitos y grafos ponderados con restricciones adicionales de saltos. Consulta el Glosario Maestro y la Guía de Diagramas.

Grafo Implícito de Estados#

• (a) En palabras simples (intuición): Un laberinto que no está dibujado en ningún mapa. Solo sabes en qué habitación estás y qué puertas puedes abrir en ese momento. Las paredes y los pasillos van apareciendo en tu mente únicamente a medida que caminas.
• (b) Definición técnica paso a paso: Grafo G = (V, E) donde ni los vértices ni las aristas están almacenados explícitamente en memoria RAM previa. En su lugar, existe una función generadora de vecinos que, dado un estado u, genera dinámicamente el conjunto de estados válidos adyacentes aplicando reglas de transición formales (ej. cambiar 1 letra en Word Ladder).
• (c) Cómo funciona en Rust (memoria y tipos): Se modela operando directamente sobre tipos &str o String en el Heap, consultando membresía en un HashSet<&str> precomputado en tiempo constante O(1).
• (d) Error típico de Junior: Intentar construir la matriz o lista de adyacencia completa de N × N antes de comenzar; para N = 5,000, esto consume O(N²) tiempo y memoria innecesariamente cuando la ruta óptima podría hallarse en solo 4 saltos.

BFS Bidireccional (Bidirectional Search)#

• (a) En palabras simples (intuición): Dos equipos de obreros perforando un túnel a través de una montaña: uno empieza en el lado norte y el otro en el lado sur. Al avanzar ambos al encuentro del otro, terminan el túnel en la mitad del tiempo y exploran solo una fracción diminuta del volumen de roca comparado con un solo equipo cavando de extremo a extremo.
• (b) Definición técnica paso a paso: Variante de Breadth-First Search que expande simultáneamente dos fronteras: una hacia adelante desde el origen (begin_word) y otra hacia atrás desde el destino (end_word). En cada iteración, se expande siempre el conjunto con menor cantidad de nodos activos, reduciendo el radio de búsqueda de profundidad D a dos conos de radio D/2.
• (c) Cómo funciona en Rust (memoria y tipos): Mantiene dos HashSet<String> (forward_set y backward_set) y realiza un intercambio de referencias eficiente con std::mem::swap para expandir la frontera menor sin copiar elementos.
• (d) Error típico de Junior: Expandir siempre la misma frontera sin comparar cardinalidades; si una frontera tiene 5 nodos y la otra 5,000, expandir la grande causa una explosión combinatoria inmediata de memoria.

Relajación Acotada por Capas (Bellman-Ford Acotado)#

• (a) En palabras simples (intuición): Un juego donde tienes un cupo de exactamente 2 fichas de transporte. En el turno 1 solo puedes comprar billetes que requieran 1 ficha. En el turno 2 puedes usar rutas que requieran hasta 2 fichas, pero tienes prohibido encadenar 3 billetes en un mismo turno usando información futura.
• (b) Definición técnica paso a paso: Modificación del algoritmo clásico de Bellman-Ford donde se ejecutan exactamente K + 1 iteraciones (correspondientes a un límite de K escalas = K + 1 vuelos). En cada ronda se clona el vector de distancias (temp_prices = prices.clone()), garantizando que la ronda r solo explore caminos de longitud máxima r aristas.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con prices: Vec<u64> y temp_prices: Vec<u64>. La aritmética saturada saturating_add previene pánicos por desbordamiento de enteros.
• (d) Error típico de Junior: Mutar directamente prices dentro del bucle de aristas; una sola arista u -> v relajada puede desencadenar la relajación de v -> w en la misma ronda, consumiendo dos escalas en una sola pasada.

Poda de Dominancia de Estados en Dijkstra#

• (a) En palabras simples (intuición): Si llegas a una estación de tren gastando 100 dólares y usando 3 escalas, pero un amigo te llama diciendo que llegó a esa misma estación gastando 80 dólares y usando solo 2 escalas, tu ruta está totalmente derrotada: es más cara y gastó más escalas. Abandonas tu camino de inmediato.
• (b) Definición técnica paso a paso: Criterio de poda en búsqueda de costo mínimo donde el estado está parametrizado por una tupla (costo, paradas, nodo). Un estado es podado si existe otro estado previamente explorado que alcanzó el mismo nodo con menor o igual costo y menor o igual número de escalas.
• (c) Cómo funciona en Rust (memoria y tipos): Se mantiene un vector best_stops: Vec<usize> que almacena el menor número de paradas observado para cada nodo en el Min-Heap.
• (d) Error típico de Junior: Aplicar la regla de Dijkstra estándar y no volver a evaluar un nodo si su costo es mayor; un camino con mayor costo pero menos escalas puede ser la única forma válida de alcanzar la meta cuando las escalas se agotan.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Reducción Exponencial en BFS Bidireccional#

Sea B el factor de ramificación promedio (número de vecinos válidos por cada palabra) y sea D la distancia mínima en saltos entre begin_word y end_word.

1. BFS Unidireccional Estándar: El árbol de búsqueda se expande desde el origen hasta alcanzar la profundidad D. El número total de nodos evaluados en el peor caso es la suma de los niveles:
   N_{uni} = 1 + B + B² + … + B^D ≈ O(B^D)
   Si B = 10 y la distancia es D = 6:
   N_{uni} ≈ 10⁶ = 1,000,000 estados visitados

1. BFS Bidireccional: Ambas fronteras avanzan simultáneamente desde extremos opuestos. El encuentro ocurre en la mitad del camino, a una profundidad aproximada de D / 2:
   N_{bidi} ≈ 2 × B^{D / 2} = mathbf{O(2 · B^{D / 2})}
   Para los mismos valores (B = 10, D = 6):
   N_{bidi} ≈ 2 × 10³ = 2,000 estados visitados

¡Una reducción astronómica de 500 veces menos trabajo de CPU y memoria física!

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Diagramas de Arquitectura#

• Gráfico SVG vectorial: ![Visualización del Día 33 y Memoria en Rust](../diagrams/sesiones/dia_33.svg)
• Código fuente del diagrama: Fuente Mermaid

Encuentro de Fronteras en BFS Bidireccional#

flowchart LR
    subgraph Adelante ["Frontera Adelante (begin_word)"]
        W1["hit"] --> W2["hot"]
    end
    subgraph Atrás ["Frontera Atrás (end_word)"]
        W5["cog"] --> W4["dog / log"]
    end
    W2 -->|Sustitución en O(26*M)| COL["dot / lot"]
    W4 -->|Colisión detectada!| COL

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Ejecución de Bellman-Ford acotado con k=1, src=0, dst=3: Vuelos: (0, 1, 100), (1, 2, 100), (1, 3, 600), (2, 3, 200)

STACK                                            HEAP
+-------------------------------+               +--------------------------------------+
| Frame find_cheapest_price     |               | prices: Vec<u64>                     |
|   n: 4, src: 0, dst: 3, k: 1  |               | [ 0, inf, inf, inf ]                 |
|   prices: Vec<u64> -----------+-------------->+--------------------------------------+
|   temp_prices: Vec<u64> ------+-------------->| temp_prices: Vec<u64>                |
+-------------------------------+               | [ 0, inf, inf, inf ]                 |
                                                +--------------------------------------+

Ronda 1 (Vuelo 1 de 2 permitidos):
- Arista (0, 1, 100): prices[0] = 0 -> temp_prices[1] = 0 + 100 = 100.
- Arista (1, 2, 100): prices[1] = inf -> NO se relaja en esta ronda (evita mutación en cadena!).
- Arista (1, 3, 600): prices[1] = inf -> NO se relaja.
Fin de Ronda 1: prices pasa a ser [ 0, 100, inf, inf ].

Ronda 2 (Vuelo 2 de 2 permitidos):
- Arista (0, 1, 100): no mejora (100 ya establecido).
- Arista (1, 2, 100): prices[1] = 100 -> temp_prices[2] = 100 + 100 = 200.
- Arista (1, 3, 600): prices[1] = 100 -> temp_prices[3] = 100 + 600 = 700.
- Arista (2, 3, 200): prices[2] = inf en prices base -> NO se relaja.
Fin de Ronda 2: prices pasa a ser [ 0, 100, 200, 700 ].

Finaliza el bucle (rondas = k + 1 = 2).
Resultado retornado para nodo 3: 700.

4. Las 3 Trampas Clásicas en Entrevistas#

1. La Trampa de la Mutación en Cadena en Bellman-Ford: - Olvidar clonar el arreglo de distancias al inicio de cada ronda de escalas. Si relajas aristas directamente sobre el arreglo activo, un camino de 4 aristas puede relajarse de golpe en una sola iteración, violando la restricción de escalas K.
2. Ciclos Infinitos por No Podar Estados Visitados en Grafos Implícitos: - En Word Ladder, si no eliminas las palabras ya visitadas de word_set o no las registras en visited, la búsqueda rebotará indefinidamente ("hit" -> "hot" -> "hit"), saturando el Call Stack o la memoria Heap.
3. Manejo Incorrecto de Centinelas Inalcanzables: - En LeetCode 787, si el destino no es alcanzable dentro de las K escalas, se debe retornar -1 (en Rust None). En LeetCode 127, si no hay secuencia, se retorna 0.

5. Implementación Canónica en Rust + Comparativa con Python#

Implementación Canónica en Rust (practica-rust/dia_33.rs)#

//! Día 33: Refuerzo y Evaluación de Grafos, BFS & Dijkstra en Rust.
use std::collections::HashSet;

/// LeetCode 127: BFS Bidireccional con sustitución de 26 caracteres en O(M * 26 * N^(1/2)).
pub fn ladder_length(begin_word: &str, end_word: &str, word_list: &[&str]) -> usize {
    if begin_word.len() != end_word.len() {
        return 0;
    }

    let mut word_set: HashSet<&str> = word_list.iter().copied().collect();
    if !word_set.contains(end_word) {
        return 0;
    }
    if begin_word == end_word {
        return 1;
    }

    let mut forward_set: HashSet<String> = HashSet::new();
    let mut backward_set: HashSet<String> = HashSet::new();

    forward_set.insert(begin_word.to_string());
    backward_set.insert(end_word.to_string());
    word_set.remove(begin_word);
    word_set.remove(end_word);

    let mut steps = 1;

    while !forward_set.is_empty() && !backward_set.is_empty() {
        if forward_set.len() > backward_set.len() {
            std::mem::swap(&mut forward_set, &mut backward_set);
        }

        let mut next_frontier: HashSet<String> = HashSet::new();

        for word in forward_set.iter() {
            let mut chars: Vec<char> = word.chars().collect();
            for i in 0..chars.len() {
                let original_char = chars[i];
                for c in b'a'..=b'z' {
                    let candidate_char = c as char;
                    if candidate_char == original_char {
                        continue;
                    }
                    chars[i] = candidate_char;
                    let candidate: String = chars.iter().collect();

                    if backward_set.contains(&candidate) {
                        return steps + 1;
                    }

                    if word_set.remove(candidate.as_str()) {
                        next_frontier.insert(candidate);
                    }
                }
                chars[i] = original_char;
            }
        }

        forward_set = next_frontier;
        steps += 1;
    }

    0
}

/// LeetCode 787: Bellman-Ford acotado por K+1 escalas en O((K+1) * E) y O(V) espacio.
pub fn find_cheapest_price_bellman_ford(
    n: usize,
    flights: &[(usize, usize, u64)],
    src: usize,
    dst: usize,
    k: usize,
) -> Option<u64> {
    if src >= n || dst >= n {
        return None;
    }

    let mut prices = vec![u64::MAX; n];
    prices[src] = 0;

    for _ in 0..=k {
        let mut temp_prices = prices.clone();
        let mut updated = false;

        for &(u, v, cost) in flights {
            if prices[u] != u64::MAX {
                let new_cost = prices[u].saturating_add(cost);
                if new_cost < temp_prices[v] {
                    temp_prices[v] = new_cost;
                    updated = true;
                }
            }
        }

        prices = temp_prices;
        if !updated {
            break;
        }
    }

    if prices[dst] == u64::MAX {
        None
    } else {
        Some(prices[dst])
    }
}

Implementación Canónica en Python (practica/dia_33_graphs_word_ladder_cheapest_flights.py)#

from collections import defaultdict
from typing import Dict, List, Set

def ladder_length(begin_word: str, end_word: str, word_list: List[str]) -> int:
    """LC 127: BFS Bidireccional con patrones comodín en O(M^2 * N)."""
    word_set = set(word_list)
    if end_word not in word_set:
        return 0

    m = len(begin_word)
    pattern_map: Dict[str, List[str]] = defaultdict(list)
    for word in word_set:
        for i in range(m):
            pattern = word[:i] + "*" + word[i + 1:]
            pattern_map[pattern].append(word)

    forward_set: Set[str] = {begin_word}
    backward_set: Set[str] = {end_word}
    visited: Set[str] = {begin_word, end_word}
    steps = 1

    while forward_set and backward_set:
        if len(forward_set) > len(backward_set):
            forward_set, backward_set = backward_set, forward_set

        next_frontier: Set[str] = set()
        for word in forward_set:
            for i in range(m):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbor in pattern_map.get(pattern, []):
                    if neighbor in backward_set:
                        return steps + 1
                    if neighbor not in visited:
                        visited.add(neighbor)
                        next_frontier.add(neighbor)

        forward_set = next_frontier
        steps += 1

    return 0

def find_cheapest_price_bellman_ford(
    n: int, flights: List[List[int]], src: int, dst: int, k: int
) -> int:
    """LC 787: Bellman-Ford acotado por K+1 escalas en O((K+1) * E) y O(V) espacio."""
    prices = [float("inf")] * n
    prices[src] = 0.0

    for _ in range(k + 1):
        temp_prices = list(prices)
        updated = False
        for u, v, cost in flights:
            if prices[u] != float("inf"):
                if prices[u] + cost < temp_prices[v]:
                    temp_prices[v] = prices[u] + cost
                    updated = True
        prices = temp_prices
        if not updated:
            break

    return int(prices[dst]) if prices[dst] != float("inf") else -1

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Puente a LeetCode y Práctica de Código#

1. LeetCode 127 — Word Ladder (Hard): - Resuelve el problema aplicando BFS bidireccional.
2. LeetCode 787 — Cheapest Flights Within K Stops (Medium): - Implementa Bellman-Ford acotado y contrástalo con Dijkstra modificado.
3. LeetCode 126 — Word Ladder II (Hard): - Extensión suprema: BFS para calcular distancias mínimas y Backtracking para reconstruir todas las rutas óptimas.
4. LeetCode 743 — Network Delay Time (Medium): - Práctica complementaria de Dijkstra estándar sin límite de escalas.

8. Tarea en Papel para Hoy#

Toma una hoja y realiza a mano la traza completa:

1. Dibuja el grafo de vuelos: 0 -> 1 (\100), CODE1 (100), 0 -> 2 (\$500), con src=0, dst=2.
2. Ejecuta la traza de Bellman-Ford para k=0 y luego para k=1.
3. Verifica cómo para k=0 el costo es \$500 (solo 1 vuelo permitido) y para k=1 se reduce a \$200 (2 vuelos permitidos).

Navegación:

• ← Volver a Sesión 32: Evaluación — Árboles Binarios y BST
• Avanzar a Sesión 34: Simulacro de Entrevista FAANG Onsite Completo →