Prof., não entendi muito bem o enunciado da última questão da tarefa 22. O enunciado diz para implementar o Boruvka que começa por colocar as arestas do grafo em ordem crescente de pesos.
O algoritmo acaba colocando as arestas externas nas componentes em ordem crescente de peso, não? Isto é, quando eu tenho uma componente C, eu procuro na franja a aresta que tiver o menor peso e seleciono-a, certo? Se eu estiver errado, me corrijam!
Então, não sei o que devo fazer com o algoritmo. Tenho que deixar o Boruvka com cara de Kruskal?
Abs,
Victor
Sim.
--Paulo
--Paulo
Coloque as arestas do grafo em ordem
crescente de peso. Agora reescreva a
implementação do algoritmo de Boruvka
procurando tirar proveito da informação
a[0].wt <= a[1].wt <= ... <= a[E].wt.
O efeito final é o mesmo do algoritmo de
Kruskal? Humm. Boa pergunta. Não tenho
certeza disso não.
--Paulo
crescente de peso. Agora reescreva a
implementação do algoritmo de Boruvka
procurando tirar proveito da informação
a[0].wt <= a[1].wt <= ... <= a[E].wt.
O efeito final é o mesmo do algoritmo de
Kruskal? Humm. Boa pergunta. Não tenho
certeza disso não.
--Paulo