Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Reconhecer objetos do mundo real e digital que podem ser representados através de grafos que estabelecem uma organização com uma quantidade variável de vértices conectados por arestas, fazendo manipulações simples sobre estas representações.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista de adjacência? Justifique em relação às variáveis V e E.
- A) Matriz de adjacência e lista de adjacência ocupam o mesmo espaço em grafos esparsos.
- B) Lista de adjacência, pois ocupa O(V+E) espaço, enquanto a matriz de adjacência ocupa O(V^2).
- C) A lista de adjacência não consegue armazenar grafos com muitos vértices.
- D) Matriz de adjacência é preferível em grafos esparsos.
- E) Lista de adjacência ocupa O(E) espaço apenas.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Em um grafo com V vértices e E arestas, a matriz de adjacência é uma tabela V x V, logo ocupa O(V^2) de espaço, independentemente de quantas arestas existem. Já a lista de adjacência guarda, para cada vértice, apenas seus vizinhos, o que dá O(V+E) de espaço (um registro por vértice e um por aresta).
- Em uma rede grande e esparsa, E é muito menor que V^2. Assim, V+E é muito menor que V^2, e a lista de adjacência é a escolha que economiza espaço.
- A alternativa B está correta porque expressa exatamente essas duas complexidades e a comparação entre elas, justificando a escolha em função de V e E.
- A alternativa A está errada, pois em grafos esparsos a matriz continua ocupando O(V^2), enquanto a lista ocupa O(V+E), que é bem menor.
- A alternativa C está errada, pois a lista de adjacência não tem limite de vértices pelo próprio método; ela justamente cresce linearmente com V e E.
- A alternativa D está errada, pois a matriz de adjacência desperdiça espaço com muitos zeros em grafos esparsos, sendo preferível apenas em grafos densos.
- A alternativa E está errada, pois a lista de adjacência precisa de O(V+E), e não apenas O(E), já que cada vértice deve ter ao menos uma entrada, mesmo que isolado.
💡 Dica: Considere as características de cada estrutura de dados.
Alternativa por alternativa
Acredita que qualquer representação ocupa a mesma quantidade de memória, ignorando que a matriz sempre armazena V^2 posições.
Por que engana: Confundir a complexidade de espaço entre matriz e lista de adjacência, acreditando que ambas ocupam o mesmo espaço em grafos esparsos.
Em grafos esparsos E « V^2; a lista armazena apenas arestas reais (proporcional a E), já a matriz reserva V^2 entradas independentemente de E, consumindo mais memória.
Supõe que a lista de adjacência tem alguma limitação intrínseca de tamanho ou de número de vértices, confundindo-a com uma estrutura de capacidade fixa.
Associa a matriz à simplicidade de acesso e imagina que ela também é econômica em grafos com poucas arestas, sem perceber que ela armazena muitos zeros.
Confunde o espaço da lista com O(E) puro, esquecendo que cada vértice também precisa de uma entrada na estrutura, inclusive os vértices isolados.
Raio-X da questão
estruturas de dados
avaliacao
estruturas de dados · complexidade de algoritmos
Revisar as diferenças entre matriz e lista de adjacência.
Confundir a complexidade de espaço entre matriz e lista de adjacência, acreditando que ambas ocupam o mesmo espaço em grafos esparsos.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Antes de ir à feira, Bia anotou: pão, bananas e sabonete. Que objeto do dia a dia é esse e como Bia pode mudar a ordem…
- No mapa da sala, há círculos para a porta, a mesa da professora, a estante e o quadro. As linhas ligam porta-mesa…
- — A mensagem não chegou ao abrigo do bairro Serra — avisou uma moradora pelo rádio comunitário. Após a enchente, a…
- — O painel da praça ficou cheio de bilhetes sobre lâmpadas apagadas — observou Caio, voluntário do bairro. Em cada…
- — Quem contracena com Caio? — perguntou a responsável pelo grupo de teatro do bairro. Para organizar os próximos…
- Por que uma mesma caminhada pela área verde pode produzir fichas tão diferentes? Para organizar os registros de…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog