Descreva em pseudocódigo um algoritmo que, dado um grafo dirigido, identifica todas as componentes fortemente…

Questão

Descreva em pseudocódigo um algoritmo que, dado um grafo dirigido, identifica todas as componentes fortemente conexas (SCC) usando busca em profundidade e explique a lógica por trás dos passos.

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

Resposta esperada

Pseudocódigo (Kosaraju): 1) stack = vazio; visited[v]=false ?v 2) for v in V: if !visited[v]: DFS1(v) DFS1(u): visited[u]=true; for w in adj[u]: if !visited[w]: DFS1(w); push(stack,u) 3) Gt = transpose(G) (inverte arestas) 4) visited[v]=false ?v 5) components = [] while stack não vazio: v = pop(stack); if !visited[v]: comp=[]; DFS2(v,comp); components.append(comp) DFS2(u,comp): visited[u]=true; comp.append(u); for w in adj_gt[u]: if !visited[w]: DFS2(w,comp) Explicação da lógica: a primeira DFS registra tempos de finalização; ao processar vértices em ordem decrescente desses tempos no grafo transposto, cada chamada DFS2 visita exatamente uma SCC. Complexidade O(n+m).

Explicação

O algoritmo de Kosaraju utiliza duas passagens de busca em profundidade para identificar as componentes fortemente conexas, primeiro registrando a ordem de finalização dos vértices e, em seguida, explorando o grafo transposto nessa ordem. Essa abordagem garante que cada chamada da segunda DFS encontre e marque todos os vértices de uma única SCC, aproveitando a propriedade de que, em um grafo transposto, as arestas são invertidas. A complexidade O(n+m) reflete a eficiência do algoritmo, onde n é o número de vértices e m é o número de arestas.

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…
• Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Descreva um algoritmo, indicando as variáveis-chave e os passos, para identificar todos os vértices de articulação (cut…
• Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo dirigido…
• Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…

Todas as questões de Decomposição