Sesión 22: Grokking Algorithms (Capítulo 6) y CTCI 4.1 — Grafos, BFS y Ruta entre Nodos#

Navegación rápida:

• ← Sesión 21: Patrón Monotonic Stack y Consolidación Semana 3
• Sesión 23: CTCI Ch4 — Árboles, Recorridos y Minimal Tree →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 60-75 minutos.
• Código fuente compilado y probado: practica-rust/dia_22.rs

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

Iniciamos la Semana 4 entrando a la estructura no lineal más universal del cómputo: los Grafos. Consulta el Glosario Maestro y la Guía de Diagramas.

Grafo Dirigido vs No Dirigido (G = (V, E))#

• (a) En palabras simples (intuición): Una red de amigos o calles. En Instagram o Twitter (grafo dirigido), tú puedes seguir a una celebridad sin que ella te siga a ti (la flecha va en un solo sentido). En Facebook o WhatsApp (grafo no dirigido), si son amigos, la conexión es mutua en ambos sentidos.
• (b) Definición técnica paso a paso: Estructura matemática G = (V, E) donde V es un conjunto de vértices (nodos) y E es un conjunto de aristas (pares de vértices). En un grafo dirigido, los pares son ordenados (u, v) donde u → v. En un grafo no dirigido, los pares son no ordenados {u, v}, permitiendo tránsito bidireccional simétrico.
• (c) Cómo funciona en Rust (memoria y tipos): Se representa mediante una estructura con lista de adyacencia Vec<Vec<usize>>. Si es no dirigido, cada arista se inserta en ambas direcciones: adj[u].push(v) y adj[v].push(u).
• (d) Error típico de Junior: Asumir que toda arista puede recorrerse en ambos sentidos, ignorando la dirección de las flechas en problemas de rutas.

Lista de Adyacencia (Vec<Vec<usize>>) vs Matriz de Adyacencia#

• (a) En palabras simples (intuición): La libreta de contactos de tu teléfono vs una cuadrícula gigante donde pones una 'X' si conoces a cada habitante de tu ciudad. En tu teléfono solo guardas a tus 50 amigos reales; la cuadrícula tendría millones de casillas vacías desperdiciadas.
• (b) Definición técnica paso a paso:
• Lista de Adyacencia: Arreglo de tamaño |V| donde cada índice almacena una lista dinámica con los vecinos directos de ese nodo. Ocupa memoria proporcional a O(V + E), siendo la representación óptima para grafos dispersos (sparse graphs).
• Matriz de Adyacencia: Matriz bidimensional |V| × |V| donde matrix[u][v] = 1 si existe arista. Consume memoria O(V²), ineficiente si el grafo tiene pocas aristas por nodo.
• (c) Cómo funciona en Rust (memoria y tipos): En Rust puro, indexar vértices como enteros usize en un Vec<Vec<usize>> evita la sobrecarga de punteros crudos o tipos con vidas complejas.
• (d) Error típico de Junior: Crear una matriz de 100,000 × 100,000 enteros, provocando un desbordamiento inmediato de memoria física (requiere ~40 GB de RAM).

Breadth-First Search (BFS - Búsqueda en Anchura)#

• (a) En palabras simples (intuición): Arrojar una piedra en un lago en calma. Las olas se expanden en círculos concéntricos: primero tocan lo que está a 1 metro, luego lo que está a 2 metros, luego a 3 metros.
• (b) Definición técnica paso a paso: Algoritmo de recorrido de grafos que explora todos los vértices a distancia d del origen antes de visitar cualquier vértice a distancia d + 1. Utiliza una Cola FIFO para procesar los nodos en estricto orden de descubrimiento.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa con std::collections::VecDeque<usize>, aprovechando su anillo circular para extraer del frente con pop_front() en O(1) estricto.
• (d) Error típico de Junior: Usar DFS (Depth-First Search) para buscar el camino más corto en un grafo no ponderado; DFS se interna en ramas profundas y casi nunca halla la ruta con menor número de aristas.

