1. ¿Qué es la teoría de grafos y por qué es importante en programación?

1.1 Introducción

La teoría de grafos es una rama de la matemática que estudia conjuntos de objetos y las relaciones que los conectan. Estos objetos se representan mediante vértices, también llamados nodos, y las relaciones mediante aristas.

Un mapa de carreteras, una red social y las dependencias de un proyecto de software parecen sistemas diferentes. Sin embargo, todos pueden describirse de la misma forma: hay elementos y existen conexiones entre algunos de ellos.

En este curso utilizaremos JavaScript para transformar estas ideas matemáticas en estructuras de datos y algoritmos ejecutables.

1.2 La idea central de un grafo

Un grafo se define habitualmente como un par de conjuntos. El conjunto V contiene los vértices y el conjunto E contiene las aristas que relacionan esos vértices.

Por ejemplo, podemos representar tres ciudades mediante V = {A, B, C}. Si hay una carretera entre A y B, y otra entre B y C, las conexiones son E = {{A, B}, {B, C}}.

El grafo no necesita guardar todos los detalles del mundo real. Conserva únicamente los objetos y relaciones necesarios para resolver el problema que nos interesa.

1.3 ¿Qué puede representar un grafo?

La misma estructura abstracta puede utilizarse en contextos muy distintos. Lo que cambia es el significado de sus vértices y aristas.

1.4 Un primer grafo en JavaScript

Podemos comenzar con dos arreglos: uno para los vértices y otro para las aristas. Cada arista se representa como un par de nombres.

const vertices = ["Ana", "Bruno", "Carla", "Diego"];

const aristas = [
  ["Ana", "Bruno"],
  ["Ana", "Carla"],
  ["Bruno", "Diego"]
];

console.log("Vértices:", vertices.length);
console.log("Aristas:", aristas.length);

Este pequeño grafo podría representar una red de amistades. Los cuatro nombres son los vértices y cada par indica una conexión. Más adelante aprenderemos representaciones más eficientes para consultar y recorrer grafos.

1.5 Pensar un problema como un grafo

Antes de programar conviene identificar qué elementos son importantes y qué tipo de relación existe entre ellos.

1.6 De los datos al problema

Guardar datos no es suficiente: normalmente queremos responder preguntas sobre sus relaciones. Un grafo convierte esas conexiones en información que puede explorarse mediante algoritmos.

• ¿Existe una ruta entre dos lugares?
• ¿Cuál es el camino más corto o más económico?
• ¿Qué personas forman comunidades dentro de una red?
• ¿En qué orden deben ejecutarse tareas con dependencias?
• ¿Qué dispositivos son puntos críticos de una red?
• ¿Es posible visitar todas las ubicaciones sin repetir trayectos?

Estas preguntas requieren algoritmos diferentes, pero todas parten de la misma representación mediante vértices y aristas.

1.7 Consultar conexiones en código

A partir del grafo anterior podemos crear una función sencilla que determine si dos personas están conectadas directamente.

const amistades = [
  ["Ana", "Bruno"],
  ["Ana", "Carla"],
  ["Bruno", "Diego"]
];

function sonAmigos(persona1, persona2) {
  return amistades.some(([a, b]) =>
    (a === persona1 && b === persona2) ||
    (a === persona2 && b === persona1)
  );
}

console.log(sonAmigos("Ana", "Carla"));
console.log(sonAmigos("Carla", "Diego"));

El primer resultado es true porque hay una arista directa entre Ana y Carla. El segundo es false: que ambas pertenezcan al grafo no significa que estén conectadas directamente.

1.8 Conexión directa y camino

Dos vértices pueden estar relacionados de forma directa mediante una arista o de forma indirecta mediante una secuencia de aristas. Esa secuencia recibe el nombre de camino.

Ana y Diego no tienen una arista directa en el ejemplo, pero existe un camino entre ellos a través de Bruno. Distinguir entre conexión directa y alcanzabilidad es fundamental en buscadores, mapas, redes y sistemas de recomendaciones.

1.9 ¿Por qué los grafos son importantes en programación?

Los grafos proporcionan un vocabulario común para problemas basados en relaciones. Una vez que un sistema se modela como grafo, podemos aplicar algoritmos conocidos en lugar de diseñar una solución completamente nueva para cada caso.

• Abstracción: permiten conservar las relaciones relevantes y omitir detalles innecesarios.
• Reutilización: un mismo algoritmo puede servir para mapas, redes o dependencias.
• Eficiencia: existen estructuras y algoritmos especializados para grafos de gran tamaño.
• Análisis: ayudan a descubrir rutas, grupos, ciclos, jerarquías y puntos críticos.
• Comunicación: facilitan describir sistemas complejos de forma visual y precisa.

1.10 Aplicaciones en el desarrollo de software

1.11 Cuándo conviene utilizar un grafo

Un grafo es una buena elección cuando las relaciones entre los datos son tan importantes como los datos mismos. También resulta útil cuando debemos recorrer conexiones, encontrar rutas o analizar cómo una modificación se propaga por un sistema.

No todos los problemas necesitan grafos. Para una colección simple sin relaciones puede bastar un arreglo; para búsquedas directas por clave, un mapa o diccionario suele ser más adecuado. El objetivo no es usar grafos siempre, sino reconocer cuándo el problema tiene una estructura de red.

1.12 Qué debes recordar de este tema

• Un grafo es una estructura formada por vértices y aristas.
• Los vértices representan objetos y las aristas representan relaciones.
• La notación habitual de un grafo es G = (V, E).
• Una conexión directa no es lo mismo que un camino entre varios vértices.
• Mapas, redes sociales, dependencias y enlaces web pueden modelarse como grafos.
• Representar un problema como grafo permite aplicar estructuras y algoritmos conocidos.
• Los grafos son especialmente útiles cuando necesitamos analizar conexiones.

1.13 Conclusión

La teoría de grafos ofrece una forma sencilla y poderosa de pensar sistemas conectados. Al separar un problema en objetos y relaciones podemos representar situaciones muy diferentes con una estructura común y analizarlas mediante algoritmos.

En el próximo tema conoceremos la historia de la teoría de grafos, desde el problema de los puentes de Königsberg hasta su presencia en la informática actual.