Considere um grafo não direcionado representando amigos. Qual a representação mais adequada para armazená-lo?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Considere um grafo não direcionado representando amigos. Qual a representação mais adequada para armazená-lo?
- A) Matriz de Adjacência
- B) Lista de Adjacência
- C) Tabela Hash
- D) Árvore
- E) Conjunto
✅ Resposta correta: alternativa B
Resolução passo a passo
- Identifique o problema. Um grafo não direcionado de amigos é uma rede social: cada pessoa é um vértice e cada amizade é uma aresta sem sentido, pois se Ana é amiga de Bruno, Bruno também é amigo de Ana. Em redes reais, cada pessoa tem poucos amigos em relação ao total de pessoas, ou seja, o grafo é esparso. Passo 2: Compare as estruturas. A matriz de adjacência usa n x n posições, mesmo quando há poucas arestas, o que desperdiça memória; além disso, para listar os amigos de alguém é preciso varrer uma linha inteira. A lista de adjacência guarda, para cada vértice, apenas a lista dos seus vizinhos, ocupando espaço proporcional ao número de vértices mais o de arestas, e permite percorrer os amigos de uma pessoa diretamente. Passo 3: Conclusão. A lista de adjacência é a representação mais adequada, por ser econômica em grafos esparsos e eficiente para consultar os amigos de cada pessoa. Passo 4: Por que as outras estão erradas. A matriz de adjacência funciona, mas desperdiça memória em grafos esparsos como uma rede de amizades. A tabela hash é uma estrutura de busca por chave e não representa, por si só, as conexões entre vértices. A árvore é um grafo acíclico e conexo, por isso não serve para representar uma rede geral de amizades, que pode ter ciclos. O conjunto guarda elementos sem relações entre eles, então não representa as arestas do grafo.
💡 Dica: Considere as estruturas de dados adequadas para grafos.
Alternativa por alternativa
Acredita que a matriz de adjacência é sempre a melhor forma por ser a representação clássica de grafos, sem considerar que o número de amizades é pequeno em relação ao total e que a matriz desperdiça espaço com posições vazias.
Por que engana: Confundir a aplicabilidade da matriz de adjacencia e lista de adjacencia, escolhendo matriz mesmo para grafos esparsos.
Representa de forma eficiente um grafo não direcionado, economizando espaço.
Confunde a tabela hash, que serve para busca rápida por chave, com uma forma de representar as conexões entre vértices de um grafo.
Associa a árvore a qualquer estrutura de dados e supõe que uma rede de amizades pode ser representada por ela, ignorando que árvores não têm ciclos e que redes de amizade costumam tê-los.
Lê a questão apenas como a necessidade de guardar um grupo de pessoas e esquece que o grafo precisa registrar as relações de amizade entre elas.
Raio-X da questão
representação de grafos
avaliacao
representacao de grafos · estruturas de dados basicas
Revisar as estruturas de dados para representação de grafos.
Confundir a aplicabilidade da matriz de adjacencia e lista de adjacencia, escolhendo matriz mesmo para grafos esparsos.
pensamento_critico
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 seguintes estruturas de dados é mais adequada para representar um grafo não direcionado?
- Identifique a estrutura de dados mais adequada para representar as relações entre amigos em uma rede social.
- Identifique a estrutura de dados mais adequada para representar uma rede social, onde cada usuário é um nó e as conexões…
- Na aula, a turma analisou uma rede de amizades. Cada pessoa foi representada como um elemento, e uma ligação foi…
- Analise a situação em que você deve escolher uma estrutura de dados para representar a relação entre amigos. Qual seria…
Todas as questões de Organização e representação da informaçã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