No algoritmo DFS aplicado a um grafo dirigido, qual condição envolvendo a variável booleana 'recStack' indica…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Explorar propriedades básicas de grafos.
Fonte: Base Nacional Comum Curricular (MEC).Questão
No algoritmo DFS aplicado a um grafo dirigido, qual condição envolvendo a variável booleana 'recStack' indica a existência de um ciclo?
- A) Verificar se recStack[v] == false para detectar ciclos.
- B) Se recStack.length > 1, há um ciclo no grafo.
- C) Encontrar uma aresta que aponta para um vértice sem recStack.
- D) Ciclos são identificados apenas pela quantidade de vértices visitados.
- E) Encontrar uma aresta que aponta para um vértice com recStack[v] == true (v em processamento).
✅ Resposta correta: alternativa E
Resolução passo a passo
- Na DFS para detecção de ciclos em grafo dirigido, mantém-se um vetor booleano recStack que marca os vértices que estão na pilha de recursão atual, isto é, os vértices em processamento (cujo exame ainda não terminou).
- Ao explorar uma aresta u -> v a partir de u, se v já está marcado com recStack[v] == true, então v é um ancestral de u no caminho de recursão atual. Isso fecha um caminho de volta a v, formando um ciclo. Logo, a alternativa E está correta e coincide com o gabarito.
- A alternativa A está errada porque recStack[v] == false significa que v não está no caminho atual, o que não indica ciclo; ao contrário, indica apenas que v pode ser visitado normalmente.
- A alternativa B está errada porque o tamanho do vetor recStack é sempre o número de vértices e não diz nada sobre a existência de ciclos.
- A alternativa C está errada porque uma aresta para um vértice fora da pilha de recursão é uma aresta comum ou de avanço/cruzamento, não de retorno, e não caracteriza ciclo.
- A alternativa D está errada porque a quantidade de vértices visitados não determina a existência de ciclos; a identificação depende da estrutura das arestas e da pilha de recursão.
💡 Dica: Considere a definição de ciclos em grafos dirigidos.
Alternativa por alternativa
O aluno acredita que a ausência de marcação na pilha de recursão sinaliza ciclo, confundindo o estado 'não visitado/fora do caminho' com a condição de retorno.
Por que engana: Confundir a condição de verificação de recStack, acreditando que um vértice não visitado pode indicar um ciclo.
O aluno supõe que o tamanho do vetor de controle tem relação com a existência de ciclos, confundindo estrutura de dados auxiliar com propriedade do grafo.
O aluno pensa que qualquer aresta para um vértice não marcado na pilha forma ciclo, sem perceber que isso é apenas uma aresta de exploração normal.
O aluno imagina que a contagem de vértices visitados basta para detectar ciclos, uma intuição de senso comum que ignora a direção e a estrutura das arestas.
Uma aresta para um vértice presente na pilha de recursão (recStack true) é um back edge; isso demonstra retorno a um vértice não finalizado, logo há ciclo dirigido.
Raio-X da questão
ciclos em grafos dirigidos
avaliacao
algoritmos de busca em grafos · estruturas de dados
Revisar as condições de detecção de ciclos em algoritmos de grafos.
Confundir a condição de verificação de recStack, acreditando que um vértice não visitado pode indicar um ciclo.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo dirigido…
- Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando…
- Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
- Qual técnica algorítmica permite detectar ciclos em um grafo dirigido em tempo O(V+E)?
- Em uma implementação iterativa do algoritmo DFS (busca em profundidade) para um grafo, qual estrutura de dado é usada…
🔎 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