Um programa recebe um grafo dirigido que representa pré-requisitos entre disciplinas (nó = disciplina; aresta…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Um programa recebe um grafo dirigido que representa pré-requisitos entre disciplinas (nó = disciplina; aresta A?B indica A é pré-requisito de B). O algoritmo implementado usa DFS recursiva com marcações para detectar ciclos. (a) dê um caso de teste mínimo que contenha um ciclo; (b) identifique um erro comum na implementação DFS que pode impedir a detecção de ciclos; (c) proponha uma alternativa de técnica ou estrutura de dados para detectar ciclos eficientemente em grafos grandes e justifique.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
(a) Caso mínimo: três nós A,B,C com arestas A?B, B?C, C?A — existe ciclo A?B?C?A. (b) Erro comum: usar apenas um vetor booleano "visitado" e tratá-lo como indicação de presença na pilha recursiva; isso conflita estados e faz que arestas de retorno não sejam reconhecidas. A implementação correta separa estados (por exemplo cores: branca, cinza, preta) ou mantém uma pilha/flag "na pilha" para identificar back edges. (c) Alternativa: usar algoritmo de Kahn (topological sort por graus de entrada) que remove nós com grau 0 iterativamente; se ao final restarem nós, existe ciclo. Kahn e a abordagem de cores com DFS têm complexidade O(n + m) (n= nós, m=arestas). Para grafos grandes, representar adjacência com listas e índices em tabelas hash ou vetores permite operações de vizinhança e atualização de graus em tempo linear médio, reduzindo custo prático à ordem O(n+m) e favorecendo escalabilidade, com trade-off de uso adicional de memória para estruturas auxiliares.
Explicação
O caso mínimo apresentado demonstra claramente a presença de um ciclo, essencial para validar a detecção de ciclos em grafos. A identificação do erro comum na implementação de DFS destaca a importância de diferenciar os estados dos nós para evitar confusões na detecção de arestas de retorno. A proposta do algoritmo de Kahn como alternativa oferece uma abordagem eficiente e escalável para detectar ciclos, utilizando uma técnica que se adapta bem a grafos grandes, equilibrando complexidade e uso de memória.
Raio-X da questão
detecção de ciclos em grafos
avaliacao
grafos dirigidos · busca em profundidade (DFS)
Revisar algoritmos de busca em profundidade e estruturas de dados para grafos.
O aluno pode confundir a marcação de nós visitados com a detecção de ciclos, levando a uma implementação que não verifica corretamente os nós em processo de visitação.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Projete um algoritmo em linguagem descritiva que, dado um grafo dirigido acíclico (DAG) que representa pré-requisitos…
- Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
- Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando…
- Descreva com precisão o algoritmo e as estruturas de dados (registros, grafo, pilha/fila) para um programa que gerencie…
- Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo dirigido…
- Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de…
Todas as questões de Organização e representação da informação
🔎 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