Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar e construir a solução de problemas por meio de refinamentos, utilizando diversos níveis de abstração desde a especificação até a implementação.
Fonte: Base Nacional Comum Curricular (MEC).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?
- 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.
- B) Usar lista de adjacência e marcar visitas por aresta em vez de por nó.
- C) Usar lista de adjacência e marcar visitado com uma única variável global.
- D) Usar matriz de adjacência e não usar vetor 'visitado'.
- 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
- 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.
- 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.
- 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.
- Por que as demais estão erradas:
- B) Marcar por aresta não impede que um nó seja revisitado por caminhos diferentes, então os ciclos continuam ocorrendo.
- 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.
- 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.
- 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.
- 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
A lista de adjacência torna iteração sobre vizinhos eficiente; o vetor booleano permite checagem O(1) se um nó já foi processado, evitando revisitas e ciclos durante a recursão.
Imagina que marcar as arestas percorridas basta para controlar o percurso, mas o que causa ciclos é revisitar nós, não arestas. Um nó pode ser alcançado por vários caminhos diferentes sem que nenhuma aresta se repita.
Por que engana: O aluno pode confundir a marcação de nós visitados com a marcação de arestas, levando a ciclos no percurso.
Acredita que um único valor global consegue indicar o estado de todas as cidades. Não percebe que cada nó precisa de sua própria marcação para saber se já foi visitado.
Acha que a matriz de adjacência dispensa o controle de visitados, talvez por confundir a forma de representar o grafo com o mecanismo de controle do percurso. A representação do grafo e a marcação de nós são problemas independentes.
Supõe que a pilha de chamadas, por guardar o caminho atual, também impede revisitas. Na verdade, ela só lembra o caminho corrente e esquece nós já explorados em outros ramos, permitindo ciclos.
Raio-X da questão
algoritmo recursivo
avaliacao
estrutura de dados · algoritmos recursivos
Revisar estruturas de dados para grafos e algoritmos recursivos.
O aluno pode confundir a marcação de nós visitados com a marcação de arestas, levando a ciclos no percurso.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
- Ao aplicar o algoritmo BFS em uma rede social modelada como grafo não ponderado, qual estrutura de dado (variável) é…
- Ao generalizar um algoritmo recursivo que calcula custo mínimo em uma rede (grafo) para múltiplas instâncias, qual…
- Em um grafo não orientado, qual estrutura de dados é mais adequada para implementar a travessia em largura (BFS)?
- Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado é usada…
- Para implementar o algoritmo BFS (busca em largura) em um grafo não ponderado, qual estrutura de dados abstrata é…
🔎 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