Algoritmos de grafos
Algoritmos5 algoritmos · 10 ejercicios corregidos · código en Java, Python, JavaScript, C# y PHP
Un grafo es un conjunto de nodos unidos por aristas: ciudades y carreteras, usuarios que se siguen, tareas que dependen de otras, páginas enlazadas. Muchísimos problemas se resuelven en cuanto se ven como un grafo: el camino más corto en un mapa, a cuántos «saltos» está alguien en una red social, en qué orden compilar los módulos de un proyecto.
Casi todo se construye sobre dos recorridos: en anchura (BFS, por niveles, con una cola) y en profundidad (DFS, hasta el fondo, con una pila o recursividad). Sobre ellos, Dijkstra calcula caminos mínimos con pesos, la ordenaci ón topológica ordena dependencias y Kruskal o Prim conectan todos los nodos con el mínimo coste.
Los algoritmos
Recorrido en anchura (BFS)
Recorre un grafo por capas: primero los vecinos del origen, luego los vecinos de esos… Con una cola, encuentra el camino con menos aristas entre dos nodos.intermedio2 ejerciciosRecorrido en profundidad (DFS)
Recorre un grafo yendo lo más lejos posible por cada camino antes de volver atrás. Con recursividad o una pila, sirve para contar componentes, detectar ciclos y explorar laberintos.intermedio2 ejerciciosAlgoritmo de Dijkstra
El camino más corto desde un nodo a todos los demás en un grafo con pesos no negativos: fija cada vez el nodo pendiente más cercano con una cola de prioridad. Es lo que hay detrás de un GPS.avanzado2 ejerciciosOrdenación topológica
Ordena los nodos de un grafo dirigido para que cada uno vaya después de todos los que necesita. El algoritmo de Kahn quita nodos sin dependencias pendientes y detecta los ciclos.intermedio2 ejerciciosKruskal (árbol de expansión mínima)
Conecta todos los nodos de un grafo con el menor coste total: ordena las aristas por peso y coge cada una si no cierra un ciclo, algo que se comprueba con conjuntos disjuntos (union-find).avanzado2 ejercicios
Cuál elegir
| Algoritmo | Para qué | Coste | Usa |
|---|---|---|---|
| Recorrido en anchura (BFS) | Recorrer por niveles; camino más corto sin pesos | O(V + E) | Una cola |
| Recorrido en profundidad (DFS) | Recorrer hasta el fondo; ciclos, componentes | O(V + E) | Una pila o recursividad |
| Algoritmo de Dijkstra | Camino más corto con pesos no negativos | O((V + E) log V) | Una cola de prioridad |
| Ordenación topológica | Ordenar tareas con dependencias | O(V + E) | Grados de entrada y una cola |
| Kruskal (árbol de expansión mínima) | Conectar todos los nodos con coste mínimo | O(E log E) | Ordenar aristas y conjuntos disjuntos |
V es el número de nodos (vértices) y E el de aristas.