Descreva, em termos de algoritmo que usa a variável 'visitado', como contar o número de componentes conexos em…

Questão

Descreva, em termos de algoritmo que usa a variável 'visitado', como contar o número de componentes conexos em uma rede representada por lista de adjacência.

1. A) Contar componentes sem usar a variável 'visitado'.
2. B) Usar DFS apenas em vértices com grau maior que 1.
3. C) Percorrer todos os vértices; para cada vértice não visitado executar DFS/BFS marcando 'visitado' e incrementar um contador; o contador é o número de componentes.
4. D) Incrementar o contador apenas quando todos vértices forem visitados.
5. E) Execute apenas a busca em vértices visitados.

✅ Resposta correta: alternativa C

Resolução passo a passo

1. Para contar componentes conexos em um grafo (rede) representado por lista de adjacência, precisamos de um algoritmo que visite cada componente exatamente uma vez. A variável 'visitado' registra quais vértices já foram alcançados por alguma busca. Passo 2: Inicie um contador de componentes com valor zero e marque todos os vértices como não visitados. Passo 3: Percorra todos os vértices da rede, um por um. Passo 4: Ao encontrar um vértice que ainda não foi visitado, ele pertence a um componente nunca explorado; então incremente o contador em 1 e execute uma DFS ou BFS a partir dele. Essa busca percorre toda a componente conexa, marcando como visitados todos os vértices alcançáveis pelas arestas da lista de adjacência. Passo 5: Quando o laço terminar, o contador contém o número de componentes conexos, pois cada componente foi iniciado exatamente uma vez, no seu primeiro vértice não visitado. Passo 6: Por que a alternativa C está certa: ela descreve exatamente esse procedimento, com varredura de todos os vértices, DFS/BFS apenas a partir de vértices não visitados, marcação e incremento do contador. Passo 7: Por que as outras estão erradas: a alternativa A elimina a variável 'visitado', sem a qual a busca reexploraria componentes já contados; a alternativa B restringe a busca a vértices de grau maior que 1, deixando de fora componentes formados por vértices isolados, que também contam; a alternativa D incrementa o contador somente ao final, o que não faz sentido, pois o número de componentes é contado a cada nova busca iniciada; a alternativa E manda buscar em vértices já visitados, o que é redundante e não conta componentes.

💡 Dica: Pense em como percorrer a lista de adjacência para identificar componentes.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Escreva um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo não direcionado e não…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado representado por listas de adjacência…
• Descreva em pseudocódigo um algoritmo que, dada uma rede representada por um grafo com n nós e lista de arestas…
• Em um algoritmo que identifica componentes conexas em um grafo não direcionado usando DFS, qual variável (tipo de dado)…
• Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…

Todas as questões de [CONFERIR] Construir soluções baseadas no uso de algoritmos e conceitos da Computação para resolver problemas, avaliando suas qualidades e melhorando-as.