Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais eficiente em uso de memória: matriz de adjacência ou lista de adjacência?
- A) Matriz de adjacência
- B) Matriz de incidência
- C) Tabela hash de arestas
- D) Lista de todos os pares de vértices
- E) Lista de adjacência.
✅ Resposta correta: alternativa E
Resolução passo a passo
- Uma matriz de adjacência de um grafo com V vértices ocupa V^2 posições, independentemente de quantas arestas existam. Num grafo esparso, quase todas essas posições são zero, então o desperdício de memória é grande.
- Uma lista de adjacência guarda, para cada vértice, apenas os vizinhos que ele realmente tem. O espaço usado é da ordem de V + E (uma entrada por vértice e uma por aresta), que é muito menor que V^2 quando E é pequeno em relação a V^2.
- Logo, a lista de adjacência (alternativa E) é a representação mais econômica em memória para o caso descrito, e é o gabarito oficial.
- Por que as outras estão erradas: A) a matriz de adjacência gasta V^2 posições mesmo com poucas arestas; B) a matriz de incidência tem tamanho V x E, que também desperdiça espaço quando há muitos vértices e poucas arestas, e não é a opção mais econômica; C) uma tabela hash de arestas não é uma estrutura padrão de representação de grafos e não traz economia sobre a lista de adjacência; D) uma lista simples de pares de vértices (lista de arestas) também é compacta, mas é uma dúvida legítima: ela usa cerca de E posições, enquanto a lista de adjacência usa V + E, então, em termos estritos, a lista de arestas poderia ser ainda menor. Mesmo assim, a lista de adjacência é a resposta esperada no contexto de provas, porque é a representação padrão que permite acessar os vizinhos de um vértice de forma eficiente, enquanto a lista de pares exige varredura de todas as arestas para isso.
💡 Dica: Considere as características de cada representação de grafo.
Alternativa por alternativa
O aluno acredita que a matriz é sempre a forma mais organizada e compacta, pois ela é a representação clássica de grafos, sem perceber que seu tamanho depende de V^2 e não do número de arestas.
Por que engana: Confundir a eficiência de matriz de adjacência com lista de adjacência em grafos esparsos, escolhendo a matriz por não considerar a quantidade de arestas.
O aluno confunde a matriz de incidência com uma forma mais enxuta de representar as arestas, sem calcular que ela tem dimensões V x E e, portanto, também cresce com o número de vértices.
O aluno supõe que uma tabela hash, por ser uma estrutura eficiente para busca, também é a mais econômica em memória para armazenar grafos esparsos, sem considerar o overhead de espaço da estrutura de hash.
O aluno percebe que listar apenas os pares de arestas economiza espaço, mas não considera que, sem uma organização por vértice, consultar os vizinhos de um vértice exige percorrer toda a lista; ele descarta a própria vantagem de memória da lista de adjacência, cuja diferença é pequena em relação ao ganho de acesso.
Lista de adjacência armazena apenas arestas existentes, com custo de memória O(V+E); matriz de adjacência ocupa O(V^2) independentemente de E, tornando-se ineficiente em grafos esparsos.
Raio-X da questão
representação de grafos
avaliacao
representação de grafos · estrutura de dados
Revisar as diferenças entre matriz de adjacência e lista de adjacência.
Confundir a eficiência de matriz de adjacência com lista de adjacência em grafos esparsos, escolhendo a matriz por não considerar a quantidade de arestas.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- 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 otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
- 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…
- Você tem uma rede social da escola com muitos usuários (nós) e poucas conexões entre eles (arestas). Entre matriz 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