Em uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a…
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 uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a ordem de exploração dos vértices e por que ela é utilizada?
- A) Array estático
- B) Pilha (LIFO)
- C) Fila (FIFO)
- D) Lista encadeada
- E) Conjunto (Set)
✅ Resposta correta: alternativa C
Resolução passo a passo
- A busca em largura (BFS) visita o grafo por níveis: primeiro o vértice inicial, depois todos os seus vizinhos diretos, depois os vizinhos dos vizinhos, e assim por diante. Para isso, é preciso processar os vértices na ordem em que foram descobertos.
- Essa ordem de descoberta é exatamente o comportamento FIFO (First In, First Out, primeiro a entrar, primeiro a sair) de uma fila. Ao descobrir um vizinho, ele é enfileirado no fim; ao processar, retira-se sempre o vértice do início. Assim, os vértices mais antigos (de nível mais próximo da origem) são explorados antes dos mais recentes.
- Por isso a alternativa C está correta: a fila (FIFO) é a estrutura essencial que garante a exploração por camadas e a menor distância, em número de arestas, a partir do vértice inicial em grafos não ponderados.
- A alternativa A está errada, pois um array estático tem tamanho fixo e não define ordem de processamento por si só.
- A alternativa B está errada, pois a pilha (LIFO) retira o elemento mais recente e produz a busca em profundidade (DFS), não a busca em largura.
- A alternativa D está errada, pois uma lista encadeada é apenas uma forma de armazenamento; ela só serviria para BFS se fosse usada como fila, o que a questão não pede como estrutura essencial.
- A alternativa E está errada, pois um conjunto (Set) não mantém ordem de exploração; ele serve para verificar se um vértice já foi visitado, papel auxiliar e não o que define a ordem.
💡 Dica: Considere a função da estrutura de dados na BFS.
Alternativa por alternativa
Acredita que a estrutura essencial é apenas um vetor de tamanho fixo para guardar os vértices, sem perceber que a ordem de processamento depende de como os elementos são retirados.
Confunde BFS com DFS e assume que a exploração deve usar o último vértice descoberto, como na pilha, o que gera a busca em profundidade.
Por que engana: Confundir a estrutura de dados necessária para a busca em largura com a busca em profundidade, escolhendo uma pilha em vez de uma fila.
A BFS explora vértices por níveis; a fila preserva a ordem de chegada, garantindo que vizinhos de um nível sejam processados antes dos de níveis mais profundos.
Pensa que a lista encadeada é a estrutura necessária porque permite inserções e remoções dinâmicas, sem notar que o que importa é a política de retirada (FIFO), não o tipo de armazenamento.
Acha que o conjunto é o elemento central por guardar os vértices já vistos, ignorando que ele não define a ordem em que os vértices são explorados.
Raio-X da questão
busca em largura
avaliacao
estruturas de dados · grafos
Revisar o funcionamento da busca em largura e suas estruturas de dados.
Confundir a estrutura de dados necessária para a busca em largura com a busca em profundidade, escolhendo uma pilha em vez de uma fila.
ciencia_tecnologia
tomada_decisao
abstrato
Questões parecidas com resolução
- Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados abstrata é…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
- Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
- Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado é usada…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
- No algoritmo de Dijkstra para caminhos mínimos em um grafo com pesos não negativos, qual estrutura de dados é usada 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