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
- Um sistema portátil registra a corrente gerada em um eletrodo de trabalho durante um pulso de 4 segundos. Para comparar…
- Em um protótipo computacional que monitora a salinidade de um tanque, dois eletrodos ficam imersos na água e são usados…
- Em uma lavanderia, uma pessoa instala dois eletrodos próximos ao piso, ligados a uma entrada digital de um controlador…
- Em uma demonstração de interface cérebro-computador, eletrodos colocados sobre o couro cabeludo captam sinais elétricos…
- Em um protótipo de interface computacional controlada por sinais musculares, cada canal utiliza um eletrodo para captar…
- Em uma prótese controlada por sinais musculares, eletrodos na pele captam a atividade elétrica e a enviam ao sistema…
🔎 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