Em uma implementação de busca em largura (BFS) em grafos, qual estrutura de dados é essencial para manter a…

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?

1. A) Array estático
2. B) Pilha (LIFO)
3. C) Fila (FIFO)
4. D) Lista encadeada
5. E) Conjunto (Set)

✅ Resposta correta: alternativa C

Resolução passo a passo

1. 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.
2. 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.
3. 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.
4. A alternativa A está errada, pois um array estático tem tamanho fixo e não define ordem de processamento por si só.
5. 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.
6. 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.
7. 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

Raio-X da questão

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…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.