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

• Projete um algoritmo em linguagem descritiva que, dada a lista de adjacência de um grafo dirigido acíclico (DAG) onde…
• Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
• Descreva com precisão o algoritmo e as estruturas de dados (registros, grafo, pilha/fila) para um programa que gerencie…
• Para organizar dependências entre tarefas de um projeto (cada tarefa pode depender de várias anteriores), qual estrutura…
• Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de…
• Você precisa agendar tarefas com dependências direcionais e detectar se há ciclo antes de executar. Que estrutura de…

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