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
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
- Para modelar conexões entre usuários em uma rede social com milhões de usuários e grau médio pequeno, qual representação…
- Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
- Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…
🔎 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