Descreva em pseudocódigo um algoritmo que, dada uma rede representada por um grafo com n nós e lista de…
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 em pseudocódigo um algoritmo que, dada uma rede representada por um grafo com n nós e lista de arestas, verifique se todos os nós são alcançáveis a partir de um nó inicial (ou seja, se a rede é conexa). Explique estruturas de dados usadas e complexidade.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Resposta modelo (exemplo com DFS/BFS): usar lista de adjacência e vetor visitado[n]=falso; usar pilha ou fila. Pseudocódigo (DFS): visitado[] <- falso pilha <- [start] visitado[start]<-verdadeiro enquanto pilha não vazia: u <- desempilhar(pilha) para cada v em adj[u]: se not visitado[v]: visitado[v]<-verdadeiro empilhar(pilha,v) Se todo visitado é verdadeiro então rede é conexa Complexidade: O(n + m) com lista de adjacência (n nós, m arestas). Estruturas: lista de adjacência, vetor booleano visitado, fila/pilha para travessia.
Explicação
O algoritmo utiliza uma abordagem de busca em profundidade (DFS) ou busca em largura (BFS) para explorar todos os nós a partir de um nó inicial, garantindo que todos sejam visitados se a rede for conexa. A lista de adjacência permite representar eficientemente as conexões entre os nós, enquanto o vetor booleano de visitados evita a contagem duplicada de nós. A complexidade O(n + m) reflete a eficiência do algoritmo, onde n é o número de nós e m é o número de arestas, assegurando que cada nó e aresta seja processado uma única vez.
Raio-X da questão
verificação de conectividade em grafos
avaliacao
estruturas de dados em grafos · algoritmos de busca
Revisar algoritmos de busca em profundidade e largura.
O aluno pode descrever um algoritmo que não considera todos os nós do grafo, falhando em verificar a conectividade completa.
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