Skip to content

Kruskal v. Prim, to the death!

By Nathan Yergler
— Sunday, February 26, 2006 at 11:37 pm

This semester I have an Algorithms course, and it’s actually turning out to be one of my favorites. So for our second project we were instructed to implement a Java applet which generated a set of nodes on a graph and the edges (or some subset of) between them, and then used “Kruskal’s”:http://en.wikipedia.org/wiki/Kruskal%27s_algorithm or “Prim’s”:http://en.wikipedia.org/wiki/Prim%27s_algorithm algorithm to find the “minimal spanning tree”:http://en.wikipedia.org/wiki/Minimal_spanning_tree, animating the process. And even though it’s Java, and even though it’s an applet, I’ve been oddly fixated by it lately. So you can check out my “second implementation”:http://yergler.net/courses/CS486/project2a, which lets you pick which algorithm to use and then sit back and watch the pretty nodes. Oooooh.

3 Comments

Categories: development.

Comment Feed

3 Responses

  1. Were I can find the code for this applet. i have a project to make and i can’t find anything that will help me. I have to make an applet for kruskal algorithm. the teacher didn’t explain very well at the course and it’s very hard to start work in java.

    Please mail me. I’m desperate. I don’t need prim’s algorithm, just kruskal.

    Vasile Manu (Romania) — Monday, January 11, 2010 @ 8:19 am — Reply

Continuing the Discussion

  1. [...] After Ian’s talk I indulged my current algorithmic obsession and went to Simplying Red-Black Trees. Once the presenter found the room (seriously, there were 3 to choose from), he presented a metaclass he’s used to simplify the implementation of red-black trees at a small performance cost. The basic approach involves identifying attributes which have symmetric behavior, and can therefore be “swapped”. In the case of rb trees, this is the left and right child nodes. [...]

    PyCon Day 3: Winding Down at the law of averages — Tuesday, March 7, 2006 @ 9:03 am