Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência…

Questão

Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine todos os vértices de articulação (vértices de corte). Use variáveis como 'tempo', 'disc[v]' e 'low[v]' e explique a ideia principal do algoritmo.

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

Resposta esperada

Resposta modelo (pseudocódigo e ideia): Inicialize tempo=0; para todo v: disc[v]=-1, low[v]=8, pai[v]=NIL. Função DFS(u): disc[u]=low[u]=++tempo; filhos=0; para cada w em adj[u]: se disc[w]==-1 então pai[w]=u; filhos++; DFS(w); low[u]=min(low[u],low[w]); se pai[u]!=NIL e low[w]>=disc[u] então u é articulação; se pai[u]==NIL e filhos>1 então u é articulação; senão se w!=pai[u] então low[u]=min(low[u],disc[w]); Executar DFS(r) para cada vértice não visitado. Justificativa e correção: disc[u] registra tempo de descoberta; low[u] indica menor tempo alcançável por u via arestas de retorno. Se existe filho w tal que low[w]=disc[u], então não há caminho alternativo de w para antecessores de u sem passar por u, logo u é vértice de corte. Complexidade: cada aresta e vértice é explorado uma vez ? O(V+E).

Explicação

O algoritmo utiliza a busca em profundidade (DFS) para explorar o grafo e identificar vértices de articulação com base nos tempos de descoberta e nos menores tempos alcançáveis. A condição que verifica se um vértice é um ponto de articulação se fundamenta na relação entre os tempos de descoberta e os valores de low, assegurando que a remoção do vértice desconectaria o grafo. A complexidade do algoritmo é eficiente, pois cada vértice e aresta é visitado uma única vez, resultando em O(V + E).

Raio-X da questão

Questões parecidas com resolução

• Na inscrição para uma oficina de robótica, a escola registra: nome completo, idade, turno escolhido e autorização da…
• — A estação da Praça das Mangueiras está aberta, mas só restam 3 bicicletas — avisou uma moradora ao serviço municipal…
• — Onde estão as peças ásperas em forma de estrela? — perguntou uma criança durante a montagem de um jogo tátil. O…
• — O caminhão só consegue visitar vinte contêineres por noite — avisou a coordenadora da coleta seletiva. Durante a…
• — A tela do empréstimo mostra primeiro a cor e depois a figura — explicou Nora, responsável pela brinquedoteca…
• — A linha 206 passou com a rampa disponível hoje? — perguntou uma usuária no ponto de ônibus. Durante um teste fictício…

Todas as questões de Programação - Tipos de dados