Los grafos convierten relaciones complejas en estructuras que pueden almacenarse, recorrerse y optimizarse. Rutas, dependencias, recomendaciones, redes, permisos y flujos de datos son problemas de grafos con distintas reglas y objetivos.
Una aplicación suele contener entidades conectadas entre sí: usuarios y amistades, servicios y llamadas, productos y compras, archivos y dependencias. Cuando la conexión es parte central del problema, un modelo de grafo ayuda a expresarlo con precisión.
La utilidad no está solo en dibujar nodos. Un grafo permite formular preguntas concretas: quién alcanza a quién, qué tareas deben ejecutarse antes, qué ruta cuesta menos, qué enlace es crítico o qué elementos forman una comunidad.
El primer paso es decidir qué representa cada vértice y qué representa cada arista. Después se define si la arista tiene dirección, peso, etiqueta o propiedades adicionales.
Agregar una arista no es una decisión técnica neutra. En una red social «ser amigo» puede ser no dirigido, mientras que «seguir» es dirigido; en un sistema de rutas, el sentido de una calle puede transformar una arista en dos direcciones distintas.
Los mapas modelan intersecciones, estaciones o ciudades como vértices y tramos transitables como aristas. Los pesos pueden representar distancia, tiempo estimado, peajes, consumo o riesgo.
Una ruta con menos calles no tiene por qué ser más rápida. El algoritmo debe recibir pesos que reflejen el objetivo real: tiempo, distancia, costo monetario o una combinación definida por el producto.
const rutas = new Map([
["Centro", [
{ destino: "Norte", peso: 8 },
{ destino: "Este", peso: 3 }
]],
["Norte", [{ destino: "Aeropuerto", peso: 5 }]],
["Este", [
{ destino: "Norte", peso: 2 },
{ destino: "Aeropuerto", peso: 12 }
]],
["Aeropuerto", []]
]);
// Dijkstra desde Centro obtiene Centro → Este → Norte → Aeropuerto
// con costo total 3 + 2 + 5 = 10.Cada destino, incluso el que no tiene salidas, aparece como clave. Esta convención evita confundir un vértice válido sin vecinos con un identificador inexistente.
Los módulos, paquetes, tareas de compilación y migraciones forman grafos dirigidos. Una arista A → B puede significar que A debe completarse antes que B, o que A depende de B; hay que documentar la convención.
Las herramientas de construcción usan estas relaciones para ejecutar solo lo necesario cuando cambia un archivo, paralelizar tareas independientes y reportar ciclos de configuración.
Un DAG representa actividades sin dependencias circulares. Las tareas de grado de entrada cero son candidatas a comenzar; al terminar una tarea, pueden desbloquearse otras.
Para estimar duración total se agregan pesos de tiempo y se estudia el camino crítico. Para asignar personas o máquinas se necesitan además restricciones de capacidad que no aparecen en el grafo básico.
Una red de amistad se modela a menudo con un grafo no dirigido; una red de seguimiento o suscripción, con un digrafo. Los vértices son perfiles y las aristas representan la relación social elegida.
Este modelo permite recomendar contactos, analizar comunidades y calcular cercanía. También exige considerar privacidad, consentimiento y sesgos antes de usar conexiones personales para tomar decisiones.
Una heurística simple recomienda usuarios que comparten varios vecinos con una persona, excluyendo a los contactos que ya posee. No es un sistema completo de recomendación, pero ilustra el uso de intersecciones de adyacencia.
function recomendarContactos(adyacentes, usuario) {
const directos = adyacentes.get(usuario) ?? new Set();
const puntajes = new Map();
for (const contacto of directos) {
for (const candidato of adyacentes.get(contacto) ?? []) {
if (candidato === usuario || directos.has(candidato)) continue;
puntajes.set(candidato, (puntajes.get(candidato) ?? 0) + 1);
}
}
return [...puntajes].sort((a, b) => b[1] - a[1]);
}Los candidatos con más vecinos comunes quedan antes. En un producto real se agregan filtros de privacidad, bloqueo, seguridad, diversidad, actualidad y explicaciones para evitar recomendaciones inapropiadas.
La Web puede modelarse como un grafo dirigido: cada página es un vértice y cada enlace es una arista. Un rastreador explora enlaces para descubrir páginas alcanzables desde una semilla.
Los sistemas reales deben respetar políticas de acceso, límites de carga, contenido duplicado, redirecciones y requisitos legales. El modelo de grafo es una parte del problema, no un permiso para rastrear cualquier sitio.
Las bases relacionales representan relaciones con claves y tablas; esas relaciones pueden interpretarse como aristas. Algunas aplicaciones usan bases de datos de grafos cuando las consultas de relaciones de varios saltos son centrales.
Elegir una base de datos de grafos no es obligatorio para trabajar con relaciones. La decisión depende de patrones de consulta, volumen, transacciones, índices y experiencia operativa.
Los permisos pueden modelarse con un grafo dirigido de usuarios, grupos, roles, recursos y reglas de herencia. Una ruta o relación específica puede indicar que una identidad obtiene cierta capacidad.
Los grafos aclaran relaciones complejas, pero no sustituyen un modelo de autorización bien definido. Las decisiones de seguridad deben usar mecanismos de control de acceso revisados y aplicar el principio de mínimo privilegio.
En una infraestructura, los nodos pueden ser servidores, servicios, contenedores o dispositivos; las aristas pueden ser enlaces físicos, llamadas de red o dependencias de datos.
Analizar conectividad permite detectar servicios aislados, rutas redundantes y componentes críticas. Los pesos pueden representar latencia, costo, ancho de banda o riesgo operativo.
Los historiales de versiones suelen formar un DAG: cada confirmación referencia uno o más padres anteriores. Las fusiones generan nodos con varios padres, pero las referencias apuntan hacia estados previos y no deben formar ciclos.
Esta estructura explica por qué dos ramas pueden divergir y luego converger. También permite hallar ancestros comunes y comparar cambios entre versiones.
Los mapas de videojuegos, tableros, laberintos y mundos virtuales se representan como grafos. Un vértice puede ser una celda, una región navegable o un estado del juego.
Para mapas grandes se usan técnicas de partición, heurísticas y precálculo. El modelo de grafo sigue siendo la base, aunque no todos los nodos se materialicen a la vez en memoria.
Algunos problemas agregan capacidad a las aristas. En redes de flujo se busca transportar la mayor cantidad posible desde una fuente hasta un destino sin superar capacidades.
Estas técnicas se usan en asignación de turnos, distribución de recursos, emparejamiento de perfiles y planificación. Requieren algoritmos específicos: una simple búsqueda de camino no optimiza automáticamente el flujo global.
Las métricas de grafos ayudan a describir una red: grado, componentes, centralidad, distancia promedio y densidad. Ninguna métrica por sí sola explica toda la estructura.
Al analizar grafos sociales o de usuarios se deben revisar calidad de datos, sesgos de recolección, privacidad y las consecuencias de automatizar decisiones a partir de relaciones.
Una máquina de estados finitos puede dibujarse como un grafo dirigido: los vértices son estados y las aristas son transiciones etiquetadas por eventos o condiciones.
Este enfoque permite visualizar casos faltantes, validar transiciones permitidas y probar que un proceso no llega a estados imposibles. Conecta los circuitos secuenciales con el modelado de software.
Un grafo real puede tener millones de vértices y aristas. La elección de lista de adyacencia, matriz, índices, almacenamiento distribuido o base especializada depende de las operaciones dominantes.
En sistemas grandes, recorrer todo el grafo por cada solicitud suele ser inviable. Se diseñan límites de profundidad, resultados paginados, cálculos previos y políticas de actualización.
Un gráfico atractivo no corrige un modelo ambiguo. La semántica de los datos debe preceder a la implementación y a la visualización.
Los grafos permiten convertir relaciones complejas en estructuras analizables y programas concretos. En el próximo tema introduciremos autómatas y lenguajes formales, modelos que también usan estados y transiciones para reconocer secuencias.