Carregando...
Carregando...
Carregando...
A implementação de algoritmos de busca em grafos requer uma compreensão detalhada das estruturas de dados e dos passos envolvidos no processo. Na busca em largura (BFS), utilizamos uma fila para garantir que todos os vértices a uma determinada distância sejam visitados antes de se aprofundar mais no grafo. A correta marcação dos vértices é essencial para evitar a visitação redundante e loops infinitos.
Durante a execução de uma busca em largura (BFS), é correto apontar que o principal propósito de utilizar uma fila é de:
Explique melhor esta questão
Abre o Tutor com o enunciado e as alternativas já no campo — você revisa e envia.
Esta questão foi verificada por um de nossos administradores.
🎓 Gabarito Comentado (AVA):
A alternativa “Manter a ordem de descoberta dos vértices, processando primeiro aqueles mais próximos do ponto de origem.” está correta, pois esta é a descrição exata do propósito de utilizar uma fila na BFS. A fila mantém a ordem de descoberta dos vértices, garantindo que aqueles mais próximos do ponto de origem (com menor número de arestas) sejam processados primeiro (First-In, First-Out - FIFO).
As demais alternativas estão incorretas:
A alternativa “Garantir que o vértice mais recentemente descoberto seja processado primeiro, mantendo assim a ordem inversa.” está incorreta, pois esta descrição se alinha mais com o comportamento da pilha utilizada na busca em profundidade (DFS), onde o vértice mais recentemente descoberto é processado primeiro (Last-In, First-Out - LIFO). Na BFS, usamos uma fila.
A alternativa “Facilitar o armazenamento de vértices com maior número de arestas, priorizando vértices mais conectados.” está incorreta, pois o propósito da BFS não é priorizar vértices mais conectados, mas sim manter a ordem de descoberta dos vértices para explorar todos os vértices a uma certa distância antes de avançar para distâncias maiores.
A alternativa “Priorizar a exploração dos vértices com maior peso, focando em caminhos de menor custo total.” está incorreta, pois BFS não considera o peso das arestas. A prioridade é dada apenas à ordem de descoberta e à distância do vértice inicial, não ao peso das arestas. Exploração baseada em peso é característica de algoritmos como Dijkstra.
A alternativa “Permitir a exploração simultânea de múltiplos caminhos no grafo, otimizando a busca por paralelismo.” está incorreta, pois embora BFS explore múltiplos caminhos a partir de um vértice, o propósito principal da fila é garantir a ordem de processamento dos vértices. A busca por paralelismo não é a razão principal para o uso da fila na BFS.