En este tutorial, aprenderá qué es una estructura de datos de gráficos. Además, encontrará representaciones de un 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.
Intentemos 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.
Toda relación es una ventaja 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.
Ejemplo de estructura de datos de gráfico
Todo Facebook es entonces una colección de estos nodos y bordes. Esto se debe a que Facebook utiliza una estructura de datos gráfica 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, representadas como pares ordenados de vértices (u, v)
Vértices y aristas
En el gráfico,
V = (0, 1, 2, 3) E = ((0,1), (0,2), (0,3), (1,2)) G = (V, E)
Terminología gráfica
- Adyacencia : Se dice que un vértice es adyacente a otro vértice si hay un borde que los conecta. Los vértices 2 y 3 no son adyacentes porque no hay ningún borde entre ellos.
- Ruta : una secuencia de aristas que le permite ir del vértice A al vértice B se llama ruta. 0-1, 1-2 y 0-2 son caminos desde el 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 hay 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 formas:
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
Matriz de adyacencia de gráficos
Dado que es un gráfico no dirigido, para el borde (0,2), también necesitamos marcar el borde (2,0); haciendo que la matriz de adyacencia sea simétrica con respecto a la diagonal.
La búsqueda de aristas (comprobar si existe una arista entre el vértice A y el vértice B) es extremadamente rápida en la representación de la matriz de adyacencia, pero tenemos que reservar espacio para cada posible enlace 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 vinculada 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:
Representación de la lista de adyacencia
Una lista de adyacencia es eficiente en términos de almacenamiento porque solo necesitamos almacenar los valores para 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:
- Compruebe si el elemento está presente en el gráfico.
- Gráfico transversal
- Agregar elementos (vértices, aristas) al gráfico
- Encontrar el camino de un vértice a otro
