Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista…

Questão

Descreva um algoritmo que, dado um grafo dirigido representando dependências entre tarefas (entrada como lista de adjacência), identifique todas as componentes fortemente conectadas. Explique as variáveis e estruturas de dados usadas e informe a complexidade temporal.

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

Resposta esperada

Algoritmo (Kosaraju) — passos: 1) Variáveis/estruturas: lista de adjacência adj[], vetor boolean visited[V], pilha stack (ou lista de ordem de término), adjTrans[] para o grafo transposto, lista components para resultados. 2) Primeira passagem: para cada vértice v não visitado, execute DFS(v) em adj[], marcando visited[v]=true; ao terminar a recursão de v, empurre v na stack. 3) Construa adjTrans[] invertendo todas as arestas de adj[]. 4) Zere visited[]. 5) Segunda passagem: enquanto stack não estiver vazia, pop u; se not visited[u], execute DFS_Collect(u) em adjTrans[] para coletar todos os vértices alcançáveis — esse conjunto é uma componente fortemente conectada; marque-os em visited e adicione o componente a components. 6) Resultado: lista de componentes fortemente conectadas. Complexidade: cada DFS percorre arestas e vértices uma vez; construir o transposto é O(V+E); complexidade total O(V+E). Observações: use listas para adjacência e arrays booleanos para eficiência de tempo e espaço; mantenha uma estrutura para armazenar cada componente (vetor ou lista).

Explicação

O algoritmo de Kosaraju é eficiente para identificar componentes fortemente conectadas em um grafo dirigido, utilizando duas passagens de busca em profundidade (DFS) e a construção do grafo transposto. A complexidade O(V+E) é garantida, pois cada vértice e aresta é processado uma única vez, tornando-o adequado para grandes grafos. O uso de estruturas como pilhas e listas de adjacência otimiza tanto o tempo quanto o espaço, permitindo uma implementação prática e eficiente.

Raio-X da questão

Questões parecidas com resolução

• Descreva em pseudocódigo um algoritmo que, dado um grafo dirigido, identifica todas as componentes fortemente conexas…
• Descreva, em pseudocódigo, um algoritmo que receba como dado um grafo direcionado G = (V,E) representando dependências…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• 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…

Todas as questões de Programação - Algoritmos clássicos