Estructura de datos del gráfico
Una estructura de datos de gráfico es una colección de nodos que tienen datos y están conectados a otros nodos.
Tratemos de entender esto a través de un ejemplo. En facebook, todo es un nodo. Eso incluye Usuario, Foto, Álbum, Evento, Grupo, Página, Comentario, Historia, Video, Enlace, Nota… cualquier cosa que tenga datos es un nodo.
Cada relación es una arista de un nodo a otro. Ya sea que publique una foto, se una a un grupo, le guste una página, etc., se crea una nueva ventaja para esa relación.
Todo facebook es entonces una colección de estos nodos y aristas. Esto se debe a que Facebook usa una estructura de datos de gráficos para almacenar sus datos.
Más precisamente, un gráfico es una estructura de datos (V, E) que consta de
- Una colección de vértices V
- Una colección de aristas E, representada como pares ordenados de vértices (u,v)
En el gráfico,
V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}Terminología de gráficos
- Proximidad: Se dice que un vértice es adyacente a otro vértice si hay una arista que los conecta. Los vértices 2 y 3 no son adyacentes porque no hay borde entre ellos.
- Sendero: Una secuencia de aristas que te permite ir del vértice A al vértice B se llama camino. 0-1, 1-2 y 0-2 son caminos del vértice 0 al vértice 2.
- Gráfico dirigido: Un gráfico en el que una arista (u,v) no significa necesariamente que también haya una arista (v,u). Los bordes en dicho gráfico están representados por flechas para mostrar la dirección del borde.
Representación gráfica
Los gráficos se representan comúnmente de dos maneras:
1. Matriz de adyacencia
Una matriz de adyacencia es una matriz 2D de vértices V x V. Cada fila y columna representan un vértice.
Si el valor de cualquier elemento a[i][j] es 1, representa que hay una arista que conecta el vértice i y el vértice j.
La matriz de adyacencia para el gráfico que creamos arriba es
Como es un gráfico no dirigido, para la arista (0,2), también necesitamos marcar la arista (2,0); haciendo que la matriz de adyacencia sea simétrica con respecto a la diagonal.
La búsqueda de bordes (comprobar si existe un borde entre el vértice A y el vértice B) es extremadamente rápida en la representación de matriz de adyacencia, pero tenemos que reservar espacio para cada enlace posible entre todos los vértices (V x V), por lo que requiere más espacio.
2. Lista de adyacencia
Una lista de adyacencia representa un gráfico como una matriz de listas enlazadas.
El índice de la matriz representa un vértice y cada elemento en su lista enlazada representa los otros vértices que forman un borde con el vértice.
La lista de adyacencia para el gráfico que hicimos en el primer ejemplo es la siguiente:
Una lista de adyacencia es eficiente en términos de almacenamiento porque solo necesitamos almacenar los valores de los bordes. Para un gráfico con millones de vértices, esto puede significar mucho espacio ahorrado.
Operaciones gráficas
Las operaciones gráficas más comunes son:
- Comprobar si el elemento está presente en el gráfico
- Gráfico transversal
- Agregar elementos (vértice, bordes) al gráfico
- Encontrar el camino de un vértice a otro
