Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS)…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Utilizar algoritmos clássicos de manipulação sobre listas.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para encontrar o menor caminho em número de arestas entre dois vértices em um grafo representado por listas de adjacência; explique invariantes e complexidade.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Defina registro Visit {v, pred}. Pseudocódigo: inicialize fila Q; marque origem visitada e enfileire( origem, pred = null ). Enquanto Q não vazia: u = desenfileire(); para cada w em adj[u] se não visitado marque visitado, pred[w]=u, enfileire(w); se w==alvo, pare e reconstrua caminho via pred. Invariantes: pred mantém predecessor mínimo em número de arestas; fila processa níveis por ordem crescente de distância. Complexidade: O(V+E) tempo e O(V) espaço para marcações e pred.
Explicação
A descrição do algoritmo apresenta claramente a estrutura de dados necessária, como a fila para a busca em largura e o registro para armazenar os predecessores. As invariantes explicadas garantem que o algoritmo sempre encontra o caminho mais curto em termos de arestas, mantendo a ordem de exploração dos vértices. A análise de complexidade fornece uma visão clara da eficiência do algoritmo em relação ao número de vértices e arestas do grafo.
Raio-X da questão
busca em largura
avaliacao
estruturas de dados · algoritmos de busca
Revisar algoritmos de busca em grafos e suas complexidades.
O aluno pode confundir a busca em largura com a busca em profundidade, aplicando a lógica errada para encontrar o menor caminho.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Um sistema de uma estufa analisa cinco leituras de umidade do solo: 19, 22, 24, 27 e 20. O algoritmo conta as leituras…
- Na montagem de um boletim digital da escola, as seções estão nesta ordem: capa, entrevista, fotos e agenda. A equipe…
- Em um aplicativo da escola, a lista de representantes da turma aparece nesta ordem: Ana, Bia, Caio, Davi e Elisa. Caio…
- Enquanto agentes de manutenção acompanham pedidos de reparo de bicicletas públicas, o painel registra os chamados em uma…
- — O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador…
- — O kit 47 já foi devolvido? — perguntou a técnica responsável pela campanha itinerante de vacinação. Antes do uso de…
🔎 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