PRIMS ALGORITHM

 

If you want to go straight to the applet click here or for information and instructions read on……!!!!!!!

ABOUT PRIMS

This Applet implements the Prims algorithm for minimum spanning tree. This algorithm uses the "greedy" strategy for growing the tree. The basic strategy is to add to the current tree the shortest(minimum weight) edge to the current tree. The tree starts with the root or in this case node zero.

Each node contains some information , namely it’s key and its parent in the tree. The key’s are initialized to infinity(a very high value) and the parent to null .

As the algorithm progresses the keys are decreased depending on it’s proximity to the current tree. The parents are set as the preceding node in the tree.

ABOUT THE APPLET :

This applet shows the working of the algorithm. It allows the user to choose various graphs and see how the algorithm goes about growing it’s MST. The applet shows how the algorithm reduces keys of the nodes and the assignment of the parent of each node. The instructions forrunning the applet are given in the lower left corner area.

There are three types of inputs one can supply the algorithm. I have given some ready made examples which are for convenience. These consist of some "simple" graphs which can be used to see the basic running of the algorithm.

Next is a random input. Which generates a random graph for the algorithm . These graphs are limited to 7 vertices . This is only been done to try and keep the generated graph small enough to be useful !

The next type of input is a user input graph which allows the user to input any graph. Again there is a limitation on the number of vertices . This is done for neatness and not because the algorithm can not handle a higher number.

The instructions are fairly simple. After the input graph is displayed the user needs to press the "Start" button to start the animation. The animation shows the growth of the tree by showing the tree edges in red. As the algorithm progresses it decreases the key and changes the parent of the various vertices.This is done by examining the edges of each node. This is shown by a change in color of the edges and the node being examined and the result is shown in the two arrays on the side.

The inputs can be given by pressing the corresponding buttons. The user input is a bit more(only a bit!) complicated.

Once the "User" button is pressed the user needs to supply all the vertices by right clicking the mouse in the drawing area on the locations he wants the vertices in. Once all the vertices are plotted one goes about adding edges. . This is done by choosing(right clicking ) on the source and destination vertex. Once done a edge will be displayed in between these two vertices. Now one has to give the edge a weight. This is done by choosing a weight by the scroll bar. The weight represented currently by it will be displayed on the bottom of the applet . The user adjusts it until he/she gets the desired weight and then he presses the "Weight" button. Unless this is pressed the corresponding edge will not be added. Once the user has finished inputting the graph press the "Start " button.

All instructions will be displayed in the lower left area of the applet.

On To The Applet!!!

The Java Source files : Vertex.java and Prims.java

BY!!

Amlan Sengupta

1