Lista de adyacencia y representación matricial del gráfico
sarah chen
⚡ Resumen inteligente
Las listas de adyacencia y las matrices de grafos almacenan vértices y aristas en memoria, lo que permite a los algoritmos recorrer las redes. Las listas de adyacencia utilizan listas enlazadas por vértice, mientras que las matrices de adyacencia utilizan una cuadrícula cuadrada bidimensional.
Aunque se ven diferentes, todos tipos de graficas se puede representar de forma similar. Generalmente existen dos tipos de representación gráfica:
- Matriz de adyacencia
- Lista de adyacencia
Lista de adyacencia
Una lista de adyacencia se compone de listas enlazadas. Cada vértice se considera un índice de la matriz, y cada elemento representa una lista enlazada. Estas listas enlazadas contienen los vértices que comparten una arista con el vértice índice.
Aquí tienes un ejemplo de una lista de adyacencia:
Sea un grafo con V vértices y E aristas. La complejidad espacial de la lista de adyacencia es O(V + E), que se escala con el número de aristas reales en lugar de con cada par posible de vértices.
La complejidad espacial en el peor de los casos se convierte en O(V²) si el grafo dado es un grafo completo, ya que cada vértice se conecta con todos los demás vértices.
Matriz de adyacencia
Una matriz de adyacencia se compone de una matriz bidimensional. Para un grafo con V vértices, el tamaño de la matriz será V × V.
Dicen matrix[i][j] = 5. Significa que hay una arista entre el nodo i y el nodo j donde el peso es 5.
Analicemos el siguiente gráfico y su matriz de adyacencia:
Construimos el Matriz 2D usando estos pasos:
Paso 1) El vértice A tiene una arista directa con B, y el peso es 5. Por lo tanto, la celda en la fila A y la columna B se llenarán con 5. El resto de las celdas en la fila A se llenarán con cero.
Paso 2) El vértice B tiene una arista directa con C, y el peso es 4. Por lo tanto, la celda en la fila B y la columna C se llenarán con 4. Las celdas restantes en la fila B se llenarán con cero, ya que B no tiene ninguna arista saliente hacia ningún otro nodo.
Paso 3) El vértice C no tiene aristas directas con ningún otro vértice. Por lo tanto, la fila C se rellenará con ceros.
Paso 4) El vértice D tiene una arista dirigida con A y C.
- La celda en la fila D y la columna A tendrá un valor de 7. La celda en la fila D y la columna C tendrá un valor de 2.
- El resto de las celdas de la fila D se rellenarán con ceros.
Paso 5) El vértice E tiene una arista dirigida con B y D. La celda en la fila E y la columna B tendrá un valor de 6. La celda en la fila E y la columna D tendrá un valor de 3. El resto de las celdas en la fila E se rellenarán con ceros.
Aquí hay algunos puntos a tener en cuenta:
- El gráfico no presenta bucles propios cuando la diagonal principal de la matriz de adyacencia es 0.
- El grafo es dirigido si las celdas en las posiciones (a, b) y (b, a) no tienen el mismo valor. En caso contrario, el grafo es no dirigido.
- El gráfico es un gráfico ponderado si el valor de cualquier celda es mayor que 1.
El principal problema de la matriz de adyacencia es que requiere espacio cuadrado. Incluso las aristas que no existen siguen asignando celdas en la memoria.
Por ejemplo, si tenemos un grafo con 100 nodos, entonces se necesitan 10,000 celdas para almacenarlo en RAM. Con menos aristas en el grafo, asignar tanta memoria puede ser un desperdicio. Por lo tanto, la complejidad espacial usando la matriz de adyacencia es O(N²)donde N es el número de nodos en el grafo.
Lista de adyacencia vs. Matriz de adyacencia
Antes de elegir una representación, resulta útil comparar ambos modelos uno al lado del otro en las operaciones que predominan en las cargas de trabajo de grafos reales:
| Operadisrupción | Matriz de adyacencia | Lista de adyacencia |
|---|---|---|
| Complejidad espacial | O(V²) | O(V + E) |
| Agregar un vértice | O(V²) | O (1) |
| Añade un borde | O (1) | O (1) |
| Eliminar un borde | O (1) | O(E) |
| Comprueba si existe la arista (i, j). | O (1) | O(grado de i) |
| Iterar sobre los vecinos de i | O (V) | O(grado de i) |
| Mejores para | Grafos densos, consultas frecuentes a los bordes | Grafos dispersos, tareas con mucho recorrido |
En resumen, la matriz de adyacencia es superior en búsquedas de aristas en tiempo constante, mientras que la lista de adyacencia es superior en cuanto a memoria e iteración de vecinos, razón por la cual algoritmos como BFS, DFS y Dijkstra suelen combinarse con listas de adyacencia.
Ventajas y desventajas de la representación gráfica
Cada representación tiene sus propias ventajas y desventajas. Conocer las fortalezas y debilidades de ambos modelos te ayudará a elegir el más adecuado para el problema que estás resolviendo.
Ventajas de la matriz de adyacencia:
- Consultas de existencia de aristas en tiempo constante O(1) entre cualquier par de vértices.
- La indexación fija facilita la implementación de algoritmos basados en matrices, como Floyd-Warshall y el cierre transitivo.
- Los bordes ponderados encajan de forma natural en una única celda de la matriz.
Desventajas de la matriz de adyacencia:
- Desperdicia O(V²) de memoria cuando el grafo es disperso.
- Agregar un nuevo vértice requiere redimensionar toda la matriz.
- Iterar sobre los vecinos de un solo vértice toma O(V) incluso cuando el vértice tiene solo unas pocas aristas.
Ventajas de la lista de adyacencia:
- Utiliza únicamente memoria O(V + E), lo que se aproxima al número real de aristas en grafos dispersos.
- Agregar un nuevo vértice o arista es O(1).
- Los algoritmos de recorrido como BFS y DFS iteran sobre los vecinos en O(grado), lo que da un tiempo de ejecución total de O(V + E).
Desventajas de la lista de adyacencia:
- Comprobar si existe una arista específica lleva un tiempo de O(grado) en lugar de O(1).
- La localidad de la caché es más débil porque las listas enlazadas están dispersas por la memoria.
- Las aristas ponderadas necesitan un campo complementario o una lista de pares, lo que complica ligeramente la estructura de datos.
Cuándo usar la lista de adyacencia frente a la matriz de adyacencia
La elección de la representación depende de la densidad del grafo y de las operaciones que realice con mayor frecuencia. Utilice esta guía rápida para seleccionar la estructura adecuada:
- Prefiero la matriz de adyacencia. cuando el grafo es denso (E está cerca de V²), cuando las aristas rara vez cambian y cuando su algoritmo pregunta "¿hay una arista entre i y j?" muchas veces.
- Prefiero la lista de adyacencia cuando el grafo es disperso (E es mucho más pequeño que V²), cuando el conjunto de vértices o aristas crece durante la ejecución y cuando se recorre el grafo con BFS, DFS o Algoritmo de ruta más corta de Dijkstra.
- Prefiero un modelo mixto (lista de adyacencia más un conjunto hash de aristas) cuando se necesita una iteración rápida de vecinos y consultas de aristas O(1), a costa de memoria adicional.
Las bibliotecas de gráficos modernas, como NetworkX e igraph, utilizan listas de adyacencia por defecto porque la mayoría de los gráficos del mundo real (redes sociales, mapas de carreteras, páginas web, dependencias de paquetes) son dispersos y requieren mucha navegación.
