Em uma atividade, uma rede é representada por um grafo usando listas de adjacência. Um algoritmo de busca em…
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
Em uma atividade, uma rede é representada por um grafo usando listas de adjacência. Um algoritmo de busca em profundidade (DFS) visita os vértices e percorre as arestas para explorar toda a rede. Qual é a complexidade temporal da DFS, considerando n vértices e m arestas nesse tipo de representação?
- A) A complexidade temporal é O(n + m).
- B) A complexidade temporal é O(nm).
- C) A complexidade temporal é O(m).
- D) A complexidade temporal é O(n).
- E) A complexidade temporal é O(m²).
✅ Resposta correta: alternativa A
Resolução passo a passo
- A DFS visita cada vértice uma vez, o que custa O(n), pois cada vértice é marcado como visitado e processado no máximo uma vez.
- Com listas de adjacência, a DFS percorre a lista de cada vértice, e a soma dos tamanhos de todas as listas é igual a 2m em grafos não direcionados (ou m em grafos direcionados). Logo, o percurso de todas as arestas custa O(m).
- Somando as duas partes, o custo total é O(n + m), que é a resposta correta, alternativa A, e coincide com o gabarito oficial.
- A alternativa B está errada porque O(nm) seria o custo típico de uma representação por matriz de adjacência com varredura de linhas, e não o da DFS com listas de adjacência, que é linear no tamanho do grafo.
- A alternativa C está errada porque ignora a visita aos n vértices; mesmo um grafo sem arestas exige O(n) para a DFS percorrer todos os vértices.
- A alternativa D está errada porque ignora o custo de percorrer as arestas, que cresce com m e não é limitado por n em grafos densos.
- A alternativa E está errada porque O(m^2) é um custo quadrático em m, que não corresponde ao trabalho de examinar cada aresta uma vez por visita, sendo muito superior ao necessário.
💡 Dica: Considere a definição de complexidade de algoritmos.
Alternativa por alternativa
Com listas de adjacência, a DFS visita cada vértice no máximo uma vez e percorre cada aresta um número constante de vezes. Por isso, o tempo total é proporcional à soma do número de vértices e de arestas: O(n + m).
O aluno pode ter associado a DFS ao produto de vértices por arestas, como se para cada vértice fosse necessário reexaminar todas as arestas do grafo.
Por que engana: Confundir a complexidade de busca em profundidade com a de outros algoritmos, como o de Dijkstra, levando a uma escolha errada da alternativa.
O aluno considerou apenas o custo de percorrer as arestas e esqueceu que cada um dos n vértices precisa ser visitado e marcado, mesmo quando há poucas arestas.
O aluno pensou que a complexidade depende apenas do número de vértices, talvez por associar a busca somente à quantidade de nós visitados e ignorar o custo de explorar cada conexão.
O aluno supôs que percorrer as arestas exigiria comparar cada par de arestas entre si, confundindo a exploração linear de adjacências com um cálculo quadrático.
Raio-X da questão
complexidade de algoritmos
avaliacao
complexidade de algoritmos · busca em profundidade
Revisar a complexidade temporal de algoritmos de busca em grafos.
Confundir a complexidade de busca em profundidade com a de outros algoritmos, como o de Dijkstra, levando a uma escolha errada da alternativa.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- 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…
- 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…
- Qual é a complexidade temporal do algoritmo BFS em um grafo com V vértices e E arestas quando o grafo é representado por…
- Uma equipe de estudantes está analisando uma rede simples de quatro estações de monitoramento. Cada estação pode estar…
- Descreva um algoritmo, indicando as variáveis-chave e os passos, para identificar todos os vértices de articulação (cut…
🔎 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