Em um grafo que representa amizades em uma turma (cada aluno é um vértice e cada amizade é uma aresta), cada…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de listas para descrever suas informações e automatizá-las usando uma linguagem de programação, empregando ou não a recursão como uma técnica de resolver o problema.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Em um grafo que representa amizades em uma turma (cada aluno é um vértice e cada amizade é uma aresta), cada aluno tem poucos amigos em relação ao total de alunos. Qual forma de guardar esse grafo no computador ocupa pouca memória e, ao mesmo tempo, permite encontrar rapidamente os amigos de um aluno?
- A) Matriz de adjacência, pois guarda uma tabela com todos os pares possíveis de alunos.
- B) Matriz de incidência, pois cruza cada aluno com cada amizade em uma tabela.
- C) Árvore, pois organiza os alunos em níveis a partir de um aluno principal.
- D) Lista de adjacência, pois guarda para cada aluno apenas a lista dos seus amigos.
- E) Lista de arestas, pois guarda apenas os pares de alunos que são amigos.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Identificar o problema. O grafo é esparso, pois cada aluno tem poucos amigos em relação ao total de alunos. Assim, a representação ideal deve gastar memória proporcional ao número de amizades (arestas) e não ao quadrado do número de alunos, além de permitir consultar os amigos de um aluno com rapidez. Passo 2: Analisar a lista de adjacência. Para cada aluno guarda-se apenas a lista dos seus amigos. O espaço total é proporcional ao número de alunos somado ao número de amizades, o que é pequeno em grafos esparsos. Para encontrar os amigos de um aluno basta acessar a lista dele, sem percorrer o restante do grafo. Passo 3: Por que as outras estão erradas. A) A matriz de adjacência tem uma posição para cada par possível de alunos, ou seja, n por n posições, desperdiçando memória quando quase todas valem zero. B) A matriz de incidência tem uma linha por aluno e uma coluna por amizade, também ocupa muito espaço e não facilita encontrar os vizinhos. C) A árvore é um tipo especial de grafo sem ciclos e não serve como forma geral de guardar qualquer grafo de amizades. E) A lista de arestas gasta pouca memória, mas para descobrir os amigos de um aluno é preciso percorrer todos os pares, o que é lento. Passo 4: Conclusão. A alternativa correta é a D, que coincide com o gabarito oficial.
💡 Dica: Observe que o grafo é esparso e compare a memória ocupada com a facilidade de consultar os vizinhos.
Alternativa por alternativa
Acredita que a matriz de adjacência é eficiente porque organiza todos os pares de alunos em uma tabela, sem perceber que ela ocupa espaço para todos os pares, inclusive os que não são amigos.
Por que engana: Escolher a matriz de adjacência por associá-la a consultas rápidas, sem considerar que ela armazena todos os pares possíveis e desperdiça memória em um grafo esparso.
Imagina que cruzar alunos com amizades em uma tabela economiza memória, sem notar que a matriz de incidência cresce com o número de alunos vezes o número de amizades e não ajuda a localizar vizinhos.
Confunde a estrutura de árvore, que organiza os elementos em níveis, com uma forma geral de representar qualquer grafo, esquecendo que a árvore é um caso particular sem ciclos.
Só as amizades existentes são guardadas (pouca memória) e os amigos de um aluno ficam juntos na lista dele (acesso rápido).
Percebe que a lista de arestas é compacta, mas assume que ela também permite achar rapidamente os amigos de um aluno, quando na verdade é preciso varrer todas as arestas para isso.
Raio-X da questão
Representação de grafos esparsos
avaliacao
Vértices e arestas de grafos · Estruturas de dados básicas
Revise matrizes e listas de representação de grafos, comparando uso de memória e consulta de vizinhos.
Escolher a matriz de adjacência por associá-la a consultas rápidas, sem considerar que ela armazena todos os pares possíveis e desperdiça memória em um grafo esparso.
ciencia_tecnologia
tomada_decisao
cotidiano
Questões parecidas com resolução
- Considere um grafo não direcionado representando amigos. Qual a representação mais adequada para armazená-lo?
- Um grafo tem milhares de vértices, mas cada vértice se liga a poucos outros. Qual estrutura representa esse grafo…
- 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…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
- Analise o uso de um grafo para representar relações de amizade em uma escola. Qual a vantagem dessa estrutura?
- Descreva como você pode representar um grafo para mostrar as amizades entre colegas de classe. Utilize exemplos.
Todas as questões de Programação - Programação com listas e recursão
🔎 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