Conjunto de Visitados (Vec<bool> / HashSet) y Prevención de Ciclos#

• (a) En palabras simples (intuición): Dejar una marca de tiza en cada puerta que ya cruzaste en un laberinto para no caminar en círculos infinitos como un perro persiguiéndose la cola.
• (b) Definición técnica paso a paso: Estructura de datos auxiliar que registra los identificadores de los nodos que ya han sido descubiertos o encolados. Impide que aristas dirigidas hacia nodos previos re-procesen el grafo en bucles infinitos.
• (c) Cómo funciona en Rust (memoria y tipos): Si los nodos son contiguos 0..V, un vector booleano vec![false; num_vertices] en el Heap es infinitamente más rápido que un HashSet, ya que el procesador consulta el índice en 1 ciclo de CPU sin calcular funciones hash.
• (d) Error típico de Junior: Marcar el nodo como visitado al desencolarlo (pop_front) en lugar de marcarlo al encolarlo (push_back), lo que provoca que nodos vecinos introduzcan duplicados masivos en la cola.

Reconstrucción de Ruta por Predecesores (parent: Vec<Option<usize>>)#

• (a) En palabras simples (intuición): El hilo de Ariadna en el mito del Minotauro. Al entrar a cada nueva habitación del laberinto, anotas de qué habitación venías. Cuando llegas a la salida, caminas hacia atrás leyendo las notas para trazar el mapa completo.
• (b) Definición técnica paso a paso: Arreglo unidimensional de tamaño |V| donde cada posición parent[v] almacena el nodo u desde el cual se descubrió a v por primera vez. Una vez alcanzado el nodo objetivo, se reconstruye la ruta óptima navegando hacia atrás hasta el nodo de inicio y luego invirtiendo la lista.
• (c) Cómo funciona en Rust (memoria y tipos): Inicializado como vec![None; num_vertices]. Al descubrir neighbor, se asigna parent[neighbor] = Some(curr).
• (d) Error típico de Junior: Guardar la ruta completa acumulada como un vector dentro de cada elemento de la cola, multiplicando el consumo de memoria por un factor de O(V²).

Búsqueda Bidireccional (Bidirectional BFS)#

• (a) En palabras simples (intuición): Cavar un túnel subterráneo empezando simultáneamente desde ambos extremos de la montaña. Los dos equipos se encontrarán en el centro en la mitad del tiempo que si un solo equipo excavara toda la montaña.
• (b) Definición técnica paso a paso: Técnica de optimización que ejecuta dos búsquedas en anchura concurrentes: una hacia adelante desde el origen y otra hacia atrás desde el destino. La búsqueda termina con éxito en el instante en que los dos frentes de onda colisionan en un nodo compartido.
• (c) Cómo funciona en Rust (memoria y tipos): Dos conjuntos HashSet<usize> y dos VecDeque<usize>, expandiendo alternadamente el frente que contenga menor cantidad de elementos en su capa activa.
• (d) Error típico de Junior: Asumir que la búsqueda bidireccional requiere hilos paralelos de hardware; se ejecuta de forma determinista y secuencial en un solo hilo alternando niveles.

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

La Matemática de la Cola FIFO y el Camino Más Corto#

¿Por qué BFS garantiza matemáticamente que el primer camino encontrado hacia un nodo destino T tiene el menor número posible de aristas en un grafo no ponderado? Demostrémoslo por inducción sobre la distancia d:

