Para modelar conexões entre usuários em uma rede social com milhões de usuários e grau médio pequeno, qual…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
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 de grafo é mais eficiente: matriz de adjacência ou listas de adjacência? Justifique em termos de espaço.
- A) Lista de pares — é apenas uma coleção de dados e não serve para estruturação de grafos.
- B) Tabela hash — eficiente na busca de vértices, mas não para representação de grafos.
- C) Matriz de adjacência — é sempre mais eficiente, independente da quantidade de arestas.
- D) Listas de adjacência — consomem O(V+E) espaço, adequadas a grafos esparsos.
- E) Array bidimensional — mesmo espaço, mas não permite manipulação eficiente de grafos.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Em uma rede social com milhões de usuários (V muito grande) e grau médio pequeno, o número de conexões E é muito menor que V^2, ou seja, o grafo é esparso.
- A matriz de adjacência ocupa V x V posições, isto é, O(V^2) de espaço, independentemente de quantas conexões existem. Com milhões de usuários, isso gera bilhões de células, quase todas vazias (zeros).
- A lista de adjacências guarda, para cada vértice, apenas seus vizinhos. O espaço total é O(V+E), que é proporcional ao número real de usuários e conexões. Por isso é a escolha adequada para grafos esparsos.
- Analisando as alternativas: A está errada, porque a lista de pares é sim uma forma válida de representar arestas, e a lista de adjacências é apenas uma organização dela. B está errada, porque a tabela hash não é a representação de grafo discutida, embora possa ser usada internamente para buscar vizinhos. C está errada, pois a matriz de adjacência só é vantajosa em grafos densos e não é sempre mais eficiente, já que gasta O(V^2) mesmo com poucas arestas. E está errada, porque um array bidimensional é justamente a matriz de adjacência, com o mesmo espaço O(V^2) e desperdício em grafos esparsos.
- Conclusão: a alternativa D é correta e coincide com o gabarito oficial, pois as listas de adjacência usam O(V+E) de espaço e são indicadas para grafos esparsos como redes sociais.
💡 Dica: Considere as características de cada representação de grafo.
Alternativa por alternativa
O aluno acredita que uma lista de pares não representa grafos, quando na verdade ela é uma forma válida de guardar as arestas, apenas menos organizada para consultar vizinhos.
O aluno confunde a estrutura de dados usada para busca rápida de elementos com a representação de conexões entre vértices, achando que a tabela hash não pode servir a grafos.
O aluno acredita que a matriz de adjacência é sempre a melhor opção, ignorando que ela ocupa O(V^2) de espaço mesmo quando há poucas arestas, o que é desperdício em grafos esparsos.
Por que engana: Confundir a eficiência de matriz de adjacência com listas de adjacência em grafos esparsos, acreditando que a matriz é sempre a melhor opção.
Em grafos esparsos (muitos vértices, poucas arestas por vértice) listas armazenam apenas arestas existentes; matriz de adjacência usa O(V²), tornando-se inviável em grande escala.
O aluno considera que o array bidimensional é outra estrutura distinta da matriz de adjacência, sem perceber que ele é exatamente a forma de implementar a matriz, com o mesmo custo O(V^2) de espaço.
Raio-X da questão
representação de grafos
avaliacao
representação de grafos · complexidade de algoritmos
Revisar as diferenças entre matriz de adjacência e listas de adjacência.
Confundir a eficiência de matriz de adjacência com listas de adjacência em grafos esparsos, acreditando que a matriz é sempre a melhor opção.
ciencia_tecnologia
pensamento_critico
cientifico
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…
- Você tem uma rede social da escola com muitos usuários (nós) e poucas conexões entre eles (arestas). Entre matriz de…
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
- Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
🔎 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