* V es el número de vértices (nodos) en el gráfico.
* e es el número de bordes en el gráfico.
Explicación:
1. Vértices: Debe almacenar cada vértice en el gráfico al menos una vez (por ejemplo, en una matriz, tabla hash o alguna otra estructura que se asigna a la lista de sus vecinos). Esto contribuye a O (V) a la complejidad del espacio.
2. Bordes: Para cada vértice, almacena una lista de sus vértices adyacentes (sus vecinos). En una representación simple, cada borde (o una referencia/puntero a un vecino) se almacena una vez para cada vértice al que está conectado. Por lo tanto, en total, todos los bordes se almacenan en las listas.
* En un gráfico no dirigido , cada borde (u, v) se almacenará dos veces:una vez en la lista de adyacencia de Vértice `U` y una vez en la lista de adyacencia de Vértice` V`. Por lo tanto, almacenará efectivamente 2 * E bordes. Sin embargo, el factor constante (2) se cae en la notación grande o, dejándonos con o (e).
* En un gráfico dirigido , cada borde (u -> v) se almacena solo una vez, en la lista de adyacencia de Vértice `U`. Entonces almacenará E bordes, lo que se traduce en O (E).
por qué o (v + e) es importante:
* gráficos escasos: Cuando E es significativamente más pequeño que V
* gráficos densos: Cuando E está más cerca de V
Ejemplo:
Considere un gráfico con 5 vértices (A, B, C, D, E) y 6 bordes:
* A <-> B
* A <-> C
* B <-> c
* B <-> D
* C <-> e
* D <-> E
Aquí, V =5 y E =6.
La lista de adyacencia requeriría espacio para:
* Almacenamiento de los 5 vértices (O (V)).
* Almacenamiento de las 12 referencias a los vecinos (6 bordes, cada uno almacenado dos veces porque es un gráfico no dirigido - O (2e) =O (e)).
Por lo tanto, el espacio total es O (V + E) =O (5 + 6) =O (11).
En resumen: Las listas de adyacencia proporcionan una forma eficiente en el espacio de representar gráficos, especialmente gráficos dispersos, ya que su complejidad espacial escala linealmente con el número de vértices y bordes.