1. Definición de capas: Sea Lₖ el conjunto de todos los nodos cuya distancia mínima en aristas desde el origen S es exactamente k. - L₀ = { S } - L₁ = { vecinos directos de S } - Lₖ = { v ∉ bigcup_{i=0}ᵏ⁻¹ Lᵢ mid ∃ u ∈ L_{k-1} con (u, v) ∈ E }
2. Propiedad de la Cola FIFO: - Los nodos de L₀ se procesan primero. Al procesar L₀, todos sus vecinos no visitados entran a la cola: estos constituyen exactamente L₁. - Ningún nodo de L₂ puede entrar a la cola antes de que todos los nodos de L₁ hayan sido encolados. - Por la propiedad LIFO/FIFO estricta de la cola, todos los nodos de la capa Lₖ se desencolan antes que cualquier nodo de la capa L_{k+1}.
3. Conclusión: Si el destino T pertenece a la capa L_m, el algoritmo visitará T durante el procesamiento de la capa m. Es físicamente imposible que un camino más largo (que pertenecería a L_{m+1} o superior) sea explorado antes.

Demostración de Complejidad Temporal: O(V + E)#

• Vértices: Gracias al vector visited, cada vértice entra a la cola FIFO a lo sumo una sola vez y se desencola a lo sumo una sola vez:

• Aristas: Cuando un nodo u es extraído de la cola, el algoritmo itera sobre su lista de adyacencia adj[u]. Cada arista saliente se examina exactamente una vez (en grafos dirigidos) o dos veces (en no dirigidos):

• Costo total: Sumando ambos componentes independientes:

• Espacio Auxiliar: La cola aloja a lo sumo V elementos y el vector de visitados consume V booleanos ⟹ O(V) espacio.

La Ventaja Geométrica de la Búsqueda Bidireccional#

Sea b el factor de ramificación promedio (número de vecinos por nodo) y d la distancia mínima entre origen y destino:

• BFS Unidireccional: Debe explorar un árbol de radio completo d:

• BFS Bidireccional: Ambos frentes se expanden solo hasta la mitad de la distancia (d/2):

• Ejemplo numérico real: Si b = 10 y d = 6:
• BFS Unidireccional: 10⁶ = 1,000,000 nodos.
• BFS Bidireccional: 2 × 10³ = 2,000 nodos.

¡Una reducción de cómputo del 99.8%!

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 22 y Memoria en Rust](../diagrams/sesiones/dia_22.svg)
• Código fuente del diagrama: Fuente Mermaid

Expansión de Capas BFS y Reconstrucción#

flowchart LR
    subgraph G["Grafo Dirigido con Ciclos"]
        N0["(0) Origen"] --> N1["(1)"]
        N0 --> N2["(2)"]
        N1 --> N3["(3)"]
        N2 --> N3
        N3 --> N4["(4) Destino"]
        N3 --> N1
    end
    subgraph BFS["Frente de Onda FIFO"]
        L0["Capa 0: [0]"] --> L1["Capa 1: [1, 2]"]
        L1 --> L2["Capa 2: [3]"]
        L2 --> L3["Capa 3: [4] ¡Meta!"]
    end

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

Grafo de 5 nodos implementado con Vec<Vec<usize>>:

STACK                                            HEAP
+-------------------------------+               +-------------------------------------------+
| Graph                         |               | adj: Vec<Vec<usize>>                      |
|   num_vertices: 5             |               | [0] -> [ 1, 2 ]                           |
|   directed: true              |               | [1] -> [ 3 ]                              |
|   adj: Vec<Vec<usize>> -------+-------------->| [2] -> [ 3 ]                              |
+-------------------------------+               | [3] -> [ 4, 1 ]                           |
                                                | [4] -> [ ]                                |
                                                +-------------------------------------------+
Llamada a bfs_shortest_path(&g, 0, 4):
Stack Frame BFS:
- visited: vec![false; 5]  -> Heap: [ true, false, false, false, false ] (marca inicio 0)
- parent:  vec![None; 5]   -> Heap: [ None, None, None, None, None ]
- queue:   VecDeque<usize> -> Heap: [ 0 ]

