Qual é a complexidade temporal do algoritmo BFS em um grafo com V vértices e E arestas quando o grafo é…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual é a complexidade temporal do algoritmo BFS em um grafo com V vértices e E arestas quando o grafo é representado por lista de adjacência?
- A) O(V^2).
- B) O(E log V).
- C) O(E^2).
- D) O(V log V + E).
- E) O(V + E).
✅ Resposta correta: alternativa E
Resolução passo a passo
- O BFS (busca em largura) visita cada vértice uma única vez, colocando-o numa fila e marcando-o como visitado.
- Ao processar cada vértice retirado da fila, o algoritmo percorre sua lista de adjacência, examinando cada aresta. Na soma de todas as listas, cada aresta aparece uma vez (grafo direcionado) ou duas vezes (não direcionado), o que resulta em trabalho proporcional a E.
- Somando o custo de inicializar e enfileirar os V vértices com o custo de examinar as E arestas, obtemos O(V + E).
- Por que as outras estão erradas: A) O(V^2) seria correto para representação por matriz de adjacência, pois percorrer cada linha custa V e são V linhas; aqui a representação é lista. B) O(E log V) aparece em algoritmos que usam fila de prioridade, como Dijkstra com heap, e não no BFS. C) O(E^2) não corresponde a nenhuma etapa do BFS, que examina cada aresta apenas uma vez. D) O termo V log V não surge no BFS, pois não há ordenação nem fila de prioridade envolvida.
- Conclusão: a complexidade temporal do BFS com lista de adjacência é O(V + E), coerente com o gabarito oficial E.
💡 Dica: Reveja a definição de complexidade temporal do algoritmo BFS.
Alternativa por alternativa
O aluno associa BFS à representação por matriz de adjacência, onde verificar os vizinhos de cada vértice custa V, e multiplica por V vértices sem considerar a lista de adjacência.
O aluno transfere para o BFS a complexidade de algoritmos com fila de prioridade, como Dijkstra com heap, supondo que o log V surge da manipulação de vértices.
O aluno supõe que cada aresta precisa ser comparada com todas as outras, multiplicando o custo das arestas entre si, em vez de examinar cada uma uma única vez.
O aluno acredita que o BFS ordena os vértices por algum critério, o que geraria o termo V log V, confundindo a fila de visitação com uma estrutura de ordenação.
Por que engana: Confundir a complexidade do BFS com a de outros algoritmos de busca, como o DFS, levando a uma escolha incorreta da alternativa.
BFS visita cada vértice uma vez e examina cada aresta incidente no máximo duas vezes (uma por extremidade) quando representado por lista de adjacência, resultando em tempo linear em V+E.
Raio-X da questão
complexidade temporal BFS
avaliacao
representacao de grafos · complexidade de algoritmos
Estudar a complexidade temporal de algoritmos em grafos.
Confundir a complexidade do BFS com a de outros algoritmos de busca, como o DFS, levando a uma escolha incorreta 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…
- 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…
- Em um grafo representado por listas de adjacência com n vértices e m arestas, ao executar a busca em largura (BFS), qual…
- Em uma atividade, uma rede é representada por um grafo usando listas de adjacência. Um algoritmo de busca em…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
- Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) 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