Descreva um algoritmo em pseudocódigo que, dado um grafo dirigido acíclico e dois vértices s e t, encontra um…
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
Descreva um algoritmo em pseudocódigo que, dado um grafo dirigido acíclico e dois vértices s e t, encontra um caminho de menor número de arestas entre s e t; explique por que o algoritmo é correto e apresente sua complexidade em termos de n e m.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Pseudocódigo: 1) Inicialize fila Q; marque todos como não visitados; pred[v]=null. 2) Enfileire s, marque visitado[s]=true. 3) Enquanto Q não vazia: u=dequeue(Q); para cada v em adj[u]: se não visitado[v]: visitado[v]=true; pred[v]=u; enqueue(Q); se v==t então pare. 4) Se pred[t]==null não há caminho; senão reconstrua caminho de t a s por pred. Correção: BFS explora por camadas; primeiro momento em que t é descoberto é via menor número de arestas desde s. Complexidade: O(n+m) tempo (cada vértice enfileirado/visitado uma vez e cada aresta examinada uma vez), e O(n) espaço para vetores visitado e pred.
Explicação
O algoritmo utiliza a busca em largura (BFS), que explora todos os vértices a uma determinada distância antes de avançar para a próxima, garantindo que o primeiro caminho encontrado para o vértice t seja o de menor número de arestas. A complexidade O(n + m) reflete a eficiência da BFS em percorrer todos os vértices e arestas do grafo, enquanto o uso de vetores auxiliares para rastrear visitados e predecessores garante um consumo de espaço linear. Assim, o algoritmo é adequado para encontrar o caminho desejado em um grafo dirigido acíclico.
Raio-X da questão
caminho em grafo
avaliacao
algoritmos em pseudocódigo · grafos dirigidos acíclicos
Revisar algoritmos de busca em grafos e suas complexidades.
O aluno pode descrever um algoritmo que não considera a aciclicidade do grafo, resultando em um caminho incorreto.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Os aplicativos de mapa, como o GPS, ajudam o carro de entregas a chegar à casa do cliente. O aplicativo compara dois…
- Lia organiza carrinhos, bonecas e blocos separando cada tipo, colocando-os em caixas e guardando as caixas na…
- Em um jogo, uma personagem controlada por IA precisa chegar a um tesouro sem bater nas paredes. Qual instrução ajuda a…
- Desenhe um algoritmo em pseudocódigo que, dada uma matriz M[N][M] com 0 (livre) e 1 (bloqueado), identifique todas as…
- Em um programa, Substring(codigo, início, quantidade) pega letras do texto a partir da posição indicada, e…
- Projete um algoritmo em pseudocódigo que, dadas as variáveis temperatura (inteiro ºC), ocupacao (inteiro, número 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