Objetivo:
Implementar o algoritmo de spanning tree, como definido por Kruskal.
Seu programa deve ler uma lista de arestas, que interligam dois roteadores específicos,
com um custo de comunicação associado a cada aresta. Deve então ler uma série de
vértices de origem de tráfego, retornando para cada um a árvore de espalhamento mínima
(lista das arestas que a comporão). Os dados serão lidos de um arquivo na forma:
N
R1,1 R1,2 C1
R2,1 R2,2 C2
...
Rn,1 Rn,2 Cn
V1 V2 ... Vk
Em que:
N = número de arestas
Ri,j = indicam quais
vértices são ligados pela aresta i
Ci = custo da aresta i
Vk = vértice de origem da árvore k
O programa termina quando Vn=0.
Observação: Considere um máximo de 100.000 arestas.
Data de entrega:
30/11, até as 23:59 horas (horário de recebimento da mensagem).
|