Em uma competição de programação, Ana recebeu um grafo que pode ter grupos de nós sem ligação entre si. Ela…

Questão

Em uma competição de programação, Ana recebeu um grafo que pode ter grupos de nós sem ligação entre si. Ela precisa criar um algoritmo que visite todos os nós, sem visitar o mesmo nó várias vezes. Qual abordagem garante que todos os nós do grafo sejam visitados?

1. A) Percorrer as ligações até voltar ao nó inicial e encerrar o algoritmo.
2. B) Iniciar a busca em um nó e repetir a busca a partir de cada nó ainda não visitado.
3. C) Iniciar a busca somente no primeiro nó e seguir suas ligações até o fim.
4. D) Organizar os nós em ordem e considerar essa lista como uma visita completa.
5. E) Escolher o nó com mais ligações e iniciar a busca somente por ele.

✅ Resposta correta: alternativa B

Resolução passo a passo

1. O enunciado descreve um grafo que pode ser desconexo, ou seja, formado por grupos de nós sem ligação entre si. Além disso, cada nó deve ser visitado apenas uma vez. Passo 2: Uma busca iniciada em um nó só alcança os nós que estão na mesma componente conexa dele. Por isso, uma única busca não garante visitar todos os nós quando o grafo é desconexo. Passo 3: A alternativa B resolve o problema: inicia-se uma busca (em profundidade ou em largura) em um nó qualquer, marcando os nós visitados. Depois, repete-se a busca a partir de cada nó que ainda não foi visitado. Como cada componente conexa recebe pelo menos uma busca, todos os nós são alcançados, e o controle de visitados impede que um nó seja processado mais de uma vez. Passo 4: A alternativa A está errada porque percorrer as ligações até voltar ao nó inicial só cobre o ciclo ou a componente onde ele está, e encerra sem verificar os demais nós. Passo 5: A alternativa C está errada porque partir apenas do primeiro nó alcança somente a componente desse nó, deixando os outros grupos sem visita. Passo 6: A alternativa D está errada porque ordenar os nós não segue as ligações do grafo e não constitui um percurso de busca, além de não garantir a visita de todos os nós com as regras do problema. Passo 7: A alternativa E está errada porque o nó com mais ligações pode pertencer a apenas um dos grupos, e iniciar só nele deixa os outros grupos sem visita. Conclusão: a resposta correta é B, que coincide com o gabarito oficial.

💡 Dica: Considere as abordagens de busca em profundidade e busca em largura.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Descreva, em termos de algoritmo que usa a variável 'visitado', como contar o número de componentes conexos em uma rede…
• Escreva um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo não direcionado e não…
• Descreva em pseudocódigo um algoritmo que, dada uma rede representada por um grafo com n nós e lista de arestas…
• Imagine que você está programando um jogo onde os personagens precisam seguir rotas em um mapa. Quais são as etapas…

Todas as questões de Programação - Propriedades de grafos