Qual estrutura de dados é mais indicada para representar um grafo em um programa?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual estrutura de dados é mais indicada para representar um grafo em um programa?
- A) Lista encadeada
- B) Array unidimensional
- C) Lista de adjacência
- D) Árvore binária
- E) Tabela hash
✅ Resposta correta: alternativa C
Resolução passo a passo
- Um grafo é formado por vértices (nós) e arestas que ligam pares de vértices. Ao representá-lo em um programa, a estrutura precisa armazenar, para cada vértice, quais vértices são seus vizinhos, de forma eficiente em memória e em tempo de consulta.
- A lista de adjacência associa a cada vértice uma lista com seus vizinhos imediatos. Ela ocupa espaço proporcional ao número de vértices mais o número de arestas (O(V+E)), o que é ideal para grafos esparsos, que são a maioria dos casos práticos. Percorrer os vizinhos de um vértice é direto.
- Por que as outras estão erradas: A) a lista encadeada é uma estrutura linear e não representa diretamente as conexões múltiplas entre vértices de um grafo; B) o array unidimensional guarda apenas uma sequência de valores e não consegue expressar as relações entre pares de vértices sem uma estrutura adicional; D) a árvore binária é um caso particular de grafo acíclico com restrições de hierarquia (cada nó tem no máximo dois filhos), portanto não serve como representação geral de grafos; E) a tabela hash é útil para buscas por chave, mas não organiza naturalmente as arestas entre vértices.
- Conclusão: a lista de adjacência é a estrutura mais indicada para representar grafos de forma geral e eficiente, e coincide com o gabarito oficial. A matriz de adjacência também representa grafos, mas não foi oferecida entre as alternativas e costuma desperdiçar memória em grafos esparsos.
💡 Dica: Associe a estrutura à representação dos vértices e de suas conexões.
Alternativa por alternativa
Confunde o grafo com uma sequência linear de elementos, achando que basta encadear os vértices um após o outro para representar todas as conexões. A lista encadeada não expressa naturalmente as múltiplas ligações entre vértices.
Por que engana: Confundir estruturas gerais, como listas ou árvores, com uma representação que organiza diretamente as conexões entre os vértices de um grafo.
Acredita que um único vetor de posições consegue guardar todas as relações entre vértices, sem perceber que o array unidimensional armazena apenas uma sequência de valores, sem indicar ligações entre pares.
Uma lista de adjacência registra, para cada vértice, os vértices ligados a ele.
Associa a estrutura de grafos a qualquer estrutura de nós e ligações, esquecendo que a árvore binária é um grafo acíclico com restrição de até dois filhos por nó e não serve como representação geral.
Pensa que, por a tabela hash permitir acesso rápido a informações associadas a chaves, ela seria a melhor forma de guardar as arestas. Porém, ela não organiza naturalmente a relação entre vértices vizinhos.
Raio-X da questão
Representação de grafos
avaliacao
Conceito de vértices e arestas · Estruturas de dados básicas
Revise como listas de adjacência registram as conexões entre vértices de um grafo.
Confundir estruturas gerais, como listas ou árvores, com uma representação que organiza diretamente as conexões entre os vértices de um grafo.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas arestas?
- Qual das seguintes estruturas de dados é mais adequada para representar um grafo não direcionado?
- Para resolver um problema utilizando grafos, qual estrutura de dados é mais adequada para implementar listas de…
- Identifique qual estrutura de dados é mais adequada para representar uma rede social em um programa.
- Identifique a estrutura de dados mais adequada para representar uma rede social, onde cada usuário é um nó e as conexões…
- Qual das seguintes estruturas de dados é mais eficiente para adicionar um novo nó em um grafo?
🔎 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