Escreva um pseudocódigo que, dado um grafo não orientado representado por lista de adjacência, retorne o…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Utilizar conceitos iniciais de uma linguagem de programação na implementação de algoritmos escritos em linguagem corrente e/ou matemática.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Escreva um pseudocódigo que, dado um grafo não orientado representado por lista de adjacência, retorne o número de componentes conectados. Explique brevemente a lógica e a complexidade temporal.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Pseudocódigo (entrada: adj lista G): 1. visited ? conjunto vazio 2. componentes ? 0 3. para cada vértice v em G: 4. se v ? visited: 5. componentes ? componentes + 1 6. realizar DFS/ BFS a partir de v: fila/stack ? [v]; marcar v como visited 7. enquanto fila/stack não vazia: 8. u ? remover(fila/stack) 9. para cada w em G[u]: 10. se w ? visited: marcar w; inserir w em fila/stack 11. retornar componentes Lógica: percorre todos os vértices; a cada início de busca em vértice não visitado encontra uma nova componente. Complexidade: usando lista de adjacência, cada vértice e cada aresta são processados no máximo uma vez, logo O(n + m).
Explicação
O pseudocódigo utiliza uma abordagem de busca em profundidade (DFS) ou busca em largura (BFS) para explorar todos os vértices de um grafo, contando quantas vezes inicia uma nova busca a partir de um vértice não visitado, o que indica a descoberta de uma nova componente conectada. A complexidade O(n + m) reflete que cada vértice e cada aresta são analisados uma única vez, garantindo eficiência na contagem das componentes. Essa metodologia é fundamental para entender a estrutura de conexões em grafos não orientados.
Raio-X da questão
componentes conectados em grafos
avaliacao
grafos e suas representações · pseudocódigo e algoritmos
Revisar algoritmos de busca em grafos e suas complexidades.
O aluno pode confundir a contagem de componentes conectados com a contagem de arestas ou vértices, resultando em uma resposta incorreta.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Descreva e escreva em pseudocódigo um algoritmo eficiente para calcular o diâmetro (comprimento do maior caminho entre…
- Considere um grafo direcionado que representa citações entre artigos (vértices = artigos; aresta u?v indica que u cita…
- Desenvolva um algoritmo em pseudocódigo que, dado um grafo conectado com pesos não negativos e um vértice origem…
- Projete um algoritmo recursivo (em pseudocódigo) que, dada uma lista de números inteiros, retorne uma lista de pares…
🔎 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