 |  |  |
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.
Click to see the PSEUDOCODE for the Prim algorithm.
You can also see an example of prim algorithm using the adjoining array (in Java of course)
| | |
HTML PAGE DIRECTOR :Papaioannou Panagiotis