Se um grafo é representado por lista de adjacência com V vértices e E arestas, qual a complexidade em notação…
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
Se um grafo é representado por lista de adjacência com V vértices e E arestas, qual a complexidade em notação O de um algoritmo que visita cada vértice e percorre cada aresta uma vez (por exemplo, DFS)?
- A) O(V + E^2)
- B) O(V + E).
- C) O(V * E)
- D) O(E^2)
- E) O(V^2)
✅ Resposta correta: alternativa B
Resolução passo a passo
- Na representação por lista de adjacência, cada vértice tem uma lista com seus vizinhos. Assim, o grafo ocupa espaço proporcional a V (uma entrada por vértice) mais E (cada aresta aparece nas listas dos seus extremos).
- Um algoritmo que visita cada vértice uma vez realiza V operações de visita, cada uma com custo constante de marcação e controle.
- Um algoritmo que percorre cada aresta uma vez, ao percorrer as listas de adjacência, realiza E operações de verificação, cada uma com custo constante.
- Somando os dois custos, o total de operações é proporcional a V + E, o que se escreve O(V + E). Esse é o gabarito, e a resposta correta é a alternativa B.
- Por que as outras estão erradas: A) O(V + E^2) superestima o custo, pois E^2 só apareceria se cada aresta fosse percorrida muitas vezes. C) O(V * E) também superestima, pois multiplica os custos em vez de somá-los. D) O(E^2) ignora o custo dos vértices e não corresponde a um percurso que toca cada aresta uma única vez. E) O(V^2) seria típico de uma representação por matriz de adjacência, que não é a representação do enunciado.
💡 Dica: Considere a definição de complexidade de algoritmos.
Alternativa por alternativa
O aluno acredita que cada aresta exige um trabalho quadrático em E, confundindo o custo de percorrer arestas com o de comparar pares de arestas.
Por que engana: Confundir a complexidade de percorrer arestas com a de um algoritmo que visita vértices, resultando em uma notação O incorreta.
Cada vértice é processado uma vez e cada aresta é percorrida no máximo uma vez ao iterar as listas de adjacência, somando O(V)+O(E).
O aluno multiplica o número de vértices pelo número de arestas, imaginando que o custo de cada visita depende de todas as arestas, em vez de somar os trabalhos separados.
O aluno considera que o algoritmo precisa comparar todas as arestas entre si, e assim associa o custo somente a E^2, sem contar os vértices.
O aluno associa o custo à representação por matriz de adjacência, que é quadrática em V, e não à lista de adjacência descrita no enunciado.
Raio-X da questão
complexidade de algoritmos
avaliacao
notação O · grafos e algoritmos
Revisar a complexidade de algoritmos em grafos.
Confundir a complexidade de percorrer arestas com a de um algoritmo que visita vértices, resultando em uma notação O incorreta.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Qual é a complexidade temporal do algoritmo BFS em um grafo com V vértices e E arestas quando o grafo é representado por…
- Em uma atividade, uma rede é representada por um grafo usando listas de adjacência. Um algoritmo de busca em…
- Qual é a complexidade temporal do algoritmo de busca em largura (BFS) em um grafo representado por listas de adjacência…
- Em um grafo representado por listas de adjacência com n vértices e m arestas, ao executar a busca em largura (BFS), qual…
- Dado um grafo representado por lista de adjacência, qual é a complexidade para verificar se existe aresta entre os…
- Em um grafo não direcionado representado por lista de adjacência, que variável e que operação um algoritmo deve usar…
🔎 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