Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado representado por listas de…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado representado por listas de adjacência, compute o número de componentes conexas. Indique as variáveis-chave e a complexidade temporal.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Pseudocódigo: visited[v]=false for all v components=0 for v in V: if not visited[v]: components+=1 stack=[v] while stack: u=stack.pop() if not visited[u]: visited[u]=true for w in adj[u]: if not visited[w]: stack.push(w) return components Variáveis-chave: visited[], stack (ou fila), components, adj. Complexidade: O(n + m) considerando n vértices e m arestas.
Explicação
O algoritmo utiliza uma abordagem de busca em profundidade (DFS) para explorar todos os vértices de um grafo, marcando-os como visitados. Cada vez que um novo vértice não visitado é encontrado, uma nova componente conexa é identificada, incrementando o contador. A complexidade O(n + m) reflete a necessidade de visitar todos os vértices e arestas, garantindo que todas as partes do grafo sejam consideradas.
Raio-X da questão
componentes conexas de grafos
avaliacao
listas de adjacência · algoritmos de busca
Revisar conceitos de grafos e algoritmos de busca.
O aluno pode confundir a contagem de componentes conexas com a contagem de vértices ou arestas, resultando em um número incorreto.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Um sistema de irrigação segue o esquema: leia a umidade do solo; se umidade < 30, ligue a água; caso contrário…
- Em um laboratório de análise de sementes, dois programas escritos na mesma linguagem processam registros. O programa P…
- Em uma incubadora usada em pesquisas científicas, um sensor mede a temperatura. A equipe considera adequada uma leitura…
- Em uma barraca de feira, cada suco custa R$ 5. Uma cliente escolhe uma quantidade de sucos, representada pela variável…
- Quatro colegas vão planejar um aplicativo simples para organizar os estudos do grupo. O aplicativo deve mostrar as…
- — A ponte do rio ficou interditada; a lancha terá de mudar o trajeto — informou a central de defesa civil. Para levar…
🔎 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