1. 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 ntimes n, onde n é 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 O(n^2).

Passo 3

A lista de adjacência armazena, para cada vértice, uma lista de vizinhos. Em um grafo com n vértices e m arestas, o espaço total é da ordem O(n + m), pois há n listas vazias mais referências correspondentes às arestas (em grafos não direcionados, tipicamente 2m referências).

Passo 4

Comparando as duas complexidades, a matriz reserva O(n^2) de espaço independentemente do número de arestas, enquanto a lista cresce apenas com n + m. Em grafos esparsos (quando mll n^2) 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 O(n^2) de memória, enquanto a lista de adjacência usa O(n + m).

Exercícios relacionados