Re: Kruskal
- Subject: Re: Kruskal
- From: Leonidas O Brandao <leo@ime.usp.br>
- Date: Mon, 5 May 2003 11:55:12 -0300 (EST)
Olá
On Sat, 3 May 2003, Tiago Motta Jorge wrote:
> Olá,
>
> Alguém lembra o que era o Kruskal? Talvez eu não tenha anotado e minha
> memória não está colaborando. Era algum algoritmo sobre grafos...
>
> Desde já agradecido,
> Tiago Motta Jorge.
É "aquele" algoritmo "guloso" para construir árvore espalhada de custo
mínimo (ou máximo): ordena-se as arestas de acordo com seu custo
(cresc. ou decresc. de acordo c/ a fç objetivo) e vai pegando "da
esquerda p/ a direita, na ordem", ficando c/ aquelas q/ não formam
circuitos.
Até
Leônidas
--------------------------------------------------------------------------
Leônidas de Oliveira Brandão - Computer Science Dep. of IME-USP (Brazil)
leo@ime.usp.br - http://www.ime.usp.br/~leo - +55 (011) 3091 [6298 | 6135]
Interessado em Matemática? Visite o "iMatica": http://www.matematica.br
- References:
- Kruskal
- From: Tiago Motta Jorge <tigod@linux.ime.usp.br>