Qué es una estructura de grafo

Guardar relaciones con puntos y líneas

Hasta ahora vimos cómo guardar valores en filas, tablas y árboles. Pero en algunos datos, las relaciones entre los valores importan más que los valores mismos: quién es amigo de quién, o qué estación se conecta con cuál.
En esos casos, ponerlos en fila resulta forzado. Así que se dibuja a las personas como puntos y las amistades como líneas. A los puntos también se les llama nodos y a las líneas, aristas, y las relaciones quedan guardadas tal cual, solo con puntos y líneas.

Toca a dos personas por turno para unirlas con una línea. Un punto es una persona; una línea es una amistad.

Al unir los puntos, las relaciones se hicieron visibles. Quién está conectado con quién se ve en cuanto miras las líneas, de forma mucho más clara que con filas escritas en una tabla.
Los puntos son cosas y las líneas, relaciones, y los datos guardados con estos dos elementos se llaman grafo. Una relación mutua, como la amistad, se dibuja con una línea sin dirección, mientras que una relación en un solo sentido, como cuando alguien sigue a otra persona, se dibuja con una flecha. Entonces, ¿qué se puede saber siguiendo estas líneas?

Por las líneas hasta el amigo de un amigo

Empieza por una persona. Sigue las líneas unidas a ese punto y llegas a los amigos de esa persona. No te detengas ahí: sigue las líneas unidas a los puntos de esos amigos y llegas a los amigos de sus amigos.
Avanzando así un paso más cada vez, llegas a los conocidos de tus conocidos. Cuando una red social te sugiere "personas que quizá conozcas", funciona de esta manera.

Toca a una persona y se encienden sus amigos; vuelve a tocar y se encienden los amigos de sus amigos.

Un toque encendió a los amigos y otro, a los amigos de los amigos. Lo lejos que está alguien de la persona inicial depende de cuántas líneas cruzaste.
Si cruzas una línea, es un amigo; si cruzas dos, es el amigo de un amigo. Con una tabla, habrías tenido que revisarla una y otra vez para averiguarlo. Siguiendo las líneas, es así de fácil.

Seguir a los vecinos para recorrer un grupo

Los puntos unidos directamente a un punto por una línea se llaman sus vecinos. Sigamos extendiéndonos por las líneas: de un punto a sus vecinos, y luego a los vecinos de los vecinos.
Tarde o temprano ya no queda adónde ir. Los puntos alcanzados hasta entonces forman un grupo conectado. Un punto que no está unido por ninguna línea no pertenece a ese grupo. Ampliar la búsqueda capa a capa de vecinos, empezando por los más cercanos, se llama búsqueda en anchura.

Toca un vecino del borde del grupo encendido para extenderlo paso a paso. Solo se encienden los puntos conectados.

Al extenderse por los vecinos, los puntos conectados se fueron encendiendo uno tras otro. Pudiste visitar todos los lugares a los que llegan las líneas, mientras que un punto separado no se encendió por mucho que avanzaras.
Estar unidos o no por líneas es lo que separa los grupos. En un grafo, seguir a los vecinos es fácil, porque basta con mirar las líneas. Entonces, ¿qué pasaría si hicieras lo mismo con una tabla?

¿Tabla o grafo?

Supón que las amistades están anotadas en una tabla. Para encontrar a los amigos de tus amigos, primero buscas en la tabla a tus propios amigos y los apuntas, y luego vuelves a revisar la tabla por cada uno de ellos. Cada paso más significa recorrer la tabla otra vez.
Con un grafo, sigues las líneas desde un punto, luego las líneas desde los puntos siguientes, y listo. Cuando lo importante son las relaciones, un grafo es mucho más cómodo.

Resuelve la misma pregunta de "amigos de amigos" con una tabla y con un grafo. Compara cuántos toques necesita cada uno.

Con la tabla hicieron falta muchos más toques para encontrar la misma respuesta, porque había que repetir las consultas. Con el grafo bastó con seguir líneas dos veces.
Claro que las tablas no son malas. Para registrar cosas fila por fila y reunirlas, una tabla funciona bien. Pero para seguir relaciones, un grafo de puntos y líneas es mucho más natural y rápido. Cuando una app de mapas busca una ruta, también usa un grafo, con estaciones y calles como puntos y líneas, y una distancia anotada en cada línea.

En resumen

En pocas palabras: guardar las cosas como puntos y las relaciones como líneas te da un grafo. Si sigues las líneas desde un punto, llegas a sus vecinos, y si sigues las de los vecinos, llegas a los amigos de los amigos.
Al extenderte por las líneas aparece el grupo conectado. En las tareas donde las relaciones son lo importante, en lugar de revisar una tabla muchas veces, basta con seguir las líneas. Puntos=cosas, líneas=relaciones y seguir a los vecinos: eso es un grafo.

Toca en orden los puntos clave para repasar. (puntos=cosas, líneas=relaciones → amigos de amigos → seguir a los vecinos → grafos para relaciones)

Ahora ya sabes cómo guardar relaciones con puntos y líneas y recorrerlas siguiendo las líneas. Los amigos de amigos, difíciles de encontrar en una tabla, estaban a solo dos líneas en un grafo. Según la forma que les des a los datos, la misma tarea puede volverse fácil o difícil.
Pero para preguntarle algo a una base de datos, hay que hacerlo en un lenguaje fijo. La próxima lección enseña el lenguaje para hacer preguntas a una base de datos: SQL.