Iteración 1: pop_front() extrae 0.
Vecinos de 0: [ 1, 2 ].
- Vecino 1: visited[1] = true, parent[1] = Some(0), queue.push(1)
- Vecino 2: visited[2] = true, parent[2] = Some(0), queue.push(2)
Estado Queue: [ 1, 2 ]

Iteración 2: pop_front() extrae 1.
Vecinos de 1: [ 3 ].
- Vecino 3: visited[3] = true, parent[3] = Some(1), queue.push(3)
Estado Queue: [ 2, 3 ]

Iteración 3: pop_front() extrae 2.
Vecinos de 2: [ 3 ]. visited[3] ya es true -> Se ignora (evita colisión redundante).
Estado Queue: [ 3 ]

Iteración 4: pop_front() extrae 3.
Vecinos de 3: [ 4, 1 ].
- Vecino 4: visited[4] = true, parent[4] = Some(3). ¡Es el destino 4! -> Búsqueda termina.

Reconstrucción de ruta mediante parent:
4 -> parent[4]=Some(3) -> parent[3]=Some(1) -> parent[1]=Some(0) -> parent[0]=None
Ruta invertida: [ 0, 1, 3, 4 ]. Longitud mínima: 3 aristas.

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

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

//! Día 22: Grafos, BFS y Route Between Nodes (CTCI 4.1, Grokking Ch6) en Rust.
//! Compilable y verificable con `rustc --test`.

use std::collections::{HashSet, VecDeque};

#[derive(Debug, Clone)]
pub struct Graph {
    num_vertices: usize,
    adj: Vec<Vec<usize>>,
    directed: bool,
}

impl Graph {
    pub fn new(num_vertices: usize, directed: bool) -> Self {
        Self {
            num_vertices,
            adj: vec![Vec::new(); num_vertices],
            directed,
        }
    }

    pub fn num_vertices(&self) -> usize { self.num_vertices }

    pub fn add_edge(&mut self, u: usize, v: usize) {
        assert!(u < self.num_vertices && v < self.num_vertices);
        self.adj[u].push(v);
        if !self.directed {
            self.adj[v].push(u);
        }
    }

    pub fn neighbors(&self, u: usize) -> &[usize] {
        &self.adj[u]
    }
}

