Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

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.