Estruturas de Dados e Algoritmos 06/07

[67] Problema A - Diâmetro de uma árvore


O problema

A função básica das redes de comunicação de hoje é a transmissão de pacotes de dados entre computadores, processadores, ou outros periféricos. A figura seguinte ilustra uma árvore binária completa com 3 entradas e 3 saídas. Os quadrados representam nós terminais, origem ou destino dos pacotes de dados, e os círculos representam os switches de comunicação que direccionam os pacotes na rede. Um switch recebe pacotes através das ligações de entrada e encaminha-os através das ligações de saída. Assim, um pacote quando emitido numa entrada atravessa um conjunto de nós (hops) até à saída. Como uma árvore fornece caminhos únicos entre dois nós, é possível sempre encaminhar um pacote de dados de forma única até ao destino.

Um dos objectivos de uma rede de comunicações é minimizar a latência de comunicação, i.e. minimizar o número de switches pelos quais um pacote tem de passar desde a origem até ao destino. Numa rede como a da figura, a maior latência corresponde à maior distância entre nós terminais (medida pelo número de nós (switches)). Este valor corresponde ao diâmetro da árvore, que numa árvore binária completa é dado por 2log(N) + 2, em que N é o número de entradas e de saídas.

Uma forma de reduzir o diâmetro de um rede é usar switches mais "largos". Os da figura admitem 3 entradas e 3 saídas (3x3), mas se usássemos switches 4x4, poderíamos construir uma árvore ternária com um diâmetro menor.

O desafio que aqui colocamos é escrever um programa em que dada uma configuração de uma árvore de aridade-K, possivelmente não completa, determine o seu diâmetro. Os dois exemplos seguintes ilustram dois casos possíveis de árvores dadas e os respectivos diâmetros.

No caso de árvores binárias (aridade-2), o diâmetro de uma árvore T é a maior das seguintes quantidades:

Deverá generalizar esta definição para árvores de aridade superior a 2.

Input

A primeira linha contém um número C, indicando o número de casos que se seguem:
Cada um dos casos é descrito por duas linhas com o seguinte formato:

Output

Para cada caso devem imprimir o número do caso e o valor calculado para o diâmetro da árvore correspondente, no formato dado no exemplo.

Exemplo de input/output

O exemplo corresponde às árvores da segunda figura acima.
InputOutput
2
2
2 2 0 2 0 0 1 1 2 2 0 0 0
2
2 2 2 0 2 0 0 1 2 0 2 0 0 1 0
Caso 1: 9
Caso 2: 8

Última actualização: