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 conexo com pesos nas arestas, qual propriedade caracteriza uma árvore geradora mínima (MST)?
- Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado conectado e um vértice raiz, construa a…
- Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando…
- Em períodos de calor intenso, o comitê de saúde de uma escola pretende divulgar, antes do recreio, um boletim na rádio…
- Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica…
- — O alerta saiu de Arumã, mas o enlace entre Caju e Ema parou de funcionar — avisou a operadora da central fluvial…
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