Projete um algoritmo em linguagem descritiva que, dado um grafo dirigido acíclico (DAG) que representa…

Questão

Projete um algoritmo em linguagem descritiva que, dado um grafo dirigido acíclico (DAG) que representa pré-requisitos entre atividades (vértices) e arestas direcionadas de pré-requisito para atividade dependente, gere uma ordem viável de execução (ordenação topológica). Explique como o algoritmo detecta ausência de ordem possível (i.e., presença de ciclo) e informe a complexidade temporal.

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

Resposta esperada

Algoritmo (Kahn) — entrada: DAG G(V,E) 1) Calcular grau de entrada indeg[v] para todo v em V. 2) Colocar em fila Q todos os vértices com indeg = 0. 3) lista ? [] 4) enquanto Q não vazia: u ? remover(Q); adicionar u em lista; para cada aresta (u,v) em E: indeg[v] ? indeg[v] - 1; se indeg[v] = 0 então enfileirar v em Q. 5) se |lista| < |V| então: reportar "não existe ordenação (ciclo)"; senão retornar lista. Detecção de ciclo: se algum vértice permanece com indeg>0 (isto é, |lista| < |V|), há ciclo. Complexidade: O( |V| + |E| ). Observação: para ordenação estável por prioridade (ex.: menor prazo primeiro), substituir Q por uma fila de prioridade; mantém complexidade O((|V|+|E|) log |V|) dependendo da estrutura.

Explicação

O algoritmo proposto utiliza a técnica de Kahn para realizar a ordenação topológica em um DAG, garantindo que as atividades sejam executadas na ordem correta de acordo com seus pré-requisitos. A detecção de ciclos é feita ao verificar se todos os vértices foram incluídos na lista final; se algum vértice permanecer com grau de entrada maior que zero, isso indica a presença de um ciclo. A complexidade temporal O(|V| + |E|) é eficiente, pois considera tanto o número de vértices quanto o de arestas no grafo.

Raio-X da questão

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