- Qual método usa mais espaço, listas de adjacência ou matriz de adjacência e porquê?
Passo 1
O enunciado pede para comparar dois métodos de representação de grafos – lista de adjacência e matriz de adjacência – focando em qual deles usa mais espaço. Vamos usar conceitos de complexidade de espaço.
Passo 2
A matriz de adjacência é uma matriz
, onde
é o número de vértices. Para cada par de vértices há uma entrada que indica presença ou ausência de aresta, resultando em uso de memória de ordem
.
Passo 3
A lista de adjacência armazena, para cada vértice, uma lista de vizinhos. Em um grafo com
vértices e
arestas, o espaço total é da ordem
, pois há
listas vazias mais referências correspondentes às arestas (em grafos não direcionados, tipicamente
referências).
Passo 4
Comparando as duas complexidades, a matriz reserva
de espaço independentemente do número de arestas, enquanto a lista cresce apenas com
. Em grafos esparsos (quando
) a diferença é ainda mais evidente.
Passo 5
Concluímos que a matriz de adjacência consome mais espaço do que a lista de adjacência, especialmente em grafos esparsos, devido ao seu custo quadrático fixo.
Resposta
A matriz de adjacência usa mais espaço, pois ocupa
de memória, enquanto a lista de adjacência usa
.