European Experts Exchange (EEE.org) :: Free Experts PHP MySql Oracle Microsoft Web SQL Delphi


Algorithms :: Maths :: Kruskal 's algorithm
By: collegeBoy	Date: 14/01/2003 00:00:00	Points: 300	Status: Answered Quality : Excellent
Hi there... I'm doing a school project, that has to do with the TSP problem... Several of the methods I'm writing about need a MST - and I've choosen to get this from the Kruskal algorithm... I've tried to make a method for working out the kruskal MST of my graph, but it doesn't seem to work. I think I'm close to the solution, but not quite... Maybe this should be posted in the programming section, but it's more of a math-question than programming. (right?) Anyway I'm trying to get it done with a recursive method, I think that should be the way to do it.. What I'm asking is for a complete code in either java or delphi that I could read (and understand, so not with applets or stuff in java, I prefer plain text input and output. I'm mostly into delphi). One that takes a matrix (with the weights of the edges) as input (or also static in the program, wouldn't matter for the understanding) and outputs the edges taken to construct the MST. I've been looking around, and there seems to be C++ codes everywhere. Unfortunately I dont understand C++ very well - at least not yet... I ofc have no problems doing Kruskal by hand, and only need this as some extra understanding for myself - the programming isn't getting rated or anything by the school, so it isn't cheating getting help with it :)
By: VGR	Date: 14/01/2003 08:49:00		Type : Comment
no idea what you're writing about 8-) but you may show me your C++ code that you don't understand and we'll translate it to (readable) Pascal ;-)

By: progGoon	Date: 14/01/2003 09:45:00		Type : Comment
Would this help? <A HREF="http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml">http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/kruskal/Kruskal.shtml</a>

By: VGR	Date: 14/01/2003 18:04:00		Type : Comment
sure. sounds not too complicated. Works on connected graphs, not on oriented ones, good point. What is the "cup" operator ? Given the shape of a cup, I guess that's U, the symbol of union. Right ?

By: collegeBoy	Date: 15/01/2003 20:18:00		Type : Comment
It's a complete, not-oriented graph.. I have been looking at that java thing you posted (found it before, but it doesn't give all that much sense to me) I've got the weights of the graph in a 2d array int[][] weights; I can do the trick about getting it to find the edge with the lowest weight and adding that to my other array, containing the (solution) edges.... that is no trick at all.. The problem comes when I want to know if the next edge I'm adding, will give me a circuit... Say, I've got the edges 0->1, 0->2 and 2->3 Now I find that the next one I want to add is 1->3 - how do I check if that will give me a circuit? I need it to find that 1 is connected to 0, which is connected to 2, which is connected to 3, and therefore I can't add it, as it would give me a circuit. I would think that a recursive solution would be the correct one, but I seem to be unable to create it, at least simply. That would actually be the part of the solution that I need... :)

By: VGR	Date: 15/01/2003 20:30:00		Type : Answer
yes, we could show you design solutions for detecting a clique or circuit, but as your hraph is complete, you know that all connections are possible. Given that you have memorized 0->1, 0->2 and 2->3 as "taken", it's clear that adding 2->3 will connect the subgraph (path) and produce a "circuit" personally, I wold build in memory an "image" of the complete graph, with indicators of "taken or not", like a chain of : Type PMyRec=^MyRec; MyRec = Record originsummit : Byte; destSummit : Byte; taken : Boolean; next, previous : PMyRec; End; // Record then computing that a new-to-be-added-candidate edge makes a circuit would be this algorithm : -given that you want to add X->Y -check all "taken" edges Y->something, until exhaustion or having found X as a destination - if X found, there is a circuit very CPU-consuming

By: collegeBoy	Date: 15/01/2003 21:51:00		Type : Comment
I managed (after a longer search) to find an example on the net, that was useful. (<A HREF="http://www.programmersheaven.com/c/AllSubmissions.asp?UserID=14619">http://www.programmersheaven.com/c/AllSubmissions.asp?UserID=14619</a>) It was quite easy to read, not using applets and stuff like that... Thanks for the help, though.

Do register to be able to answer

©2010 These pages are served without commercial sponsorship. (No popup ads, etc...). Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE.
Please DO link to this page! Post to Plurk Post to Yahoo Buzz Post to Delicious Post to Digg Post to MySpace Post to Ping.fm Post to Reddit Post to StumbleUpon

Contact

page generated in 343.976020 milliseconds

Why Google AdSense ads ?

New Improved Search!