Projete um algoritmo (explique a ideia e apresente pseudocódigo) que, dado um grafo não direcionado em lista…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir e simular algoritmos, de forma independente ou em colaboração, que resolvam problemas simples e do cotidiano com uso de sequências, seleções condicionais e repetições de instruções.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete um algoritmo (explique a ideia e apresente pseudocódigo) que, dado um grafo não direcionado em lista de adjacência, identifique todas as pontes (arestas cuja remoção aumenta o número de componentes). Indique também a complexidade em termos de n vértices e m arestas. Use os termos ponte, DFS, low e discovery.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Idéia: usar DFS com tempo de descoberta tin[u] e valor low[u]. Durante DFS, low[u] = min(tin[u], min(low[v] para filhos v), min(tin[v] para arestas de retorno)). Se ao explorar aresta u–v (v é filho) verificarmos low[v] > tin[u], então u–v é ponte. Pseudocódigo (resumido): timer=0 DFS(u,parent): visited[u]=true; tin[u]=low[u]=timer++ for v in adj[u]: if v==parent: continue if not visited[v]: DFS(v,u) low[u]=min(low[u], low[v]) if low[v] > tin[u]: report ponte (u,v) else: low[u]=min(low[u], tin[v]) Complexidade: O(n + m) tempo e O(n) espaço para vetores visited, tin e low.
Explicação
A abordagem utiliza a busca em profundidade (DFS) para explorar o grafo, permitindo calcular os tempos de descoberta e os valores low de cada vértice. A condição que verifica se uma aresta é uma ponte baseia-se na comparação entre o valor low do filho e o tempo de descoberta do pai, garantindo que a remoção da aresta realmente aumente o número de componentes. A complexidade O(n + m) reflete a eficiência do algoritmo, que visita cada vértice e aresta uma única vez.
Raio-X da questão
pontes em grafos
avaliacao
estruturas de dados em grafos · busca em profundidade (DFS)
Revisar algoritmos de busca em profundidade (DFS) e suas aplicações em grafos.
O aluno pode confundir a definição de ponte com outras propriedades de arestas em grafos, como arestas de corte, levando a uma implementação incorreta do algoritmo.
ciencia_tecnologia
criatividade
cientifico
Questões parecidas com resolução
- Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência, determine…
- Descreva um algoritmo em alto nível que, dado um grafo não direcionado representado por lista de adjacência, identifique…
- Descreva um algoritmo baseado em DFS para identificar vértices de articulação (cut vertices) em um grafo não direcionado…
- Descreva um algoritmo, indicando as variáveis-chave e os passos, para identificar todos os vértices de articulação (cut…
- Descreva em pseudocódigo, definindo registros e variáveis, um algoritmo que utilize busca em largura (BFS) para…
- Escreva em linguagem descritiva um algoritmo que, recebendo a lista de adjacência de um grafo não direcionado, retorne…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog