Prim's algorithm

Definition: 
An algorithm for computing a minimum spanning tree. It builds upon a single partial minimum spanning tree, at each step adding an edge connecting the vertex nearest to but not already in the current partial minimum spanning tree.

See also Kruskal'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 T tree.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 O 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 O 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 O 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 j pointer,and we also change the P set by removing the j pointer.

This may seem to you extremely complicated but it is easily understood by a set of examples.

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 P :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 O 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.