Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — FCM 2018

Algoritmos e Estrutura de DadosEstrutura de Dados
Código
qq337489
Banca
FCM
Órgão
IFN-MG
Ano
2018
Nível
Superior
Cargo
Ciências da Computação: Teoria da Computação
A obtenção das componentes fortemente conexas de um grafo dirigido G = (V, E) é feita da seguinte forma:
  1. AAplicação da busca em profundidade em G, para obtenção dos tempos de término para cada vértice, e aplicação da busca em profundidade em G, considerando os vértices em ordem decrescente dos tempos de término.
  2. BAplicação da busca em profundidade em G, para obtenção dos tempos de término para cada vértice, e aplicação da busca em profundidade no grafo transposto GT = (V, ET ), considerando os vértices em ordem decrescente dos tempos de término.
  3. CAplicação da busca em profundidade em G, para obtenção dos tempos de término para cada vértice, e aplicação da busca em largura no grafo transposto GT= (V, ET ), considerando os vértices em ordem decrescente dos tempos de término.
  4. DAplicação da busca em profundidade em G, para obtenção dos tempos de descoberta para cada vértice, e aplicação da busca em profundidade no grafo transposto GT = (V, ET ), considerando os vértices em ordem crescente dos tempos de descoberta.
  5. EAplicação da busca em profundidade no grafo transposto GT = (V, ET ), para obtenção dos tempos de descoberta para cada vértice, e aplicação da busca em profundidade em G, considerando os vértices em ordem decrescente dos tempos de descoberta.
Revelar gabarito e comentário

GabaritoB — Aplicação da busca em profundidade em G, para obtenção dos tempos de término para cada vértice, e aplicação da busca em profundidade no grafo transposto GT = (V, ET ), considerando os vértices em ordem decrescente dos tempos de término.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Componentes Fortemente Conexas (Algoritmo de Kosaraju-Sharir)

Gabarito: letra B. A obtenção das componentes fortemente conexas de um grafo dirigido é feita com duas buscas em profundidade (DFS): a primeira no grafo original G calcula os tempos de término de cada vértice; a segunda é realizada no grafo transposto GT, processando os vértices em ordem decrescente desses tempos de término. Esse é o algoritmo clássico de Kosaraju-Sharir, descrito em livros-texto de algoritmos.

O contexto fornecido (trecho de Cormen et al.) descreve exatamente esse procedimento:

Algoritmo de Componentes Fortemente Conexas: O algoritmo de tempo linear ... calcula as componentes fortemente conexas de um grafo dirigido G = (V, E) usando duas buscas em profundidade, uma em G e uma em GT ... considerando vértices na segunda busca em profundidade em ordem decrescente dos tempos de término que foram calculados na primeira busca em profundidade.

Vamos analisar cada alternativa:

  1. 11ª DFS em G
  2. 2Tempos de término (f)
  3. 3Ordena vértices por f decrescente
  4. 42ª DFS em GT na ordem
  5. 5Cada árvore = uma CFC
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma que a segunda DFS é aplicada sobre o mesmo grafo G, e não sobre o transposto. Erro conceitual: o algoritmo exige a inversão das arestas (GT) para que cada árvore da segunda DFS corresponda a uma componente fortemente conexa.

Alternativa B — ✅ Correta ⟵ GABARITO

Descreve fielmente o algoritmo: primeira DFS em G para obter tempos de término; segunda DFS no grafo transposto GT, processando vértices em ordem decrescente desses tempos. É a definição do método de Kosaraju-Sharir.

Alternativa C — ❌ Incorreta

Troca a segunda busca em profundidade por busca em largura (BFS). O algoritmo exige DFS para respeitar a ordem de término e gerar a floresta correta de componentes.

Alternativa D — ❌ Incorreta

Utiliza tempos de descoberta (d) em vez de tempos de término (f) e ainda os considera em ordem crescente. O correto é usar tempos de término em ordem decrescente.

Alternativa E — ❌ Incorreta

Inverte a ordem da aplicação: primeiro DFS em GT, depois DFS em G, e ainda usa tempos de descoberta no lugar dos de término. A sequência e os dados utilizados estão trocados.

NÃO CAIA NESSA!

A banca troca sistematicamente três elementos: (1) o grafo da segunda DFS (G em vez de GT); (2) o tipo de tempo (descoberta em vez de término); (3) a ordem (crescente em vez de decrescente). Memorize que a segunda DFS é no transposto, em ordem decrescente dos tempos de término.

Conclusão: A única alternativa que descreve corretamente o algoritmo é a B.

Gabarito: letra B.

Link permanente: /questoes/qq337489