/// CTCI 4.1: Determina si existe una ruta entre dos nodos en O(V + E).
pub fn has_route_between_nodes(graph: &Graph, start: usize, target: usize) -> bool {
    if start >= graph.num_vertices() || target >= graph.num_vertices() { return false; }
    if start == target { return true; }

    let mut visited = vec![false; graph.num_vertices()];
    let mut queue = VecDeque::new();

    visited[start] = true;
    queue.push_back(start);

    while let Some(curr) = queue.pop_front() {
        if curr == target { return true; }

        for &neighbor in graph.neighbors(curr) {
            if !visited[neighbor] {
                if neighbor == target { return true; }
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }
    false
}

/// BFS para encontrar el camino más corto en aristas y reconstruirlo.
pub fn bfs_shortest_path(graph: &Graph, start: usize, target: usize) -> Option<Vec<usize>> {
    if start >= graph.num_vertices() || target >= graph.num_vertices() { return None; }
    if start == target { return Some(vec![start]); }

    let mut visited = vec![false; graph.num_vertices()];
    let mut parent = vec![None; graph.num_vertices()];
    let mut queue = VecDeque::new();

    visited[start] = true;
    queue.push_back(start);

    let mut found = false;
    while let Some(curr) = queue.pop_front() {
        if curr == target { found = true; break; }

        for &neighbor in graph.neighbors(curr) {
            if !visited[neighbor] {
                visited[neighbor] = true;
                parent[neighbor] = Some(curr);
                queue.push_back(neighbor);
                if neighbor == target { found = true; break; }
            }
        }
        if found { break; }
    }

    if !found { return None; }

    let mut path = Vec::new();
    let mut curr = Some(target);
    while let Some(node) = curr {
        path.push(node);
        if node == start { break; }
        curr = parent[node];
    }
    path.reverse();
    Some(path)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_route_and_shortest_path() {
        let mut g = Graph::new(5, true);
        g.add_edge(0, 1);
        g.add_edge(0, 2);
        g.add_edge(1, 3);
        g.add_edge(2, 3);
        g.add_edge(3, 4);

        assert!(has_route_between_nodes(&g, 0, 4));
        assert!(!has_route_between_nodes(&g, 4, 0));

        let path = bfs_shortest_path(&g, 0, 4).unwrap();
        assert_eq!(path.len(), 4);
        assert_eq!(path[0], 0);
        assert_eq!(path[3], 4);
    }
}

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

from collections import deque
from typing import Dict, List, Optional, Set

class Graph:
    def __init__(self, directed: bool = True) -> None:
        self.directed = directed
        self.adj: Dict[int, List[int]] = {}

    def add_edge(self, u: int, v: int) -> None:
        if u not in self.adj: self.adj[u] = []
        if v not in self.adj: self.adj[v] = []
        self.adj[u].append(v)
        if not self.directed:
            self.adj[v].append(u)

def has_route_between_nodes(graph: Graph, start: int, target: int) -> bool:
    if start not in graph.adj or target not in graph.adj:
        return False
    if start == target:
        return True

    queue: deque[int] = deque([start])
    visited: Set[int] = {start}

    while queue:
        curr = queue.popleft()
        if curr == target:
            return True

        for neighbor in graph.adj.get(curr, []):
            if neighbor not in visited:
                if neighbor == target:
                    return True
                visited.add(neighbor)
                queue.append(neighbor)

    return False

5. Las 3 Trampas Clásicas en Entrevistas#

1. Olvidar el Conjunto visited (El Bucle Infinito Mortal): - A diferencia de los árboles binarios, los grafos suelen tener ciclos cerrados (A → B → C → A). Sin visited, el programa entrará en un ciclo infinito saturando la memoria RAM y detonando un Out of Memory o Time Limit Exceeded.
2. Marcar como Visitado al Desencolar en Lugar de al Encolar: - Si marcas visited[curr] = true tras hacer pop_front(), múltiples nodos vecinos en la misma capa podrán ver al nodo objetivo como no visitado y encolarlo decenas de veces. La cola explota a tamaño cuadrático O(V²). Marca siempre al momento exacto de hacer push_back.
3. Usar DFS para Buscar el Camino Más Corto: - DFS se sumerge hasta la máxima profundidad antes de retroceder. Encontrará una ruta si existe, pero casi con total seguridad no será la de menor longitud de aristas. Para distancia mínima sin ponderar, BFS es la única solución correcta.

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

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

1. LeetCode 797 — All Paths From Source to Target (Medium): - Recorrido completo en Grafos Dirigidos Acíclicos (DAG).
2. LeetCode 127 — Word Ladder (Hard): - El ejercicio maestro de BFS y BFS Bidireccional para encontrar la secuencia de transformación más corta.
3. LeetCode 200 — Number of Islands (Medium): - Modelado de matrices 2D como grafos no dirigidos implícitos mediante BFS/DFS de componentes conexas.

8. Tarea en Papel para Hoy#

Dibuja en papel un grafo dirigido de 6 nodos ($0$ al $5$) con las siguientes aristas: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3, 3 -> 4, 4 -> 1 (ciclo hacia atrás), 2 -> 5.

1. Traza a mano la ejecución completa de BFS para encontrar el camino más corto de 0 a 4.
2. Dibuja el estado de la cola queue, el arreglo visited y el vector parent en cada paso.
3. Demuestra cómo el ciclo 4 -> 1 es neutralizado con éxito por la marca de visitado.

Navegación:

• ← Volver a Sesión 21: Patrón Monotonic Stack y Consolidación Semana 3
• Avanzar a Sesión 23: CTCI Ch4 — Árboles, Recorridos y Minimal Tree →