Algoritmos de grafos: las estructuras que modelan el mundo real

Las redes sociales, internet, los mapas de carreteras, las cadenas de suministro — todos son grafos. Los algoritmos sobre grafos son de las herramientas más versátiles y poderosas de la informática.

¿Qué es un grafo?

Un grafo es un conjunto de nodos (vértices) conectados por aristas. Pueden ser dirigidos (las aristas tienen dirección, como Twitter: puedo seguirte sin que me sigas) o no dirigidos (como Facebook: la amistad es mutua). Las aristas pueden tener pesos (distancias, costes) o no.

BFS y DFS: los dos recorridos fundamentales

BFS (Breadth-First Search): explora nivel por nivel, empezando por los vecinos más cercanos. Ideal para encontrar el camino más corto en grafos no ponderados. Usa una cola (FIFO).

DFS (Depth-First Search): explora tan lejos como puede antes de retroceder. Ideal para detectar ciclos, ordenación topológica y componentes conexas. Usa una pila (o recursión).

Aplicaciones reales de algoritmos de grafos

PageRank (Google): algoritmo de grafos dirigidos que asigna importancia a páginas web según cuántos links reciben y de quién.
Detección de comunidades: en redes sociales, para identificar grupos de usuarios relacionados.
Árbol de expansión mínima (Kruskal, Prim): diseño de redes de telecomunicaciones con el mínimo cable.
Flujo máximo (Ford-Fulkerson): optimización de redes de distribución, asignación de recursos.

Preguntas frecuentes

¿Cuándo usar BFS y cuándo DFS?

BFS para encontrar el camino más corto (en número de aristas) o explorar por niveles de proximidad. DFS para explorar todas las ramas posibles, detectar ciclos o hacer ordenación topológica.

¿Qué librería usar para grafos en Python?

NetworkX es la más completa para análisis de grafos. Para grafos grandes de alto rendimiento, igraph o graph-tool son más eficientes.