Você precisa agendar tarefas com dependências direcionais e detectar se há ciclo antes de executar. Que…

Questão

Você precisa agendar tarefas com dependências direcionais e detectar se há ciclo antes de executar. Que estrutura de dados técnica e que algoritmo devem ser usados para representar e verificar a ordem executável?

1. A) Detectar ciclos usando busca em largura (BFS) em vez de DFS.
2. B) Representar tarefas como um grafo direcionado e usar ordenação topológica; detectar ciclos via DFS.
3. C) Usar um array para armazenar tarefas em vez de grafo direcionado.
4. D) Representar tarefas como uma lista ligada para simplicidade.
5. E) Utilizar uma fila para agendar tarefas sem considerar dependências.

✅ Resposta correta: alternativa B

Resolução passo a passo

1. O problema pede uma estrutura para representar tarefas com dependências direcionais (tarefa X deve ocorrer antes de tarefa Y) e um algoritmo para verificar se a ordem é executável.
2. Dependências direcionais são naturalmente modeladas por um grafo direcionado, em que vértices são tarefas e arestas indicam a precedência entre elas.
3. Para obter uma ordem válida de execução, usa-se a ordenação topológica, que só existe se o grafo for acíclico (DAG).
4. Um ciclo significa dependência circular (A depende de B, que depende de A), o que torna impossível executar tudo. Esse ciclo pode ser detectado com DFS (busca em profundidade) usando marcações de visitado e de 'em processamento': se a busca encontra um vértice já em processamento, há ciclo. O algoritmo de Kahn (grau de entrada) também serve, mas a alternativa correta menciona DFS, que é a abordagem clássica.
5. Por que as outras estão erradas: A) BFS pode sim ser usado para detectar ciclos (via Kahn), mas a alternativa limita-se a trocar DFS por BFS e não responde à representação nem à ordenação topológica; B) é a resposta completa e correta. C) Um array de tarefas não representa dependências entre elas, que exigem relações entre pares. D) Uma lista ligada simples de tarefas não captura as múltiplas dependências direcionais de cada tarefa. E) Uma fila sem considerar dependências pode executar uma tarefa antes da que ela precisa, violando o enunciado.
6. Conclusão: a estrutura é o grafo direcionado e o algoritmo é a ordenação topológica com detecção de ciclos por DFS, alternativa B.

💡 Dica: Considere as estruturas de dados e algoritmos adequados para grafos.

Alternativa por alternativa

Raio-X da questão

Questões parecidas com resolução

• Para organizar dependências entre tarefas de um projeto (cada tarefa pode depender de várias anteriores), qual estrutura…
• Descreva com precisão o algoritmo e as estruturas de dados (registros, grafo, pilha/fila) para um programa que gerencie…
• 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…
• Em um projeto de programação, a equipe precisa guardar as tarefas a fazer em uma sequência na qual seja possível incluir…
• Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de…

Todas as questões de Programação - Programação usando grafos e árvores