Datos unidos con puntos y líneas, el grafo

Guarda relaciones como puntos y líneas

Antes aprendimos a guardar valores
en fila por números de casilla.
Pero para ciertos datos,
la relación entre las cosas importa más que cada valor.
Como quién es amigo de quién.
Poner esos datos en fila resulta torpe.
Por eso dibujamos a cada persona como un punto,
y cada amistad como una línea.
Solo con puntos y líneas, la relación queda guardada tal cual.

Toca a dos personas por turno para unirlas con una línea. Los puntos son personas, las líneas amistades.

Al unir los puntos, la relación se hizo visible.
Quién está conectado con quién,
lo notas solo mirando las líneas.
Llega mucho más como una imagen
que filas escritas una a una en una tabla.
Los puntos son cosas, las líneas relaciones.
Los datos guardados con estos dos se llaman grafo.
Entonces, si seguimos estas líneas,
¿qué podemos averiguar?

Por las líneas hasta el amigo de un amigo

Empecemos por una persona.
Sigue las líneas atadas a ese punto,
y enseguida aparecen los amigos de esa persona.
Sin parar ahí,
sigue también las líneas atadas al punto de un amigo,
y aparece el amigo de un amigo.
Dando un salto más lejos así,
llegas a conocidos de conocidos.
Así se hacen las recomendaciones.

Toca a una persona para encender a los amigos, toca otra vez para los amigos de amigos, paso a paso.

Un toque encendió a los amigos,
otro toque encendió a los amigos de amigos.
Qué tan lejos está alguien del inicio
lo fija cuántas líneas cruzaste.
A una línea está un amigo,
a dos líneas un amigo de un amigo.
Con una tabla habrías buscado
una y otra vez para hallar esto.
Siguiendo líneas, es así de fácil.

Sigue a los vecinos para recorrer el grupo

Los puntos unidos por una línea directa a un punto
se llaman vecinos de ese punto.
De un punto a sus vecinos,
luego a los vecinos de esos,
sigamos extendiéndonos por las líneas.
Con el tiempo no queda adónde ir.
Los puntos alcanzados para entonces
son un grupo conectado entre sí.
Un punto sin línea que entre no se suma.

Toca un vecino que toque el borde del grupo encendido para extender un salto. Solo se encienden los puntos conectados.

Al extenderse por los vecinos,
los puntos conectados se encendieron uno a uno.
Adonde llegaba una línea, podías recorrer.
Los puntos separados, en cambio,
nunca se encendieron por lejos que fueras.
Que una línea los conecte es lo que separa los grupos.
Seguir a los vecinos así
es fácil en un grafo, pues solo miras las líneas.
Pero ¿y si hicieras lo mismo con una tabla?

Por tabla, o por grafo

Supón que las amistades están en una tabla.
Para hallar al amigo de un amigo,
primero buscas a los amigos en la tabla y los anotas,
luego por cada amigo revisas la tabla otra vez.
Cada vez que avanzas un paso,
recorres la tabla desde arriba una vez más.
Con un grafo, sigues una línea desde un punto,
luego una línea desde ese punto, y listo.
Cuando la relación es lo central, un grafo es mucho más cómodo.

Resuelve la misma pregunta de "amigo de un amigo" por tabla y por grafo. Compara cuántos toques lleva cada uno.

Por tabla, hallar la misma respuesta
llevó muchos más toques.
Porque suponía buscar una y otra vez.
El grafo siguió líneas dos veces y terminó.
Claro que una tabla no es mala.
Para anotar cosas en fila, una a una, la tabla va genial.
Pero para tareas que siguen relaciones,
un grafo que las guarda como puntos y líneas
es mucho más natural y rápido.

Resumamos

Reunido en una línea, es esto.
Guarda las cosas como puntos y las relaciones como líneas.
Eso es un grafo.
Desde un punto, seguir una línea da un vecino,
y seguir al vecino da al amigo de un amigo.
Extiéndete por las líneas y aparece un grupo conectado.
Para tareas donde la relación es lo central,
lo que una tabla te hace buscar, lo alcanzas con solo seguir líneas.
Los puntos son cosas, las líneas relaciones, sigues a los vecinos. Eso es un grafo.

Toca los puntos clave en orden para repasar. (puntos son cosas, líneas relaciones -> amigo de un amigo -> sigue a los vecinos -> grafos para relaciones)

Ahora sabes guardar relaciones como puntos y líneas
y recorrer siguiendo líneas.
Un amigo de un amigo, torpe por tabla,
se alcanzó en dos líneas en un grafo.
Según la forma que des a los datos,
la misma tarea se vuelve más fácil o más difícil.
El ojo para elegir esa forma
es la fuerza de manejar datos.
Sigamos explorando juntos la próxima vez también.