Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência…

Questão

Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique todos os vértices de articulação (cut vertices); explique como usar as variáveis 'tempo', 'disc' e 'low'.

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

Resposta esperada

Usar um DFS modificada (algoritmo de Tarjan): inicialize arrays disc[u], low[u], parent[u] e visited[u]; tempo = 0. Para cada vértice u não visitado, chame DFS(u). Em DFS(u): marque visited[u]=true; disc[u]=low[u]=++tempo; children=0. Para cada v em adj[u]: se v não visitado então parent[v]=u; children++; chamar DFS(v); low[u]=min(low[u], low[v]); se parent[u]==-1 e children>1 então u é ponto de articulação; se parent[u]!=-1 e low[v]>=disc[u] então u é ponto de articulação. Se v já visitado e v != parent[u], atualize low[u]=min(low[u], disc[v]). Complexidade: O(V+E). As variáveis: 'tempo' dá ordem de descoberta (disc), 'disc' registra tempo de descoberta, 'low' registra menor tempo alcançável por retrografo e permite decidir se uma subárvore depende de u para se conectar ao resto do grafo.

Explicação

O algoritmo apresentado utiliza a busca em profundidade (DFS) para identificar vértices de articulação, aproveitando as variáveis 'disc' e 'low' para rastrear a ordem de descoberta e a menor profundidade acessível, respectivamente. A lógica de verificação para determinar se um vértice é um ponto de articulação baseia-se na contagem de filhos e na comparação dos valores de 'low' e 'disc', assegurando que a remoção do vértice desconecte partes do grafo. A complexidade O(V+E) indica que o algoritmo é eficiente, percorrendo cada vértice e aresta uma única vez.

Raio-X da questão

Questões parecidas com resolução

• Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
• Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…
• Descreva um algoritmo, indicando as variáveis-chave e os passos, para identificar todos os vértices de articulação (cut…
• Descreva um algoritmo baseado em DFS para identificar vértices de articulação (cut vertices) em um grafo não direcionado…
• Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
• Projete um algoritmo (explique a ideia e apresente pseudocódigo) que, dado um grafo não direcionado em lista de…

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