Em um grafo representado por listas de adjacência com n vértices e m arestas, ao executar a busca em largura…
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 um grafo representado por listas de adjacência com n vértices e m arestas, ao executar a busca em largura (BFS), qual é a ordem assintótica do tempo em termos das variáveis n e m?
- A) Tempo O(n^2), considerando que cada vértice é conectado a todos os outros.
- B) Tempo O(m^2) porque m representa o número total de arestas.
- C) Tempo O(log n), considerando estrutura de árvore balanceada para busca.
- D) Tempo O(n) pois ignora a relação com as arestas do grafo.
- E) Tempo O(n + m), onde n = número de vértices e m = número de arestas.
✅ Resposta correta: alternativa E
Resolução passo a passo
- A busca em largura (BFS) visita cada vértice no máximo uma vez, colocando-o na fila e marcando-o como visitado. Isso custa O(n) no total, considerando o trabalho de inicializar e processar todos os vértices.
- Ao remover cada vértice da fila, a BFS percorre sua lista de adjacência para examinar os vizinhos. Como cada aresta aparece nas listas de adjacência (duas vezes em grafo não direcionado, uma vez em grafo direcionado), o total de inspeções das listas é proporcional a m.
- Somando os dois custos, o tempo total é O(n + m). Esta é a complexidade padrão da BFS com listas de adjacência e é a resposta correta, coincidindo com o gabarito oficial.
- A alternativa A está errada, pois O(n^2) só seria adequado com matriz de adjacência ou grafo denso, e não é a complexidade da BFS com listas de adjacência; o fato de cada vértice ligar a todos os outros não é pressuposto do enunciado.
- A alternativa B está errada, pois O(m^2) é um custo que não surge na BFS; a BFS examina cada aresta apenas uma vez por lista de adjacência, não comparando pares de arestas.
- A alternativa C está errada, pois O(log n) corresponde a buscas em árvores balanceadas, enquanto a BFS precisa visitar todos os vértices e arestas, o que impede tempo logarítmico.
- A alternativa D está errada, pois O(n) ignora as arestas, que são inspecionadas durante a expansão de cada vértice; o tempo depende também de m.
💡 Dica: Considere a definição de complexidade de algoritmos.
Alternativa por alternativa
Assume que o grafo é denso e que a estrutura exige comparar todos os pares de vértices, como faria uma matriz de adjacência. Confunde o custo de representação com o custo do algoritmo sobre listas de adjacência.
Por que engana: Confundir a complexidade da busca em largura com a de outros algoritmos, como a busca em profundidade, levando a uma escolha incorreta da alternativa.
Acredita que o número de arestas tem que ser elevado ao quadrado, talvez por confundir a BFS com algoritmos que comparam pares de arestas. Não entende que cada aresta é examinada uma vez por lista de adjacência.
Transfere a intuição de busca binária ou de árvore balanceada para um grafo qualquer. Não percebe que a BFS precisa percorrer todos os vértices e não descarta metade da entrada a cada passo.
Considera apenas o número de vértices, achando que processar cada vértice basta. Esquece que a expansão de cada vértice percorre seus vizinhos, o que depende de m.
BFS visita cada vértice uma vez e percorre todas as arestas adjacentes uma vez ao explorar listas de adjacência, resultando em custo linear em n+m.
Raio-X da questão
busca em largura
avaliacao
complexidade de algoritmos · estruturas de dados
Revisar a complexidade de algoritmos de busca em grafos.
Confundir a complexidade da busca em largura com a de outros algoritmos, como a busca em profundidade, levando a uma escolha incorreta da alternativa.
ciencia_tecnologia
pensamento_critico
abstrato
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 uma atividade, uma rede é representada por um grafo usando listas de adjacência. Um algoritmo de busca em…
- Qual é a complexidade temporal do algoritmo BFS em um grafo com V vértices e E arestas quando o grafo é representado por…
- 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)?
🔎 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