Prim’s Algorithm

       At first a peak is chosen in random order ,which for simplicity we accept it as V(1).This way two sets of pointers are initialized,the 0={1} and P={2…n}.          The O set (the O is taken from the Greek word Oristiko which means Terminal),will always contain the pointers of those peaks which are terminally attached in the T tree.The V(1) peak has already been attached in the Ttree.The P set( P is taken form the Greek word Prosorino which means Temporary) contains the rest of the pointers for the peaks,P={1…n}-O which are those pointers who have not been terminally connected with a node of T,that means they are not attached in the tree.
         In every execution of the Prim Algorithm a new peak will be connected to the T tree,not always with their numbering order, for example the V(4) peak can be connected to the tree before the V(2) peak.The corresponding pointer of the newly connected peak will be deleted from P set and will be inserted to the set.When all peaks are connected there will be O={1,…n} and P=0.This of course means the end of the algorithm.

         The new peak every time will be chosen by using greedy method ,among all sides of G which connect peaks already inserted in the T (pointers in the set ) tree with the rest of the peaks (pointers in the P set ),we choose one with minimum cost.If the chosen one is e(ij) then i belongs in the set , V(i) peak is already in the T tree, j belongs in the P set , and V(j) peak has not been attached in the T tree yet.We put V(j) in the T tree,we change the O set by putting the pointer,and we also change the P set by removing the pointer.

 

Pseudocode For The Prim Algorithm

 

INPUT :n,c[e(ij)],i,j belonging to {1,…,n}. 
OUTPUT :p(j) j=2,…,n (pointer of peaks j father in the T tree).

STEPS

  1. :(initializations).
    O={1} (V(1) root of the T tree).
    P={2,…,n}
    For every j belonging to :e(j):=c[e(j1)] , p(j)=1
    ( all peaks connected to the root.By definition of the cost function:e(j)=infinite when V(j) does not connect to V(1).).
  2. Choose a k for which e(k)<=e(j) for every j belonging to P.In case of tight choose the smaller one.
    Exchange the set with the set produced by the union of the O set and {k} . Exchange the P set with the set produced by the difference of the P set and {k} .(P<-P-{k}) If P=0 then stop.
  3. For every j belonging to P compare e(j) with c[e(kj)].
    If e(j) >c[e(kj)] exchange e(j) <-c(e(kj)).Go back to Step 1.






Other Pictures for Prim’s Algorithm

 

 

 
 
 
Source: CEID and Google
 
If you find this site useful, please support us. Like our FaceBook Page. You can also contact us by mail : portaltechinfo@gmail.com

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

<span>%d</span> bloggers like this: