home | news | contact | about
Prim's algorithm explained with java applet
25 October 2007, 10:56 PM
Prim's algorithm is another kind of a greedy algorithm, just like dijkstra's shortest path algorithm. However the difference is Prim's algorithm is to find a minimum spanning tree, not the least path taken as in dijkstra's. A minimum spanning tree is a tree having branches that are as short as possible. When all the branches are measured and summed it must be the smallest value possible.

In this article I thought that it would be good to use the actual terms used in graph theory for the geeky open and closed. An open node is a fringe vertex, a node that is visible and is a candidate for the next search node. A closed node is a tree vertex, a node that has been visited and added into the tree list. A tree is of course the minimum spanning tree. There is another term called the unseen vertex, a node that is not yet seen by the algorithm.

In Prim's algorithm implementation, we will need two kind of arrays. The fringe list and the tree list. The fringe list holds all nodes that are visible and the tree list is the resulting minimum spanning tree. Think of a fringe list as an open list and the tree list as the closed list. In the beginning of the search, both fringe and tree list has no elements, empty. Now if we are to find a minimum spanning tree starting from a certain node, lets say node a, we start the search by adding node a into the fringe list and begin the search from there. This basically covers the initialization step.

Prim's algorithm steps are:
  1. initilization
  2. pick a node with shortest branch/weight from fringe list as X
  3. find all neighbors of X as S
  4. for eash S as E
  5. if E is a member of tree return to step 4
  6. if E is already a member of fringe list and E to X is a shorter than E to E's current parent, reassign E's parent to X. return to step 4
  7. set E's parent to X, and put E into fringe list. return to step 4
  8. put X into tree list, and remove it from fringe list
  9. if fringe list is not empty, return to step 2
  10. the search is now complete

If we follow the steps above in the beginning of the search where there is only one node in fringe list, node a. We find that the node has no parent. This is expected because that node is the root and there cant be any other node before it. Check on the applet below to find the minimum spanning tree starting from node a, if you cannot see it better enable java applet or use a java capable browser, like Firefox :)

Your browser does not support Java applet!!

If the graph looks familiar, it is the same graph with the one from wikipedia's Prim Algorithm page.

Keep clicking on the applet to find the minimum spanning tree. A white node is the unseen node, a magenta node is a fringe node, and a light gray node is a tree node. Numbers between lines are the cost/length/weight of the path/branch/edge between two connecting nodes. Arrow lines indicates parent<-child relationship between nodes. It is encouraged that the reader works out a mental (or sketched) confirmation of above applet with all the steps described before. That should be very easy.

Here is a list of all searches.

unseen list fringe list tree list explanation
a,b,c,d,e,f,g nothing nothing everything is still unseen
b,c,d,e,f,g a nothing we want to start searching from a, so add it to the fringe list
c,e,f,g b,d a find all neighbors of a and put into fringe list. a is now added to tree list.
c,g b,e,f a,d d is selected because it has the smallest weight of 5. All its neighbors are added to the fringe list and d itself put into tree list.
c b,e,g a,d,f f is selected because it has the smallest weight of 6. f's neighbor e is already in fringe list, but seeing e to f (8) is shorter than e to d (15), e's parent is reassigned to f.
nothing e,g,c a,d,f,b b is selected with weight of 7. b's neighbor e is already in fringe list, but seeing e to b (7) is shorter than e to f (8), e's parent is reassigned to b.
nothing g,c a,d,f,b,e e is selected with weight of 7. Both g's and c's parent has been changed to e because those are shorter than to their original parents.
nothing g a,d,f,b,e,c c is selected with weight of 5. c's neighbors are all in tree list so don't bother.
nothing nothing a,d,f,b,e,c,g g is selected with weight of 9. g's neighbors are all in tree list so don't do anything. fringe list is now empty, ending the search. the tree list is the minimum spanning tree.

Last edited on 25 June 2009

Comments

~pallavi, 23 February 2010, 03:07 AM
plz keep the sample program
Post a comment~
Name*
algorithm has how many characters?*
Comment*
Notes: The comment system is moderated.
Meaning your comment will not show until reviewed.