Boruvka's Minimum Spanning Tree algorithm
[1/5] from: lmecir::mbox::vol::cz at: 13-May-2004 23:54
I posted a Rebol implementation of Boruvka's classic Minimum Spanning Tree algoritm to http://www.compkarori.com/vanilla/display/Graph Any questions, comments, corrections and improvements welcome. -L
[2/5] from: lmecir:mbox:vol:cz at: 16-May-2004 15:39
Ladislav Mečíř napsal(a):
>I posted a Rebol implementation of Boruvka's classic Minimum Spanning >Tree algoritm to http://www.compkarori.com/vanilla/display/Graph > >Any questions, comments, corrections and improvements welcome. > >-L >
FYI, in http://www.library.cornell.edu/nr/bookcpdf/c8-6.pdf I found a function Eclass. The algorithm of it is attributed to D.E. Knuth. I found out, that the Eclass function if MUCH slower (for large number of nodes), than the combination of the Components and Adjacency functions you can find above. -L
[3/5] from: reblist:codeconscious at: 19-May-2004 21:04
Hi Ladislav, I like your choice of edge representation - flexible. Haven't had a lot of time to play with it, but I'm keeping it in the back of my mind as something potentially quite useful. Thanks for posting it, Brett.
[4/5] from: lmecir:mbox:vol:cz at: 19-May-2004 18:39
Brett Handley napsal(a):
>Hi Ladislav, > >I like your choice of edge representation - flexible. >
....snip... yes, that was my primary goal, but for this algorithm (and maybe for some other), the adjacency structure used instead of a block of graph edges might lead to a simpler formulation. (But there would be a problem, where to store edge weights - any idea?) -L
[5/5] from: reblist:codeconscious at: 20-May-2004 21:47
Can't really suggest anything unfortunately . I find the process of choosing REBOL representations for my informaion always illuminating and always tough. Regards, Brett.