Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando…

Questão

Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências entre tarefas (cada vértice = tarefa; aresta u->v indica que u deve preceder v) e verifique se existe um ciclo de dependência. Use uma variável de estado para cada vértice e explique como o algoritmo detecta ciclos e sua complexidade temporal em função de |V| e |E|.

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

Resposta esperada

Resposta modelo (pseudocódigo e justificativa): // Variáveis: estado[v] ? {0,1,2} para cada vértice v: 0=não visitado, 1=visitando, 2=visitado função existeCiclo(G): para cada v em V faça estado[v] ? 0 para cada v em V faça se estado[v] == 0 então se DFS(v) então retorne verdadeiro // ciclo encontrado retorne falso // nenhum ciclo função DFS(u): estado[u] ? 1 // entrando (na pilha de recusão) para cada (u ? w) em E faça se estado[w] == 0 então se DFS(w) então retorne verdadeiro senão se estado[w] == 1 então retorne verdadeiro // aresta para vértice em processamento = ciclo estado[u] ? 2 // saída (processamento concluído) retorne falso Justificativa e análise: - A variável estado[v] distingue três situações: não iniciado (0), em processamento/recursão (1) e concluído (2). Uma aresta que aponta para um vértice com estado 1 indica um retrocesso na recursão (back edge), logo existe um ciclo. - Correção: o DFS explora caminhos; se houver ciclo, haverá uma aresta para um vértice ainda em processamento e a função detecta e propaga a descoberta do ciclo até a chamada inicial. - Complexidade temporal: cada vértice é visitado uma vez e cada aresta é examinada uma vez durante as chamadas DFS; portanto o tempo é O(|V| + |E|). - Espaço adicional: vetor estado de tamanho |V| e a pilha de recursão com altura = |V|.

Explicação

O algoritmo utiliza a técnica de busca em profundidade (DFS) para explorar o grafo, marcando os vértices com estados que ajudam a identificar ciclos. A detecção de um ciclo ocorre quando uma aresta aponta para um vértice que ainda está em processamento, indicando um retrocesso na recursão. A complexidade temporal O(|V| + |E|) reflete a eficiência do algoritmo, pois cada vértice e aresta é analisado uma única vez.

Raio-X da questão

Questões parecidas com resolução

• Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de…
• Projete um algoritmo em linguagem descritiva que, dado um grafo dirigido acíclico (DAG) que representa pré-requisitos…
• Projete um algoritmo em pseudocódigo para detectar ciclos em um grafo dirigido representado por listas de adjacência…
• 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…
• Qual técnica algorítmica permite detectar ciclos em um grafo dirigido em tempo O(V+E)?

Todas as questões de Programação - Propriedades de grafos