A complexidade do espaço de uma estrutura de dados da lista de adjacência é o (v + e) ​​ , onde:

* v é o número de vértices (nós) no gráfico.
* e é o número de arestas no gráfico.

Explicação:

1. vértices: Você precisa armazenar cada vértice no gráfico pelo menos uma vez (por exemplo, em uma matriz, tabela de hash ou alguma outra estrutura que mapeia a lista de seus vizinhos). Isso contribui com o (v) para a complexidade do espaço.

2. arestas: Para cada vértice, você armazena uma lista de seus vértices adjacentes (seus vizinhos). Em uma representação simples, cada borda (ou uma referência/ponteiro para um vizinho) é armazenada uma vez para cada vértice à qual está conectado. Portanto, no total, todas as arestas são armazenadas nas listas.
* Em um gráfico não direcionado , cada borda (u, v) será armazenada duas vezes:uma vez na lista de adjacência de vértice `u` e uma vez na lista de adjacência de vértice` v`. Então, você armazenará efetivamente 2 * e bordas. No entanto, o fator constante (2) é descartado em uma grande notação O, deixando -nos com O (E).
* Em um gráfico direcionado , cada borda (u -> v) é armazenada apenas uma vez, na lista de adjacência do vértice `u`. Então, você armazenará as bordas E, que se traduz em O (E).

Por que o (v + e) ​​é importante:

* gráficos esparsos: Quando E é significativamente menor que V 2 (Um gráfico esparso), a lista de adjacência é muito mais eficiente em termos espaciais que a matriz de adjacência, que tem uma complexidade espacial de O (v 2 ).
* gráficos densos: Quando E está mais perto de V 2 (Um gráfico denso), a complexidade do espaço de ambas as representações se torna semelhante. No entanto, os fatores constantes na implementação ainda podem fazer a diferença.

Exemplo:

Considere um gráfico com 5 vértices (A, B, C, D, E) e 6 arestas:

* A <-> b
* A <-> c
* B <-> C
* B <-> D
* C <-> e
* D <-> e

Aqui, v =5 e e =6.

A lista de adjacência exigiria espaço para:

* Armazenando os 5 vértices (O (v)).
* Armazenando as 12 referências a vizinhos (6 bordas, cada uma armazenada duas vezes porque é um gráfico não direcionado - O (2e) =O (e)).

Portanto, o espaço total é O (V + E) =O (5 + 6) =O (11).

em resumo: As listas de adjacência fornecem uma maneira eficiente de representar gráficos, especialmente gráficos escassos, à medida que sua complexidade espacial escala linearmente com o número de vértices e bordas.