Escreva um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo não direcionado e não…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Reconhecer objetos do mundo real e digital que podem ser representados através de grafos que estabelecem uma organização com uma quantidade variável de vértices conectados por arestas, fazendo manipulações simples sobre estas representações.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Escreva um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo não direcionado e não ponderado, conte e retorne o número de componentes conectadas. Use os termos 'algoritmo' e 'visitado'.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Algoritmo ContarComponentes(ListaAdj): 1. Para cada vértice v em ListaAdj: visitado[v] <- falso 2. componentes <- 0 3. Para cada vértice v em ListaAdj: se visitado[v] = falso então componentes <- componentes + 1 executar DFS(v) 4. Retornar componentes Subrotina DFS(u): 1. marcar visitado[u] <- verdadeiro 2. Para cada w em ListaAdj[u]: se visitado[w] = falso então chamar DFS(w) Descrição: o algoritmo inicializa todos os visitados como falso, percorre cada vértice e, quando encontra um não visitado, incrementa o contador de componentes e executa uma DFS marcando todos os vértices alcançáveis daquela componente. No final, 'componentes' contém o número de componentes conectadas.
Explicação
O algoritmo utiliza uma abordagem de busca em profundidade (DFS) para explorar cada componente do grafo, garantindo que todos os vértices conectados sejam marcados como visitados. Ao contar quantas vezes inicia uma nova DFS, o algoritmo determina o número total de componentes conectadas. Essa metodologia é eficaz, pois cada execução da DFS identifica e marca todos os vértices de uma única componente, evitando contagens duplicadas.
Raio-X da questão
componentes conectadas
avaliacao
listas de adjacência · componentes de grafos
Revisar conceitos de grafos e algoritmos de busca.
O aluno pode confundir o conceito de componentes conectadas com o de arestas ou vértices isolados, resultando em uma contagem incorreta.
ciencia_tecnologia
criatividade
abstrato
Questões parecidas com resolução
- Antes de ir à feira, Bia anotou: pão, bananas e sabonete. Que objeto do dia a dia é esse e como Bia pode mudar a ordem…
- No mapa da sala, há círculos para a porta, a mesa da professora, a estante e o quadro. As linhas ligam porta-mesa…
- — A mensagem não chegou ao abrigo do bairro Serra — avisou uma moradora pelo rádio comunitário. Após a enchente, a…
- — O painel da praça ficou cheio de bilhetes sobre lâmpadas apagadas — observou Caio, voluntário do bairro. Em cada…
- — Quem contracena com Caio? — perguntou a responsável pelo grupo de teatro do bairro. Para organizar os próximos…
- Por que uma mesma caminhada pela área verde pode produzir fichas tão diferentes? Para organizar os registros 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