Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas…

Questão

Qual das estruturas de dados abaixo é mais adequada para representar um grafo com muitos vértices e poucas arestas?

1. A) Matriz de Adjacência
2. B) Lista de Adjacência
3. C) Lista Dupla
4. D) Árvore
5. E) Vetores

✅ Resposta correta: alternativa B

Resolução passo a passo

1. Em um grafo com muitos vértices e poucas arestas, a maioria das combinações possíveis de pares de vértices não tem aresta. Assim, a representação deve gastar espaço proporcional ao número de arestas, não ao quadrado do número de vértices. Passo 2: A Lista de Adjacência guarda, para cada vértice, apenas a lista dos seus vizinhos. O espaço usado é da ordem de V + E (vértices mais arestas), o que é muito econômico quando E é pequeno. Passo 3: Consultar se existe aresta entre dois vértices fica mais lento que na matriz, mas percorrer os vizinhos de um vértice é rápido, e isso costuma ser a operação mais frequente em algoritmos sobre grafos esparsos. Passo 4: Por que as outras estão erradas: a Matriz de Adjacência ocupa V^2 posições mesmo quando há poucas arestas, o que desperdiça memória; a Lista Dupla não é uma forma padrão de representar grafos, sendo apenas uma estrutura linear com ponteiros para frente e para trás; a Árvore é um caso particular de grafo, conectado e sem ciclos, com apenas V-1 arestas, e não serve como estrutura geral para representar qualquer grafo; Vetores, sozinhos, não indicam quais vértices são conectados, e só ganham sentido quando usados para montar listas de adjacência. Passo 5: Conclusão: a alternativa correta é a B, Lista de Adjacência, que é a estrutura mais adequada para grafos esparsos, com gabarito concordando com a resolução.

💡 Dica: Considere as características dos grafos ao escolher a estrutura.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Um sistema portátil registra a corrente gerada em um eletrodo de trabalho durante um pulso de 4 segundos. Para comparar…
• Em um protótipo computacional que monitora a salinidade de um tanque, dois eletrodos ficam imersos na água e são usados…
• Em uma lavanderia, uma pessoa instala dois eletrodos próximos ao piso, ligados a uma entrada digital de um controlador…
• Em uma demonstração de interface cérebro-computador, eletrodos colocados sobre o couro cabeludo captam sinais elétricos…
• Em um protótipo de interface computacional controlada por sinais musculares, cada canal utiliza um eletrodo para captar…
• Em uma prótese controlada por sinais musculares, eletrodos na pele captam a atividade elétrica e a enviam ao sistema…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.