Data Structures
Lecciones · #9 de 11

Grafos

Vértices y aristas — la abstracción universal

Graph · algorithms lab

Click any node to set start, then run BFS or DFS. The frontier panel renders as a queue for BFS and a stack for DFS — that single difference is what makes the two visit orders diverge.

frontier
visited (order) 
click a node, then bfs or dfs

Pruébalo: Seis modos, una sola demostración. recorrer: BFS vs DFS con la frontera visualizada como una cola vs una pila — haz clic en cualquier nodo para fijar el inicio, luego compite con ambos a la vez. camino más corto: elige inicio + meta, compara Dijkstra con A* en un grafo ponderado. cuadrícula: pinta muros y observa cómo BFS planifica rodeándolos. dag · topo: ordena la secuencia de arranque de un robot; introduce un ciclo y observa cómo el algoritmo se niega. grafo de poses: relaja una trayectoria con deriva usando una restricción de cierre de bucle (SLAM de juguete). cobertura: coloca anclas, obtén un diagrama de Voronoi discreto.

Por qué importa

Los grafos modelan relaciones: redes sociales, mapas de carreteras, dependencias, máquinas de estados. BFS encuentra caminos más cortos, DFS explora todas las posibilidades. Los grafos son el lenguaje universal de los datos conectados.

La idea

Piensa en un mapa de ciudades conectadas por carreteras. Cada ciudad es un vértice (nodo), cada carretera es una arista (conexión).

Los grafos pueden ser:

Dos representaciones:

  1. Matriz de adyacencia: Arreglo 2D donde matriz[i][j] = 1 si existe la arista. Búsqueda rápida O(1), pero espacio O(V^2).
  2. Lista de adyacencia: Cada vértice almacena una lista de sus vecinos. Eficiente en espacio, O(V+E).

Dos recorridos:

Puntos clave

Profundizando

Ordenamiento topológico — el algoritmo de Kahn y los tiempos de finalización de DFS

Un DAG (grafo dirigido acíclico) representa dependencias. El ordenamiento topológico lineariza el DAG de modo que cada arista u → v tenga a u apareciendo antes que v en la salida — es decir, cada dependencia viene antes que sus dependientes. Dos algoritmos, ambos O(V + E):

Algoritmo de Kahn (usado en el modo dag · topo de la demostración):

1. Calcula el grado de entrada de cada nodo.
2. Encola todos los nodos con grado de entrada 0 (sin dependencias).
3. Mientras la cola no esté vacía:
     u = desencolar.  emitir(u).
     Para cada arista u → v:
       grado-entrada[v] -= 1
       si grado-entrada[v] == 0: encolar(v).
4. Si se emitieron menos de V nodos → el grafo contiene un ciclo.

Variante con tiempos de finalización de DFS: ejecuta DFS desde cada nodo no visitado; cuando un nodo termina (todos sus descendientes explorados), apílalo en una pila. Desapila en orden inverso para obtener el orden topológico. Esta variante se extiende naturalmente para encontrar componentes fuertemente conexos (Kosaraju, Tarjan) — sus aplicaciones incluyen encontrar grupos en grafos sociales y analizar el flujo de control de programas.

Uso en robótica: los archivos de lanzamiento de ROS forman un DAG (cada nodo tiene nodos prerrequisito que deben iniciarse primero); el sistema de lanzamiento hace ordenamiento topológico por debajo. Los árboles de comportamiento y los grafos de compilación de Make/Bazel tienen la misma forma.

Bellman-Ford — el primo de Dijkstra para pesos negativos

Dijkstra asume pesos de arista no negativos. Su prueba de correctitud se apoya en el hecho de que, una vez que extraes un nodo de la cola de prioridad con el costo-hasta-ahora mínimo, ningún camino más corto podría llegar después. Las aristas negativas rompen esa suposición — un desvío largo pero barato podría acortar un camino "ya establecido".

Bellman-Ford sacrifica velocidad por la capacidad de manejar pesos negativos:

Por cada una de V−1 iteraciones:
  Por cada arista (u, v, w):
    si dist[u] + w < dist[v]: dist[v] = dist[u] + w

Eso es O(V·E) — mucho más lento que el O((V+E) log V) de Dijkstra con un montículo. La recompensa es la correctitud bajo pesos negativos, y la capacidad de detectar ciclos negativos (una V-ésima iteración que aún relaja alguna arista significa que existe un ciclo con peso total negativo — tu camino más corto daría vueltas para siempre).

Cuándo lo necesitas: detección de arbitraje de divisas, planificación de rutas con reembolsos de peaje / subsidios, cualquier cosa donde las aristas puedan ser "descuentos". La mayor parte de la navegación en robótica usa solo costos no negativos (distancia, energía, tiempo), así que Dijkstra y A* dominan.

Árbol de expansión mínima (MST)

Para un grafo conexo, no dirigido y ponderado, un MST es el subconjunto de V − 1 aristas que conecta todos los vértices con peso total mínimo. Dos algoritmos clásicos, ambos O(E log V):

Cuándo lo necesitas: trazado de carreteras / cableado / tuberías, agrupamiento (el agrupamiento por enlace simple = construir un MST y luego cortar las aristas más grandes), diseño de redes. Para la coordinación multiagente en robótica, el MST da un árbol de comunicación mínima que abarca todos los robots.

Elecciones de representación

Matriz de adyacencia vs lista de adyacencia no es solo cuestión de espacio. Tienen distintos puntos óptimos:

La mayoría de las librerías de grafos de producción usan listas por defecto. La estructura Graph de la demostración de camino más corto de arriba usa listas de adyacencia indexadas por el id del nodo.

Detalles matemáticos

Complejidad espacial
Adjacency Matrix: O(V^2)
Adjacency List: O(V + E)
Complejidad temporal
BFS/DFS: O(V + E)
Check edge (matrix): O(1)
Check edge (list): O(degree)

Implementación

Representaciones de grafos

// Lista de adyacencia
let mut graph: Vec<Vec<usize>> = vec![vec![]; n];
graph[0].push(1);  // Arista 0 -> 1
graph[1].push(0);  // Arista 1 -> 0 (no dirigido)

// BFS desde el vértice 0
let mut visited = vec![false; n];
let mut queue = VecDeque::from([0]);
while let Some(v) = queue.pop_front() {
    if visited[v] { continue; }
    visited[v] = true;
    for &neighbor in &graph[v] {
        queue.push_back(neighbor);
    }
}

Algoritmos clásicos

Práctica

Tres problemas que cubren los tres modismos de grafos más solicitados:

→ Explora todos los problemas de práctica