Projete um algoritmo em pseudocódigo que, dada uma árvore enraizada representada por nós com referências a…

Questão

Projete um algoritmo em pseudocódigo que, dada uma árvore enraizada representada por nós com referências a filhos e uma variável inteira k, retorne a lista de todos os nós cuja distância em arestas até a raiz é igual a k. Descreva as variáveis-chave e analise a complexidade.

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

Resposta esperada

Resposta modelo (BFS por níveis): func nós_à_distância_k(raiz, k): if raiz == null: return [] fila = [(raiz,0)] # (nó, distância) resultado = [] while fila não vazia: (n, d) = dequeue(fila) if d == k: resultado.append(n) if d > k: continue for filho in n.children: enqueue(fila, (filho, d+1)) return resultado Variáveis-chave: fila (estrutura FIFO de pares), n (nó atual), d (distância atual), resultado (lista de nós). Complexidade: percorre cada nó no máximo uma vez ? tempo O(n) e espaço O(n) no pior caso (fila + resultado).

Explicação

O algoritmo utiliza uma abordagem de busca em largura (BFS) para explorar a árvore nível por nível, permitindo que a distância dos nós até a raiz seja facilmente rastreada. A fila armazena pares de nós e suas respectivas distâncias, garantindo que cada nó seja visitado uma única vez, o que resulta em uma complexidade linear em relação ao número total de nós. A estrutura do código é clara e eficiente, permitindo a coleta dos nós desejados de forma organizada.

Raio-X da questão

Questões parecidas com resolução

• Desenvolva um algoritmo em pseudocódigo que, dado um grafo não direcionado conectado e um vértice raiz, construa a…
• Projete uma solução computacional (estrutura de dados e algoritmo em alto nível) que, dado um grafo não direcionado…
• Descreva um algoritmo em pseudocódigo que, dada uma árvore enraizada onde cada nó mantém uma lista arbitrária de filhos…
• Projete um algoritmo em pseudocódigo que, dada uma árvore de decisão codificada como nós com condição e referências a…
• Descreva em pseudocódigo um algoritmo que, dada uma rede representada por um grafo com n nós e lista de arestas…
• Projete um algoritmo (pseudocódigo) baseado em Kruskal ou Prim que, dado um grafo conectado ponderado (dados: lista de…

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