Descreva e escreva em pseudocódigo um algoritmo eficiente para calcular o diâmetro (comprimento do maior…

Questão

Descreva e escreva em pseudocódigo um algoritmo eficiente para calcular o diâmetro (comprimento do maior caminho entre dois vértices) de uma árvore não orientada. Justifique por que o método funciona e analise sua complexidade temporal e espacial.

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

Resposta esperada

Método (duas BFS): 1) Escolha um vértice arbitrário s. Execute BFS a partir de s para encontrar o vértice v mais distante. 2) Execute BFS a partir de v para encontrar o vértice w mais distante e registre a distância d(v,w). d(v,w) é o diâmetro da árvore. Pseudocódigo (assume lista de adjacência): function BFS_farthest(start): queue ? empty queue enqueue(queue, start) dist[start] ? 0 visited[start] ? true farthest ? start while queue not empty: u ? dequeue(queue) for each neighbor n of u: if not visited[n]: visited[n] ? true dist[n] ? dist[u] + 1 enqueue(queue, n) if dist[n] > dist[farthest]: farthest ? n return (farthest, dist[farthest]) function tree_diameter(any_vertex): (v, _) ? BFS_farthest(any_vertex) (w, diameter) ? BFS_farthest(v) return diameter Justificativa: em árvores, a BFS a partir de um vértice extremo encontra outro extremo; repetir a partir desse extremo alcança o maior caminho. Complexidade: cada BFS é O(N) tempo e O(N) espaço (N = número de vértices), logo o algoritmo é O(N) tempo e O(N) espaço.

Explicação

O método utiliza a propriedade das árvores de que o maior caminho entre dois vértices sempre termina em vértices extremos. A primeira busca encontra um desses extremos, e a segunda busca determina a distância máxima a partir dele, garantindo que o resultado seja o diâmetro. A complexidade do algoritmo é linear em relação ao número de vértices, pois cada busca em largura percorre todos os vértices e arestas uma única vez.

Raio-X da questão

Questões parecidas com resolução

• Desenvolva um algoritmo em pseudocódigo que, dado um grafo conectado com pesos não negativos e um vértice origem…
• Escreva um pseudocódigo que, dado um grafo não orientado representado por lista de adjacência, retorne o número de…
• Dada uma tabela de frequências (símbolo ? frequência) obtida por amostragem, elabore um algoritmo em pseudocódigo que…

Todas as questões de Leitura e interpretação de tabelas e gráficos (de colunas ou barras simples ou múltiplas) referentes a variáveis categóricas e variáveis numéricas