Qual é a complexidade temporal do algoritmo de busca em largura (BFS) em um grafo representado por listas de…
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 de busca em largura (BFS) em um grafo representado por listas de adjacência, em função de n vértices e m arestas?
- A) O algoritmo BFS tem complexidade O(n^2), sendo quadrática em relação aos vértices.
- B) BFS opera com complexidade O(n * m), indicando uma relação multiplicativa entre vértices e arestas.
- C) No BFS, a complexidade é proporcional ao número de ciclos no grafo.
- D) O(n + m) — linear no número de vértices mais arestas.
- E) A complexidade do BFS é O(1), pois não considera arestas ou vértices.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Lembre como funciona a busca em largura. O algoritmo começa em um vértice de origem, coloca-o em uma fila e, enquanto a fila não estiver vazia, retira um vértice e examina seus vizinhos, enfileirando os que ainda não foram visitados.
- Conte o trabalho realizado. Cada vértice entra na fila no máximo uma vez, o que custa um total proporcional a n (número de vértices). Ao retirar um vértice, percorre-se sua lista de adjacência; como cada aresta aparece nas listas de adjacência de seus extremos (duas vezes no grafo não orientado, uma vez no orientado), a soma de todos os percursos das listas é proporcional a m (número de arestas).
- Some os custos. O tempo total é proporcional a n + m, ou seja, O(n + m), que é a alternativa D. Esta é a complexidade usual do BFS com lista de adjacência.
- Analise as demais alternativas. A) está errada, pois O(n^2) só surgiria com matriz de adjacência ou algo equivalente, não com listas de adjacência. B) está errada, pois O(n * m) é um custo multiplicativo que não corresponde ao que o algoritmo faz, já que cada aresta é examinada uma vez por extremo. C) está errada, pois a complexidade depende de vértices e arestas, não do número de ciclos. E) está errada, pois O(1) é impossível, já que o algoritmo precisa ao menos ler os vértices e arestas do grafo.
- Conclusão. A resposta correta é a alternativa D, que coincide com o gabarito oficial.
💡 Dica: Considere a definição de complexidade de algoritmos.
Alternativa por alternativa
Assume que a busca precisa comparar todos os pares de vértices, como ocorre com a matriz de adjacência, e não percebe que a lista de adjacência permite percorrer apenas as arestas existentes.
Por que engana: Confundir a complexidade do BFS com a de outros algoritmos, como o DFS, levando a uma escolha incorreta da alternativa.
Acredita que, para cada vértice processado, é necessário percorrer todas as arestas do grafo, gerando um produto entre n e m em vez de uma soma.
Associa a complexidade à estrutura de ciclos do grafo, confundindo a presença de ciclos com o número de operações realizadas pelo algoritmo.
BFS visita cada vértice uma vez e percorre cada aresta no máximo uma vez nas listas de adjacência, resultando em O(n + m).
Imagina que a busca pode ser feita sem examinar o grafo, talvez por confundir a complexidade de acessar um único vértice com a de percorrer o grafo inteiro.
Raio-X da questão
complexidade temporal BFS
avaliacao
algoritmos de busca · listas de adjacência
Revisar a complexidade de algoritmos de busca em grafos.
Confundir a complexidade do BFS com a de outros algoritmos, como o DFS, levando a uma escolha incorreta da alternativa.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em um grafo representado por listas de adjacência com n vértices e m arestas, ao executar a busca em largura (BFS), qual…
- 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…
- 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…
- Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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