Grafos y búsqueda

📐 Fundamento

Un grafo es un par $G = (V, E)$ donde:

• $V$ es un conjunto de vértices (nodos).
• $E \subseteq V \times V$ es un conjunto de aristas (edges).

Tipos:

Términos clave:

• Grado de un vértice: número de aristas incidentes. En digrafos, se separa en in-degree y out-degree.
• Camino: secuencia de vértices conectados por aristas, sin repetir.
• Ciclo: camino que empieza y termina en el mismo vértice.
• Conectado (no dirigido): existe camino entre cualquier par de vértices.
• Fuertemente conectado (dirigido): existe camino dirigido entre cualquier par.
• Componente conexo: subgrafo maximal conectado.

Tamaño: se denota por $|V| = n$ (número de vértices) y $|E| = m$ (número de aristas). En análisis de complejidad vamos a hablar de $O(V + E)$ o $O(V^2)$ — no son lo mismo.

📐 Fundamento

Hay dos representaciones canónicas. Elegir la correcta cambia la complejidad de tus algoritmos.

Lista de adyacencia (la default)

Cada vértice tiene una lista de sus vecinos.

# Grafo no dirigido, no ponderado
grafo = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}

# Grafo dirigido, ponderado: peso almacenado como tupla
grafo = {
    'A': [('B', 4), ('C', 2)],
    'B': [('D', 5)],
    'C': [('B', 1), ('D', 8)],
    'D': [],
}

• Espacio: $O(V + E)$.
• Iterar vecinos de $v$: $O(\text{deg}(v))$.
• ¿Existe arista $(u, v)$?: $O(\text{deg}(u))$.
• Mejor cuando: $E \ll V^2$ (grafo disperso — la mayoría de los grafos reales).

Matriz de adyacencia

Una matriz $n \times n$ donde $M[i][j] = 1$ si hay arista de $i$ a $j$ (o el peso si es ponderado).

# 4 vértices: A=0, B=1, C=2, D=3
matriz = [
    [0, 1, 1, 0],   # A: conectado a B, C
    [1, 0, 0, 1],   # B: conectado a A, D
    [1, 0, 0, 1],   # C: conectado a A, D
    [0, 1, 1, 0],   # D: conectado a B, C
]

• Espacio: $O(V^2)$.
• ¿Existe arista $(u, v)$?: $O(1)$.
• Iterar vecinos de $v$: $O(V)$.
• Mejor cuando: $E \approx V^2$ (grafo denso) o necesitás chequear adyacencia constantemente.

¿Cuál usás?

• Por default, lista de adyacencia. La mayoría de los grafos reales son dispersos. Internet tiene billones de vértices y un promedio de ~10 aristas por vértice.
• Matriz solo si: (a) el grafo es chico (< 1000 vértices) y denso, o (b) el algoritmo requiere chequeo de adyacencia $O(1)$ muchas veces (p. ej. Floyd-Warshall).

📐 Fundamento

Idea: usar una cola (FIFO) de vértices "por visitar".

from collections import deque

def bfs(grafo, inicio):
    """Recorre todos los nodos alcanzables desde 'inicio'."""
    visitados = {inicio}
    cola = deque([inicio])
    orden = []

    while cola:
        v = cola.popleft()      # FIFO: el primero que entró
        orden.append(v)

        for vecino in grafo[v]:
            if vecino not in visitados:
                visitados.add(vecino)
                cola.append(vecino)

    return orden

Complejidad: $O(V + E)$ — cada vértice se encola una sola vez, cada arista se examina una sola vez.

BFS para camino más corto (sin pesos)

def camino_mas_corto_bfs(grafo, inicio, destino):
    """Devuelve el camino más corto en aristas, o None si no existe."""
    if inicio == destino:
        return [inicio]
    visitados = {inicio}
    cola = deque([(inicio, [inicio])])     # (nodo_actual, camino_para_llegar)

    while cola:
        v, camino = cola.popleft()
        for vecino in grafo[v]:
            if vecino == destino:
                return camino + [vecino]
            if vecino not in visitados:
                visitados.add(vecino)
                cola.append((vecino, camino + [vecino]))
    return None     # no hay camino

