Prim's algorithm explained with java applet

25 October 2007, 10:56 PM

*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:

- initilization
- pick a node with shortest branch/weight from fringe list as X
- find all neighbors of X as S
- for eash S as E
- if E is a member of tree return to step 4
- 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
- set E's parent to X, and put E into fringe list. return to step 4
- put X into tree list, and remove it from fringe list
- if fringe list is not empty, return to step 2
- 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 :)

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

Post a comment~

pallavi, 23 February 2010, 03:07 AM