Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções de problemas usando a técnica de recursão e automatizar tais soluções usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo dirigido. Em sua resposta descreva as variáveis técnicas 'visitado' e 'pilha_rec' (recursion_stack) e os critérios usados para reconhecer um ciclo.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
DFS recursivo: marcar visitado[v]=pilha_rec[v]=true; para cada vizinho u: se !visitado[u] chamar dfs(u); se pilha_rec[u] for true ? ciclo detectado; ao final pilha_rec[v]=false. Complexidade O(V+E).
Explicação
A explicação aborda a implementação do algoritmo DFS para detectar ciclos em um grafo dirigido, utilizando as variáveis 'visitado' e 'pilha_rec' para rastrear os nós já explorados e os que estão na pilha de recursão, respectivamente. O reconhecimento de um ciclo ocorre quando um nó já visitado é encontrado novamente na pilha de recursão, indicando que um caminho foi percorrido que retorna a um nó anterior. A complexidade O(V+E) reflete a eficiência do algoritmo ao percorrer todos os vértices e arestas do grafo.
Raio-X da questão
ciclos em grafos
avaliacao
algoritmos de busca · estruturas de dados
Revisar a busca em profundidade e suas aplicações em grafos.
O aluno pode confundir a função da pilha de recursão com a lista de nós visitados, não explicando corretamente como cada uma contribui para a detecção de ciclos.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando…
- No algoritmo DFS aplicado a um grafo dirigido, qual condição envolvendo a variável booleana 'recStack' indica a…
- Descreva um algoritmo, indicando as variáveis-chave e os passos, para identificar todos os vértices de articulação (cut…
- Em um algoritmo de busca em profundidade (DFS) em um grafo que precisa rastrear o caminho atual para detecção de ciclos…
- Ao projetar um algoritmo recursivo para percorrer uma rede de cidades representada por um grafo, qual estrutura de dados…
- Qual técnica algorítmica permite detectar ciclos em um grafo dirigido em tempo O(V+E)?
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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