Tabla de Contenidos
Esta chuleta está hecha para dos momentos: la última hora antes de una entrevista técnica y la mitad de una sesión de programación cuando conoces la forma del problema pero necesitas la herramienta exacta. Es deliberadamente compacta. Para la historia completa detrás de cada algoritmo, sigue los enlaces a los artículos en profundidad, y si quieres un camino estructurado por todo ello, empieza con la hoja de ruta de teoría de grafos.
A lo largo del texto, V es el número de vértices (nodos) y E es el número de aristas.
La Tabla Maestra de Complejidad
Lo más útil que se puede tener memorizado. Las complejidades suponen la implementación eficiente estándar (montículo binario para Dijkstra y Prim, compresión de caminos y unión por rango para union-find).
| Algoritmo | Mejor para | Tiempo | Espacio |
|---|---|---|---|
| BFS | Camino más corto en grafos no ponderados, orden por niveles | O(V + E) | O(V) |
| DFS | Conectividad, ciclos, explorar la estructura | O(V + E) | O(V) |
| Dijkstra | Camino más corto, pesos no negativos | O((V + E) log V) | O(V) |
| Bellman-Ford | Camino más corto con pesos negativos | O(V · E) | O(V) |
| Floyd-Warshall | Caminos más cortos entre todos los pares, grafos pequeños y densos | O(V³) | O(V²) |
| A* | Camino más corto heurístico (mapas, videojuegos) | O(E) típico | O(V) |
| Kruskal | Árbol de expansión mínima, grafos dispersos | O(E log E) | O(V) |
| Prim | Árbol de expansión mínima, grafos densos | O((V + E) log V) | O(V) |
| Topological Sort | Ordenar un DAG por dependencias | O(V + E) | O(V) |
| Union-Find | Conectividad dinámica, agrupamiento | O(α(V)) por op. | O(V) |
| Tarjan / Kosaraju | Componentes fuertemente conexas | O(V + E) | O(V) |
| Edmonds-Karp | Flujo máximo, corte mínimo | O(V · E²) | O(V + E) |
| ¿Necesitas el código real? Esta tabla lista 12 esenciales de un vistazo. El Manual de algoritmos tiene los 55, cada uno con el pseudocódigo y su complejidad desarrollada paso a paso. | |||
Nota sobre A*: su tiempo de ejecución depende por completo de la heurística. Con una heurística perfecta va casi en línea recta a la meta; con una inútil se degrada a Dijkstra. La α en union-find es la función inversa de Ackermann, en la práctica una constante pequeña para cualquier entrada que verás jamás. Para el razonamiento detrás de cada fila, consulta la guía de complejidad de algoritmos de grafos.
Representaciones de Grafos
Antes de cualquier algoritmo, eliges cómo almacenar el grafo. Esta única decisión afecta a cada complejidad de arriba.
| Representación | Espacio | Consulta de arista | Mejor para |
|---|---|---|---|
| Lista de adyacencia | O(V + E) | O(degree) | Grafos dispersos, la opción por defecto |
| Matriz de adyacencia | O(V²) | O(1) | Grafos densos, consultas en tiempo constante |
Regla general: recurre a la lista de adyacencia salvo que el grafo sea denso o necesites comprobaciones de aristas en tiempo constante. Una cuadrícula 2D es un grafo implícito donde cada celda es un nodo conectado a sus vecinas, así que a menudo no necesitas ninguna representación explícita.
Recorrido: BFS y DFS
Los dos algoritmos sobre los que se construye todo lo demás. Aprende la comparación completa en BFS vs DFS.
- BFS usa una cola, explora nivel por nivel y encuentra el camino más corto en un grafo no ponderado. Palabras clave: más corto, pasos mínimos, más cercano, orden por niveles.
- DFS usa una pila (a menudo la pila de llamadas de la recursión), se sumerge en profundidad y es ideal para conectividad, detección de ciclos y backtracking. Palabras clave: todos los caminos, alcanzabilidad, regiones, explorar.
Caminos Más Cortos
La familia más común en entrevistas y en la práctica. La elección correcta la dictan los pesos de las aristas. La inmersión completa está en entender los algoritmos de caminos más cortos.
| Situación | Usa | Por qué |
|---|---|---|
| Aristas no ponderadas | BFS | La primera llegada es el camino más corto |
| Pesos no negativos | Dijkstra | Voraz con un min-heap, siempre correcto aquí |
| Pesos negativos | Bellman-Ford | Relaja las aristas V-1 veces, detecta ciclos negativos |
| Todos los pares a la vez | Floyd-Warshall | Tres bucles anidados, código diminuto, genial en grafos pequeños |
| Tienes una heurística | A* | Dijkstra guiado hacia la meta, ver A* |
La trampa clásica: nunca ejecutes Dijkstra en un grafo con aristas negativas. Fija un nodo como definitivo demasiado pronto y puede devolver una respuesta incorrecta. Recurre a Bellman-Ford en su lugar.
Árboles de Expansión Mínima
Conecta cada vértice al menor costo total de aristas. Ambos algoritmos son correctos; elige por la densidad del grafo. Recorridos completos en árboles de expansión mínima.
- Kruskal: ordena todas las aristas, añade la más barata que no forme un ciclo, usando union-find para comprobar ciclos. Brilla en grafos dispersos.
- Prim: haz crecer un solo árbol hacia fuera, añadiendo siempre la arista más barata que sale de él, usando una cola de prioridad. Brilla en grafos densos.
Ordenamiento y Conectividad
- Orden topológico (de Kahn o basado en DFS): produce un orden lineal de un DAG de modo que cada arista apunte hacia adelante. La herramienta para dependencias, orden de compilación y planificación. Imposible si existe un ciclo, que es justo cómo detectas uno.
- Union-Find (conjuntos disjuntos): responde "¿están estos dos en el mismo grupo?" y fusiona grupos en tiempo casi constante. La columna vertebral de Kruskal y de los problemas de conectividad dinámica.
- Componentes fuertemente conexas (Tarjan o Kosaraju): encuentra grupos maximales donde cada nodo alcanza a todos los demás, en un grafo dirigido. Ambos se ejecutan en
O(V + E).
Los tres aparecen constantemente en entrevistas. Consulta los patrones resueltos en algoritmos de grafos esenciales para entrevistas de programación.
Flujo en Redes
Modela el rendimiento, el emparejamiento y los cuellos de botella. El resultado elegante aquí es que el flujo máximo es igual al corte mínimo. Tratamiento completo en flujo en redes y el teorema de flujo máximo y corte mínimo.
- Ford-Fulkerson: empuja repetidamente flujo por caminos de aumento en el grafo residual. Sencillo, pero su tiempo de ejecución depende de los valores de flujo.
- Edmonds-Karp: Ford-Fulkerson que encuentra caminos de aumento con BFS, dando una cota limpia
O(V · E²)independiente de las capacidades.
¿Qué Algoritmo Debería Usar?
La forma más rápida de usar esta chuleta: lee la columna izquierda, salta a la derecha.
| Si necesitas… | Recurre a |
|---|---|
| Visitar o explorar cada nodo | BFS o DFS |
| Encontrar el camino más corto en un grafo no ponderado | BFS |
| Encontrar el camino más corto con pesos no negativos | Dijkstra |
| Manejar pesos de arista negativos | Bellman-Ford |
| Obtener caminos más cortos entre todos los pares | Floyd-Warshall |
| Encontrar un camino rápido con una heurística (mapas, videojuegos) | A* |
| Conectar todo al costo mínimo | Kruskal o Prim |
| Ordenar tareas por sus dependencias | Orden topológico |
| Comprobar si dos nodos están conectados, o agrupar elementos | Union-Find |
| Encontrar clústeres en un grafo dirigido | Tarjan o Kosaraju (SCC) |
| Maximizar el rendimiento o encontrar un cuello de botella | Edmonds-Karp (flujo máximo) |
Convierte la tabla en intuición
Una chuleta te dice qué algoritmo; verlo ejecutarse te dice por qué. Recorre cualquiera de estos paso a paso en un grafo en vivo.
Abrir el Visualizador de AlgoritmosPreguntas Frecuentes
¿Cuál es la complejidad temporal del algoritmo de Dijkstra?
Con un montículo binario (cola de prioridad), el algoritmo de Dijkstra se ejecuta en tiempo O((V + E) log V) y espacio O(V). Con un simple arreglo en lugar de un montículo es O(V al cuadrado), que puede ser más rápido en grafos densos.
¿Qué algoritmo de grafos debería usar para caminos más cortos?
Depende del grafo. Usa BFS para grafos no ponderados, Dijkstra para pesos no negativos, Bellman-Ford cuando hay pesos negativos, Floyd-Warshall para caminos más cortos entre todos los pares, y A* cuando tienes una buena heurística (mapas y videojuegos).
¿Debería usar una lista de adyacencia o una matriz de adyacencia?
Usa una lista de adyacencia para grafos dispersos: usa O(V + E) espacio y es la opción por defecto para la mayoría de los problemas. Usa una matriz de adyacencia para grafos densos o cuando necesitas consultas de aristas en O(1), a costa de O(V al cuadrado) espacio.
¿Qué algoritmos de grafos debería memorizar para entrevistas de programación?
Los cinco esenciales son BFS, DFS, el algoritmo de Dijkstra, el ordenamiento topológico y union-find. Juntos cubren la gran mayoría de las preguntas de grafos en las entrevistas técnicas.