0 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 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.

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 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.

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

0 How to measure time taken by a function in C?

                  To calculate time taken by a process, we can use clock() function which is available time.h. We can call the clock function

0 Program: Pascal’s Triangle

                                Pascal’s triangle is a triangular array of the binomial coefficients. Write a function that takes an integer value n as input and prints first n lines of the Pascal’s triangle. Following are the first 6 rows of Pascal’s Triangle.

1 

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

0 Program: Next higher number with same number of set bits

Given a number x, find next number with same number of 1 bits in it’s binary representation.

For example, consider x = 12, whose binary representation is 1100 (excluding leading zeros on 32 bit machine). It contains two logic 1 bits. The next higher number with two logic 1 bits is 17 (10001₂).

0 Program: Lowest Common Ancestor in a Binary Search Tree

Given the values of two nodes in a *binary search tree*, write a c program to find the lowest common ancestor. You may assume that both values already exist in the tree.

The function prototype is as follows:

 int FindLowestCommonAncestor(node* root, int value1, int value)

  I/P : 4 and 14

  O/P : 8

  (Here the common ancestors of 4 and 14, are {8,20}.

  Of {8,20}, the lowest one is 8).

0 Programs: Reverse a Linked List in groups of given size

Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

Example:

Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3

Output:  3->2->1->6->5->4->8->7->NULL.

Inputs:   1->2->3->4->5->6->7->80->NULL and k = 5

Output:  5->4->3->2->1->8->7->6->NULL.

1 Print a given matrix in spiral form

Given a 2D array, print it in spiral form. See the following examples.

Input:

        1    2   3   4

        5    6   7   8

        9   10  11  12

        13  14  15  16

Output:

1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10