Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos memória: matriz de adjacência ou lista de adjacência? Justifique citando a complexidade de espaço.
- A) Lista de adjacência; consome O(N+E) memória, enquanto a matriz usa O(N^2), sendo a lista mais eficiente quando E << N^2.
- B) A lista de adjacência é sempre mais lenta que a matriz.
- C) Ambas as representações consomem a mesma quantidade de memória.
- D) A matriz de adjacência é mais eficiente para grafos esparsos.
- E) A matriz de adjacência consome O(N).
✅ Resposta correta: alternativa A
Resolução passo a passo
- Uma matriz de adjacência de N vértices é uma tabela N x N, então ocupa O(N^2) de memória, independentemente de quantas arestas existam. Passo 2: Uma lista de adjacência guarda, para cada vértice, apenas a lista dos seus vizinhos. Há N listas (O(N)) e, em um grafo não direcionado, cada aresta aparece duas vezes, totalizando O(N+E) de memória. Passo 3: Em um grafo esparso, E é muito menor que N^2, logo O(N+E) é muito menor que O(N^2) e a lista de adjacência é a opção que consome menos memória. Passo 4: Justificativa das alternativas erradas: a alternativa B está errada porque a lista não é sempre mais lenta, pois para percorrer os vizinhos de um vértice ela é mais rápida que a matriz; a alternativa C está errada porque as complexidades de espaço diferem substancialmente em grafos esparsos; a alternativa D está errada porque a matriz desperdiça memória com muitas posições zeradas em grafos esparsos; a alternativa E está errada porque a matriz usa O(N^2), não O(N), já que armazena todas as combinações de pares de vértices.
💡 Dica: Compare as complexidades de espaço das duas representações.
Alternativa por alternativa
A matriz armazena N×N entradas independentes do número de arestas; a lista registra apenas vértices existentes por aresta, reduzindo espaço em grafos esparsos.
O aluno associa a representação por lista a um custo maior de acesso e conclui que ela é sempre lenta, ignorando que percorrer os vizinhos de um vértice é mais eficiente na lista.
O aluno acredita que, como ambas representam o mesmo grafo, precisam ocupar o mesmo espaço, sem comparar como cada estrutura cresce com N e E.
O aluno pensa que a matriz, por ter acesso direto O(1) às arestas, é mais econômica, sem perceber que ela reserva espaço para pares de vértices que não estão conectados.
Por que engana: Confundir a eficiência de memória entre a lista de adjacência e a matriz de adjacência, escolhendo a matriz como a opção mais eficiente.
O aluno confunde a quantidade de vértices com o tamanho da matriz, supondo que ela cresce apenas linearmente com N, quando na verdade precisa de N linhas e N colunas.
Raio-X da questão
representação de grafos
avaliacao
complexidade de espaço · representação de grafos
Revisar as representações de grafos e suas complexidades de espaço.
Confundir a eficiência de memória entre a lista de adjacência e a matriz de adjacência, escolhendo a matriz como a opção mais eficiente.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…
- Para modelar conexões entre usuários em uma rede social com milhões de usuários e grau médio pequeno, qual representação…
- Ao projetar um algoritmo que processa um grafo de amizades de estudantes, qual estrutura de dado é preferível para…
🔎 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