Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados abstrata é essencial para controlar a ordem de exploração dos vértices?
- A) Árvore binária
- B) Conjunto (set)
- C) Lista encadeada
- D) Fila (queue).
- E) Pilha (stack)
✅ Resposta correta: alternativa D
Resolução passo a passo
- A busca em largura (BFS) explora o grafo por níveis: primeiro visita o vértice inicial, depois todos os seus vizinhos diretos, depois os vizinhos desses vizinhos, e assim por diante.
- Para que essa ordem seja respeitada, os vértices descobertos precisam ser processados na ordem em que foram encontrados, ou seja, o primeiro a entrar é o primeiro a sair (FIFO).
- Essa disciplina de acesso é exatamente a de uma fila (queue). Ao descobrir um vizinho não visitado, ele é enfileirado; a cada iteração, retira-se o vértice da frente da fila para explorar seus vizinhos.
- Por que as outras estão erradas: a árvore binária é um tipo de grafo/estrutura hierárquica, não um mecanismo de controle de ordem de exploração; o conjunto (set) serve para registrar quais vértices já foram visitados, mas não define a ordem; a lista encadeada é uma forma de armazenar dados e, sozinha, não impõe a ordem FIFO; a pilha (stack) impõe ordem LIFO e é a estrutura usada na busca em profundidade (DFS), não na BFS.
- Conclusão: a alternativa correta é a D, Fila (queue), que coincide com o gabarito oficial.
💡 Dica: Lembre-se da estrutura de dados utilizada em BFS.
Alternativa por alternativa
O aluno confunde a estrutura do grafo com a estrutura auxiliar de controle do algoritmo, imaginando que a árvore binária é o mecanismo que organiza a exploração.
O aluno acredita que, por a BFS precisar saber quais vértices já foram visitados, o conjunto é a estrutura que controla a ordem; ele registra a visita, mas não determina a sequência de exploração.
O aluno pensa que qualquer estrutura de lista serve para a BFS, sem perceber que é preciso uma disciplina específica de acesso (primeiro a entrar, primeiro a sair).
Por que engana: Confundir a estrutura de dados necessária para BFS com a de DFS, escolhendo uma pilha em vez de uma fila.
BFS explora vértices em ordem de chegada; a fila garante comportamento FIFO para visitar primeiro os vértices enfileirados, mantendo a ordem por nível.
O aluno associa pilha a qualquer busca em grafos e não percebe que a pilha (LIFO) produz a busca em profundidade, enquanto a BFS exige a ordem FIFO.
Raio-X da questão
algoritmo BFS
avaliacao
estruturas de dados · algoritmos de busca
Revisar as estruturas de dados utilizadas em algoritmos de busca.
Confundir a estrutura de dados necessária para BFS com a de DFS, escolhendo uma pilha em vez de uma fila.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a ordem de…
- 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