Por qué BFS encuentra el más corto sin pesos: explora vértices a distancia $k$ antes que vértices a distancia $k+1$. La primera vez que toca el destino, es por el camino más corto.

Casos de uso reales:

• Distancia social en redes (¿cuántos saltos entre vos y otra persona?).
• Web crawler que va capa por capa desde una URL semilla.
• "Resolvé el laberinto en menos pasos".
• Validar bipartición de un grafo.

📐 Fundamento

Idea: usar una pila (LIFO) — o más natural, recursión.

def dfs_recursivo(grafo, inicio, visitados=None, orden=None):
    if visitados is None:
        visitados = set()
        orden = []
    visitados.add(inicio)
    orden.append(inicio)
    for vecino in grafo[inicio]:
        if vecino not in visitados:
            dfs_recursivo(grafo, vecino, visitados, orden)
    return orden


def dfs_iterativo(grafo, inicio):
    visitados = set()
    pila = [inicio]
    orden = []
    while pila:
        v = pila.pop()              # LIFO: el último que entró
        if v in visitados:
            continue
        visitados.add(v)
        orden.append(v)
        for vecino in grafo[v]:
            if vecino not in visitados:
                pila.append(vecino)
    return orden

Complejidad: $O(V + E)$ igual que BFS.

Casos de uso reales:

• Detección de ciclos.
• Orden topológico (DFS post-order invertido).
• Componentes conexos / fuertemente conexos (Kosaraju, Tarjan).
• Resolución de laberintos / puzzles donde "todos los caminos importan, no el más corto".
• Generadores de mazos / niveles en videojuegos.

📐 Fundamento

Cuando las aristas tienen peso positivo distinto, BFS no sirve: una ruta con más saltos puede ser más barata. Dijkstra generaliza BFS reemplazando la cola FIFO por una cola de prioridad (min-heap) por costo acumulado.

import heapq

def dijkstra(grafo, inicio):
    """grafo: dict[nodo, list[(vecino, peso)]]
    Devuelve dict[nodo, distancia_minima_desde_inicio]."""
    distancias = {v: float('inf') for v in grafo}
    distancias[inicio] = 0
    heap = [(0, inicio)]                  # (distancia_acumulada, nodo)

    while heap:
        d, v = heapq.heappop(heap)
        if d > distancias[v]:
            continue                      # entrada obsoleta
        for vecino, peso in grafo[v]:
            nueva = d + peso
            if nueva < distancias[vecino]:
                distancias[vecino] = nueva
                heapq.heappush(heap, (nueva, vecino))

    return distancias

Complejidad: $O((V + E) \log V)$ con heap binario; $O(V \log V + E)$ con Fibonacci heap (raro en práctica).

Restricción crítica: pesos no negativos. Con pesos negativos usás Bellman-Ford ($O(VE)$).

Casos de uso reales:

• GPS y navegadores (Google Maps, Waze).
• Routing de paquetes en redes (OSPF).
• Costo mínimo en un juego (PathFinding).
• "Camino más rápido / más barato" en cualquier dominio.

📐 Fundamento

Algoritmo de Kahn (basado en in-degree):

def orden_topologico(grafo):
    """grafo: dict[nodo, list[nodo]] (dirigido)."""
    in_deg = {v: 0 for v in grafo}
    for v in grafo:
        for w in grafo[v]:
            in_deg[w] = in_deg.get(w, 0) + 1

    cola = deque([v for v, d in in_deg.items() if d == 0])
    orden = []

    while cola:
        v = cola.popleft()
        orden.append(v)
        for vecino in grafo[v]:
            in_deg[vecino] -= 1
            if in_deg[vecino] == 0:
                cola.append(vecino)

    if len(orden) != len(grafo):
        raise ValueError("El grafo tiene un ciclo — no hay orden topológico.")
    return orden

Complejidad: $O(V + E)$.

Resultado bonus: si al final len(orden) != len(grafo), detectaste un ciclo. Es el método más simple de detección de ciclos en digrafos.

Casos de uso reales:

• make, npm, cargo, bazel — dependencias entre archivos/paquetes.
• Schedulers de tareas (Airflow, Prefect).
• Orden de inicialización de servicios (systemd).
• Inferencia en redes neuronales (forward pass).