Um grafo tem milhares de vértices, mas cada vértice se liga a poucos outros. Qual estrutura representa esse…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Um grafo tem milhares de vértices, mas cada vértice se liga a poucos outros. Qual estrutura representa esse grafo gastando menos memória?
- A) Matriz de adjacência
- B) Lista de adjacência
- C) Árvore
- D) Pilha
- E) Fila
✅ Resposta correta: alternativa B
Resolução passo a passo
- O enunciado descreve um grafo esparso, ou seja, com milhares de vértices, mas com poucas arestas por vértice. O objetivo é representá-lo gastando o mínimo de memória.
- Uma matriz de adjacência de n vértices ocupa n^2 posições, independentemente de quantas arestas existam. Com milhares de vértices, quase todas as células ficariam vazias (zeros), desperdiçando memória.
- Uma lista de adjacência guarda, para cada vértice, apenas a lista de seus vizinhos. O espaço fica proporcional a n mais m (número de vértices mais número de arestas), o que é muito menor quando o grafo é esparso. Logo, a alternativa correta é a B.
- Por que as outras estão erradas: a matriz de adjacência é justamente a estrutura que desperdiça memória em grafos esparsos; árvore é um tipo especial de grafo (conexo e sem ciclos), não uma forma de representar grafos gerais; pilha é uma estrutura de dados LIFO, sem relação direta com a representação de grafos; fila é uma estrutura FIFO, usada por exemplo na busca em largura, mas não representa a estrutura do grafo.
- Conclusão: concordo com o gabarito oficial, B, pois a lista de adjacência é a representação mais econômica em memória para grafos com muitos vértices e poucas conexões por vértice.
💡 Dica: Compare o espaço ocupado por cada representação quando há poucas arestas em relação ao número de vértices.
Alternativa por alternativa
O aluno acredita que a matriz de adjacência é sempre a melhor forma de representar grafos, por ser a mais simples de construir e consultar, sem considerar o custo de memória de n^2 posições quando o grafo é esparso.
Por que engana: Escolher a matriz de adjacência por associá-la a uma representação mais direta, sem considerar que ela reserva espaço para todos os pares de vértices.
A lista de adjacência guarda só as arestas que existem, então gasta pouca memória quando há poucas ligações.
O aluno confunde o conceito de árvore, um tipo específico de grafo, com uma estrutura de representação de grafos, achando que a palavra 'árvore' se refere a qualquer organização de vértices e conexões.
O aluno associa qualquer estrutura de dados a qualquer problema envolvendo vértices e conexões, sem perceber que a pilha é uma estrutura linear LIFO que não representa conexões entre vértices.
O aluno lembra que a fila aparece em algoritmos de grafos, como a busca em largura, e conclui que ela serve para representar o grafo, quando na verdade é apenas auxiliar no percurso.
Raio-X da questão
Lista de adjacência em grafos
avaliacao
Vértices e arestas de grafos · Representações de estruturas de dados
Revise representações de grafos e o uso de memória em grafos esparsos.
Escolher a matriz de adjacência por associá-la a uma representação mais direta, sem considerar que ela reserva espaço para todos os pares de vértices.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Em um grafo que representa amizades em uma turma (cada aluno é um vértice e cada amizade é uma aresta), cada aluno tem…
- Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas arestas?
- Uma plataforma brasileira de jogos on-line possui 10.000 usuários. Cada usuário mantém conexão, em média, com apenas 50…
- Uma equipe de mobilidade urbana modelou as conexões entre 12.000 pontos de ônibus de uma cidade como um grafo não…
- Ao implementar um grafo não direcionado em código para modelar rotas locais, que estrutura de dado é mais adequada para…
- Uma plataforma brasileira de comunicação pretende representar as relações entre seus usuários. Nessa plataforma, seguir…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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