Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual…

Questão

Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados e variável são mais adequadas para marcar nós visitados e evitar ciclos durante o percurso?

1. A) Usar uma lista de adjacência para o grafo e um vetor/registro booleano 'visitado[n]' (ou conjunto) para marcar nós; verificar visitado antes de recursar.
2. B) Usar lista de adjacência e marcar visitas por aresta em vez de por nó.
3. C) Usar lista de adjacência e marcar visitado com uma única variável global.
4. D) Usar matriz de adjacência e não usar vetor 'visitado'.
5. E) Usar lista de adjacência e confiar só na pilha de chamadas para evitar ciclos.

✅ Resposta correta: alternativa A

Resolução passo a passo

1. O problema pede a estrutura de dados e a variável mais adequadas para percorrer um grafo recursivamente sem entrar em ciclos. Para isso, precisamos de uma representação eficiente das arestas e de um mecanismo que lembre quais nós já foram visitados.
2. A lista de adjacência é a representação mais adequada para uma rede esparsa de cidades, pois para cada nó guarda apenas seus vizinhos diretos, economizando memória e tornando a iteração sobre os vizinhos rápida.
3. Para evitar ciclos, basta um vetor booleano visitado[n] (ou um conjunto), indexado pelos nós, que é marcado ao entrar em um nó. Antes de recursar para um vizinho, verifica-se se ele já está marcado; se estiver, a chamada não é feita. Isso garante que cada nó seja processado no máximo uma vez.
4. Por que as demais estão erradas:
5. B) Marcar por aresta não impede que um nó seja revisitado por caminhos diferentes, então os ciclos continuam ocorrendo.
6. C) Uma única variável global não consegue registrar o estado de cada um dos muitos nós; ela não distingue quais cidades já foram visitadas.
7. D) A matriz de adjacência pode representar o grafo, mas dispensar o vetor de visitados deixa o algoritmo sem controle de ciclos, o que gera recursão infinita em grafos com ciclos.
8. E) A pilha de chamadas apenas guarda o caminho corrente; ela não lembra nós já percorridos por outros ramos, então não evita ciclos nem revisitas.
9. Conclusão: a alternativa A combina a representação adequada do grafo com a marcação por nó, que é exatamente o que garante o término do percurso.

💡 Dica: Considere as estruturas de dados adequadas para grafos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
• Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
• Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
• Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
• Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
• — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…

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.