Descreva um algoritmo, indicando as variáveis-chave e os passos, para identificar todos os vértices de…

Questão

Descreva um algoritmo, indicando as variáveis-chave e os passos, para identificar todos os vértices de articulação (cut vertices) em um grafo não dirigido usando busca em profundidade (DFS). Explique como são atualizados 'disc' e 'low' e qual a complexidade do algoritmo.

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

Resposta esperada

Use DFS global com tempo crescente (tempo++). Variáveis-chave: disc[v] (tempo de descoberta), low[v] (menor disc alcançável via v ou seus descendentes), parent[v], visited[v]. Para cada vértice u não visitado: DFS(u): visited[u]=true; disc[u]=low[u]=tempo++; filhos=0; para cada v vizinho de u: se !visited[v]: parent[v]=u; filhos++; DFS(v); low[u]=min(low[u], low[v]); se parent[u]==NULL e filhos>1 então u é articulação; se parent[u]!=NULL e low[v]>=disc[u] então u é articulação; senão se v != parent[u] então low[u]=min(low[u], disc[v]). Raciocínio: low[v] propaga a capacidade de conexão de subárvores a ancestrais; condição low[v]>=disc[u] indica que não existe retorno da subárvore de v a um ancestral de u, logo u separa componentes. Complexidade: cada aresta e vértice é processado uma vez, portanto O(V+E). Opcional: apresentar pseudocódigo compacto e estruturas de armazenamento (listas de adjacência, arrays para disc/low/parent).

Explicação

O algoritmo descrito utiliza a busca em profundidade para explorar o grafo e identificar vértices de articulação, atualizando as variáveis 'disc' e 'low' para rastrear o tempo de descoberta e a menor descoberta acessível a partir de cada vértice. As condições para identificar um vértice de articulação garantem que, se um vértice não puder ser alcançado por nenhum de seus descendentes, ele é crítico para a conectividade do grafo. A complexidade O(V+E) reflete que cada vértice e aresta é visitado uma única vez, assegurando eficiência na execução do algoritmo.

Raio-X da questão

Questões parecidas com resolução

• Descreva um algoritmo baseado em DFS para identificar vértices de articulação (cut vertices) em um grafo não direcionado…
• Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
• Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
• Descreva um algoritmo, indicando as variáveis-chave e os passos, para detectar ciclos em um grafo dirigido usando…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…
• Explique como um algoritmo baseado em DFS (busca em profundidade) identifica a presença de ciclo em um grafo dirigido…

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