Computação4º anoBNCC EF15CO02Difícil⏱ longo

Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido…

Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva

Habilidade BNCC EF15CO02

Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.

Fonte: Base Nacional Comum Curricular (MEC).

Questão

Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando travessia em profundidade (DFS). Explique como as marcações de visita e a pilha de recursão são usadas.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

1) Variáveis-chave: visited[v] (boolean), inStack[v] (boolean) ou recStack; grafo representado por listas de adjacência. 2) Para cada vértice v não visitado, chamar DFS(v). 3) Na entrada de DFS(v): marcar visited[v]=true e inStack[v]=true. 4) Para cada vizinho u de v: se visited[u] == false, chamar DFS(u) recursivamente; se visited[u]==true e inStack[u]==true, existe ciclo (aresta de retorno). 5) Na saída de DFS(v): inStack[v]=false (pop da pilha de recursão). 6) Alternativa iterativa: usar pilha explícita e marcar estados (0=não visitado,1=em processamento,2=finalizado). 7) Complexidade: O(n + m) no tempo e O(n) extra para as marcações/recursão. 8) Observação de implementação: cuidar de profundidade de recursão em grafos grandes (usar pilha explícita ou detecção de limites). Essa abordagem usa duas marcações para distinguir vértices em processamento (na pilha) daqueles já finalizados; uma aresta que aponta para um vértice ainda na pilha indica um ciclo em grafos dirigidos.

Explicação

A explicação apresentada descreve de forma clara e estruturada como detectar ciclos em um grafo dirigido utilizando a técnica de travessia em profundidade, abordando as variáveis essenciais e o fluxo do algoritmo. A utilização das marcações de visita e da pilha de recursão permite identificar quais vértices estão em processamento, facilitando a detecção de arestas de retorno que indicam a presença de ciclos. Além disso, a menção à complexidade do algoritmo e à alternativa de implementação reforça a compreensão sobre a eficiência e os cuidados necessários em casos de grafos grandes.

Raio-X da questão

Dificuldade Difícil

Bloom Criar

Leitura alto

Discriminação alto

Peso pedagógico alto

Autonomia do enunciado completo

Cobertura da habilidade multipla

🧪 Simulado🩺 Diagnóstico🧮 Exige cálculo🏠 Cotidiano🔗 Interdisciplinar⭐ Representativa✍️ interpretativa🧩 desafio

🎯 Conceito central

detecção de ciclos em grafos

📌 Objetivo

avaliacao

🧱 Pré-requisitos

algoritmos de busca · grafos dirigidos

📚 Reveja

Revisar algoritmos de busca em profundidade e suas aplicações.

⚠️ Erro mais comum

O aluno pode descrever um algoritmo que não considera corretamente as marcações de visita, levando a uma detecção incorreta de ciclos.

🌎 Tema transversal

ciencia_tecnologia

🤝 Socioemocional

pensamento_critico

🏫 Contexto

cientifico

Questões parecidas com resolução

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