Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de árvores e grafos para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de adjacência; explique a estrutura de dados, os passos e a complexidade.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Usar DFS com marcação de estados: 0=não visitado, 1=visiting, 2=visitado. Pseudocódigo: DFS(u): state[u]=1; para v em adj[u]: se state[v]==0 então DFS(v) elif state[v]==1 então return true; fim; state[u]=2; return false. Executar DFS em todos os vértices não visitados. Estruturas: lista de adjacência e vetor de estados. Complexidade: O(V+E).
Explicação
A abordagem utiliza a busca em profundidade (DFS) para percorrer os vértices do grafo, marcando o estado de cada um para identificar ciclos. A marcação dos estados permite distinguir entre vértices que estão sendo visitados e aqueles que já foram completamente explorados, facilitando a detecção de ciclos. A complexidade O(V+E) reflete a eficiência do algoritmo, pois cada vértice e aresta é processado uma única vez.
Raio-X da questão
detecção de ciclos em grafos
avaliacao
estruturas de dados · algoritmos de busca
Revisar algoritmos de busca em grafos e suas complexidades.
O aluno pode confundir a detecção de ciclos com a simples travessia do grafo, não considerando as condições necessárias para identificar um ciclo.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em períodos de calor intenso, o comitê de saúde de uma escola pretende divulgar, antes do recreio, um boletim na rádio…
- Por que algumas oficinas de um centro cultural não podem ocorrer no mesmo horário? Na programação de sábado, Robótica…
- — O alerta saiu de Arumã, mas o enlace entre Caju e Ema parou de funcionar — avisou a operadora da central fluvial…
- Por que duas oficinas muito procuradas não podem ocorrer no mesmo horário? Em uma situação fictícia, a organização de…
- — Se eu voltar pelo mesmo corredor, chego de novo na entrada? — perguntou uma visitante ao testar o aplicativo de um…
- Ontem o mapa do festival me mandou dar uma volta enorme reclamou uma visitante. Para reduzir aglomeracoes, a…
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