DATA STRUCTURE AND ALGORITHM FULL NOTES

DATA STRUCTURE AND ALGORITHM FULL NOTES WITH PROGRAMMING EXAMPLES....

1. POLISH NOTATION
According to the position of a binary operator, an expression can be of three types:
i) Infix Expression: An expression is said to be infix if the position of the operand is in
between the two operands. Thus the general syntax is “operand1 operator operand2”.
Ex: a+b, a*b, a/b, a$b, a+b*c etc.
ii) Prefix expression: An expression is said to be prefix if the position of the operand is
before the two operands. Thus the general syntax is “operator operand1 operand2”.
Ex: +ab,*ab, /ab, +*abc, *+abc etc.
iii) Postfix expression: An expression is said to be postfix if the position of the operand is
after the two operands. Thus the general syntax is “operand1 operand2 operator”.
Ex: ab+, ab*, ab/, abc+*,abc*+ etc.


Precedence and Associativity of the operators:
OPERATOR ASSOCIATIVITY PRECEDENCE
$ RIGHT TO LEFT HIGHEST
*,/,% LEFT TO RIGHT
+,- LEFT TO RIGHT LOWEST
NOTE: OPERATORS WITH SAME PRECEDENCE EXECUTES ACCORDING TO THEIR
ASSOCIATIVITY



PREFIX AND POSTFIX OF CORRESPONDING INFIX EXPRESSION
INFIX POSTFIX PREFIX
A+B AB+ +AB
A+B-C AB+C- -+ABC
(A+B)*(C-D) AB+CD-* *+AB-CD
A-B/(C*D$E) ABCDE$*/- -A/B*C$DE
A$B*C-D+E/F/(G+H) AB$C*D-EF/GH+/+ +-*$ABCD//EF+GH
((A+B)*C-(D-E))$(F+G) AB+C*DE - - FG+$ $-*+ABC-DE+FG

2. EVALUATION OF A POSTFIX EXPRESSION
ALGORITHM
While (not end of postfix string)
{
symb=next element of the postfix string
if(symb is an operand)
{
push(stack,symb);
}
else if( symb is an operator)
{
val1= pop(stack);
val2= pop(stack);
result= apply symb on val2 and val1;
push(stack,result);
}
}
result= pop(stack);
return result;
Note:
Stack here is a character array having the logic of first in last out or last in first out and push
and pop are the standard insert and retrieve operations in stack.

3. STACK STATUS
EX1: 7,8,+,2,3,-,*
Symbol Read Operation Op1 Op2 Evaluation Value Stack
7 Push(7) - - - 7
8 Push(8) - - - 8,7
+ Pop, Pop 8 7 7+8 15 Empty
NOP Push(15) - - - - 15
2 Push(2) 2,15
3 Push(3) 3,2,15
- Pop(),pop() 3 2 2-3 -1 15
NOP Push(-1) -1,15
* Pop(),pop() -1 15 -1*15 -15 Empty
NOP Push(-15) -15
NOP Pop() -15 - - - Empty

Result= -15
Ex2: 6,2,3,+,-,3,8,2,/,+,*,2,$,3,+
Symbol Read Operation Op1 Op2 Evaluation Value Stack
6 Push(6) - - - - 6
2 Push(2) - - - - 2,6
3 Push(3) - - - - 3,2,6
+ Pop(), pop() 3 2 2+3 5 6
NOP Push(5) - - - - 5,6
- Pop(),pop() 5 6 6-5 1 Empty
NOP Push(1) - - - - 1
3 Push(3) - - - - 3,1
8 Push(8) - - - - 8,3,1
2 Push(2) - - - - 2,8,3,1
/ Pop(), pop() 2 8 8/2 4 3,1
NOP Push(4) - - - - 4,3,1
+ Pop(),pop() 4 3 3+4 7 1
NOP Push(7) - - - - 7,1
* Pop(), pop() 7 1 1*7 7 Empty
NOP Push(7) - - - - 7
2 Push(2) - - - - 2,7
$ Pop(),pop() 2 7 7^2 49 Empty
NOP Push(49) - - - - 49
3 Push(3) - - - - 3,49
+ Pop(),pop() 3 49 49+3 52 Empty
NOP Push(52) - - - - 52
NOP Pop(52) 52 - - - Empty

Result =52

4. C IMPLEMENTATION OF EVALUATION OF POSTFIX STRING
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# include <math.h>
# define SIZE 100

// Declaration of stack structure

typedefstruct stack
{ double item [SIZE] ;
int top ;
} stack ;

// Prototype declaration of functions

void push ( stack * , double) ;
double pop ( stack * ) ;
double evaluate ( char [ ] ) ;
double operate ( double, double, char ) ;

// Function Definitions

void push ( stack * sp , double value )
{
if ( sp -> top == SIZE - 1 )
{
printf (" \n stack overflow ……..");
exit (0);
}
sp ->item [ ++sp ->top ] = value ;
}
double pop ( stack *sp )
{
if ( sp->top == - 1 )
{

5. printf (" \n stack underflow ……..");
exit (0) ;
}
return (sp->item[sp->top--]) ;
}

// Starting main()

int main ()
{
char postfix [ SIZE ] ;
double value ;
printf(" \n Enter postfix string seperated by comma:");
scanf("%s" , postfix ) ;
value = evaluate (postfix);
printf (" \n value of the given expression is=%lf",value);
getch();
return 0;
}

// Evaluation of the postfix expression

double evaluate ( char postfix [ ] )
{
stack s ;
int i, j ; double result, value, value1, value2 ;
char temp [20];
s.top =-1; i = 0;
while(postfix[i]!='\0')
{
j=0;
while ( postfix [i] != ',' && postfix [i]!='\0' )
{
temp[j++] = postfix[i++] ;
}
temp [j] ='\0';
value = atof(temp);
if ( value!=0)
{
push (&s, value ) ;

6. }
else if ( value == 0 && temp [0]!= 0)
{
value1 = pop(&s);
value2 = pop(&s);
result = operate(value2,value1, temp[0]);
push(&s, result ) ;
}
if ( postfix [i]!='\0')
i++;
}
result= pop(&s);
return result;
}

// Calculating the result on the basis of the operator

double operate (double left, double right, char opr)
{
double result = 0.0;
switch (opr)
{
case '+' : result = left + right ;
break ;
case '-' : result = left - right ;
break ;
case '*' : result = left * right ;
break ;
case '/' : result = left / right ;
break ;
case '$' : result = pow(left,right ) ;
break ;
}
return result ;
}

7. O/P: [EX1, EX2]








INFIX TO POSTFIX CONVERSION
ALGORITHM
1. Create a stack
2. for each character „t‟ in the input stream {
 if (t is an operand)
add „t‟ to the output postfix string
 else if ( till the stack is not empty and priority of stack top is higher than
the current symbol read){
POP and add it to the output postfix string if not opening parenthesis
}
 if (current symbol is not closing parenthesis){ Push the symbol into stack
else{ pop and add it to the output postfix string}
}

3. POP and add the remaining symbols to the output postfix string until the
stack is empty.

8. STACK TRACE

EX:A * B – (C + D) + E

INPUT
CHARACTER OPERATION ON STACK STACK
POSTFIX
EXPRESSION
A

Empty A
* Push * A
B

* A B
– Check and Push – A B *
( Push – ( A B *
C

– ( A B * C
+ Check and Push – ( + A B * C
D

– ( + A B * C D
)
Pop and append to postfix till
„(„ – A B * C D +
+ Check and push + A B * C D + –
E

+ A B * C D + – E
End of Input Pop till Empty Empty A B * C D + – E +

9. C IMPLEMENTATION FOR INFIX TO POSTFIX CONVERSION

//INFIX TO POSTFIX CONVERSION
#include<stdio.h>
#include<conio.h>
#define SIZE 100
struct stack
{
char item[SIZE];
int top;
};
struct stack s;
enumboolean
{
f=0, t=1,

};
void push(struct stack *,char);
char pop(struct stack *);
void convert(char[],char[]);
booleanprec(char,char);
int main()
{
char postfix[SIZE],infix[SIZE];
printf("\n ENTER THE INFIX STRING:");
scanf("%s",infix);
convert(infix,postfix);
printf("\n THE REQUIRED CONVERTED ANSWER IS:%s",postfix);
getch();
return 0;
}
void convert(char infix[],char postfix[])
{
int i=0,j=0;
s.top=-1;
charsymb;
while(infix[i]!='\0')
{
if(infix[i]>='0'&&infix[i]<='9')

10. {
while(infix[i]>='0'&&infix[i]<='9')
{
postfix[j++]=infix[i++];
}
postfix[j++]=',';
}
if(infix[i]=='*'||infix[i]=='/'||infix[i]=='+'||infix[i]=='-
'||infix[i]=='$'||infix[i]=='('||infix[i]==')')
{
while(s.top!=-1 &&prec(s.item[s.top],infix[i]))
{
symb=pop(&s);
if(symb!='(')
{
postfix[j++]=symb;
postfix[j++]=',';
}
}
if(infix[i]!=')')
push(&s,infix[i]);
else
{
symb=pop(&s);
if(symb!='(')
{
postfix[j++]=symb;
postfix[j++]=',';
}
}

}
if(infix[i]!='\0')
i++;
}
while(s.top!=-1)
{
symb=pop(&s);
if(symb!='(')
{

11. postfix[j++]=symb;
postfix[j++]=',';
}

}
postfix[j]='\0';

}
booleanprec(char left, char right)
{
boolean success=f;
if(left=='('||right=='(')
success=f;
if(right==')')
success=t;
if(left=='*')
{
if(right=='*'||right=='+'||right=='-')
success=t;
else
success=f;
}
if(left=='/')
{
if(right=='*'||right=='/'||right=='+'||right=='-')
success=t;
else
success=f;
}
if(left=='+'||left=='-')
{
if(right=='+'||right=='-')
success=t;
else
success=f;
}
if(left=='$')
{
if(right=='$')
success=f;

12. else
success=t;
}
return success;
}
void push(struct stack *sp,char value)
{
if(sp->top==SIZE-1)
{
printf("\n OVERFLOW");
return;
}
else
{
sp->top++;
sp->item[sp->top]=value;
}
}
char pop(struct stack *sp)
{
if(sp->top==-1)
return -9999;
else
returnsp->item[sp->top--];
}

13. TREE
DEFINITION: A tree is a finite set of one or more nodes such that,
i. There is a specially designated node known as root
ii. The remaining nodes are partitioned into n>=0 disjoint sets T1,T2,……Tn
where each of these sets is tree. The sets T1,T2,……Tn are the sub- trees of
the root.
The sets are disjoint with each other, since they are not interconnected by
any link or edge.

T1 T2




T3


A Sample Tree T
In the sample tree T there is a set of 11 nodes. Here A is a specially designated
node, root of the tree. The remaining nodes are partitioned into 3 disjoint sets T1,
T2, T3 they are sub-trees of the root. The same tree can be expressed in a string
notation: T= (A(B(E,F),C(G(M)),D(H,K,L))
TERMINOLOGIES:


F
D
A
B
C
G
E
K H
A
B
F
D

L E H K G
C
M

14. TREE
NODE- Each element of the tree is known as node, and represented by a circle.
EDGE- The lines connecting the nodes are called edges or branches.
PARENT- The immediate predecessor of any node is called the parent node. Ex: A
is the parent of nodes B, C, D and C is parent of F.
CHILD- All the immediate successors of a node are its children. Ex: B, C, D is
children of A and G is a child of D and H is a child of E.
SIBLING- Two or more children having same parent are called siblings or brothers.
Ex: B, C, D is siblings, since children of same parent A.
LEAF- A node does not have any child known as leaf node. Ex: H, F, K.
DEGREE- The number of sub-trees or children of any node is called the degree of
a node. Ex: deg (A) =3, deg (B) =1, deg (F) =0.
The degree of a tree is the maximum degree of a node in the tree. Ex: the degree
of the above tree is 3.
LEVEL- level of any node is the distance of that node from the root. The level of
the root is 0 and the level of any node is one more than the level of its parent. Ex:
level (A) =0, level (B) = 0+1=>1, level (E) =1+1=>2, level (H) = 2+1=>3
DEPTH- The maximum level of any node is known as the depth of the tree. Ex: the
depth of the above tree is max (0, 1, 2, 3) =3
HEIGHT- The total number of levels in the tree is known as the height of the tree.
Ex: the height of the above tree is 4, since there are four levels 0, 1, 2, 3.
FOREST-A forest is a set of n>=0 disjoint trees, that is, removing the root of tree,
will make it a forest.

15. PATH- Path of a node is defined as the sequence of nodes N1, N2,….., Nm such that
each node Ni is parent of node Ni+1 where 1<i<m. there is only one path between
two nodes. The path length is the number of edges in the path.
ANCESTERAND DESCENDENT- Any node Na is said to be the ancestor of the node
Nm if Na lies in the unique path from the root to the node Nm. Ex: D is an ancestor
of the node K. if Na is an ancestor of the node Nm then Nm is called the descendent
of node Na.
INTERNAL NODE- All the non leaf nodes are known as internal nodes. Ex: A, B, C,
D, E, G.
EXTERNAL NODE- All the leaf nodes are also known as external nodes. Ex: H, F, K.
INTERNAL PATH LENGTH- Sum of the levels of the internal nodes is known as
internal path length. Ex: level(A)=0, level(B)=1, level(C)= 1, level(D)=1, level(E)=2,
level(G)=2, therefore the internal path length is= 0+1+1+1+2+2=7
EXTERNAL PATH LENGTH- Sum of the levels of the external nodes is known as
external path length. Ex: level (F) =2, level (H) =3, level (K) =3, therefore external
path length is= 2+3+3=8
CHARECTERIZATION
• BINARY TREE:: A binary tree T is a finite set of nodes that is
i. Either empty or
ii. Contains a specially designated node called the root and partitioned
into two disjoint sets T1 and T2 where both of them are binary trees.
T1 and T2 are known as the left and the right sub-trees respectively.



Binary trees
A
A A
A
A
A
A
A A
A
A
A
A A

16. PROPERTIES:
1. The maximum number of nodes possible at level i is 2
i
where i>=0
Proof- This can be proved by induction on i. the root node is the only node at
level 0. So the maximum number of node at level i=0 is 1 that is 2
0
. So the
property is true for i=0. Now let the property is true for level k, thus the
maximum number of nodes at level k is 2
k
where k>=0. Each node in the binary
tree can have at most 2 children, so the maximum number of children in the
next level k+1 will be twice the number of nodes at level k that is 2* 2
k
= 2
k+1
.
So this property is true for any k then it will be true for k+1. Hence proved.
2. The maximum number of nodes possible in a binary tree of height h is
2
h
-1
Proof- The maximum number of nodes in a binary tree can be expressed as the
sum of the maximum number of nodes possible at each level. The maximum
level of a tree (depth) is h-1, since starting from level 0 and the maximum
number of nodes at any level i is 2
i
. So the total number of nodes possible in a
binary tree of height h is,
N=∑i=0
h-1
2
i

= 2
0
+2
1
+2
2
+……+2
h-1
(Geometric progression)
=1+2+4+8………
=2
(h-1)+1
-1/2-1
=2
h
-1
3. The minimum number of nodes possible of height h is equal to h.
Proof – A tree will have minimum number of nodes if each level has minimum
nodes. The minimum number of nodes possible at any level is 1, and there are

17. total h levels, thus the minimum number of nodes possible in a binary tree of
height h is equal to h.
4. A binary tree having n nodes then the minimum height of the tree is
log2 (n+1).
Proof- If each node has exactly two children then the maximum value of
number of nodes (n) will be 2
h
-1.
N<=2
h
-1
Or, n+1<=2
h
or, log2 (n+1) <=h or, h>=log2 (n+1) (proved)
5. For any non empty binary tree if n0 is the number of nodes with no child
and n2 is the number of nodes with two child then n0=n2+1.
Proof- Consider that the relationship holds for n=m. for n=m, Tnull=m+1. Now
for n=m+1, increment of one node means increment of two null nodes and
decrement of null node. So the resultant increment of null nodes is 1. So for
n=m+1, Tnull= (m+1)+2-1=(m+1)+1. Thus for any non empty binary tree n0=n2+1.
6. The total number of binary tree possible with n nodes is 1/n+1*
2n
cn
• COMPLETE BINARY TREE:: A binary tree T is said to be a complete binary
tree if all the levels of the tree have exactly maximum number of nodes
possible at that level. OR
A binary tree T is said to be complete binary tree if all the leaf nodes are at
the same level d, where d is the depth of the tree.

CBT CBT NCBT



A
B C
G
C
D
D E F
B
F E
A
C B
A
D E

18. ALMOST COMPLETE BINARY TREE:: A binary tree of depth d is said to be a
almost complete binary tree if it satisfies the following two conditions-
i. Any node n at level less than d-1 must gave two children, where d is
the depth of the tree.
ii. For any node n, having right descendent at level d, must have a left
son, and every left son is either a leaf at level d or must have two
children.




NACBT NACBT
The 1
st
tree in the above figure violating the rule (i), since depth=3, so
according to rule (i) all the nodes up to level 1 must have two children. But the
node C at level 1 is a leaf node.
The 2
nd
tree in the above figure, satisfying the rule (i), since all the nodes up to
level 1 have two children. But violating the rule (ii), since the node A having a
right descendent (J, K) at level d, but possessing a left son at level 2(E), which is
leaf.




ACBT
A
C B
D
F G
E
A
B C
D E F
K
G
I H J
B
A
C
D
E F G
H I

19. The above figure satisfies both rule (i) and rule (ii). Thus it is an almost complete
binary tree.
• STRICTLY BINARY TREE:: A binary tree T is said to be a strictly binary tree or
2-tree if the nodes are either a leaf or having exactly two children.




SBT NSBT NSBT SBT
PROPERTIES:
1) A strictly binary tree with n non leaf nodes has n+1 leaf nodes.
Proof- We can prove this property by induction on the number of non leaf nodes.
If a binary tree only have root node, then it has no non leaf node but have one
leaf node. So it is true for n=0. We will take a strictly binary tree with k non leaf
nodes (k>0) and assume that this property is true for both the left and right sub
trees. Suppose the left sub tree has m no of non leaf nodes, so the right sub tree
will have k-m-1 no of non leaf nodes. Since the property is true for both sub trees,
left sub tree will have m+1 no of leaf nodes and the right sub tree will have k-m-
1+1 no of leaf nodes. So the total no of leaf node are m+1+k-m-1+1=k+1 no of
nodes. Hence the property is true.
2) A strictly binary tree with n leaf nodes has total 2n-1 nodes.
Proof- We know that the strictly binary tree with n no of non leaf nodes will have
n+1 no of leaf nodes. Thus the total no of nodes are n+n-1=2n-1.
3) If E is the external path length and I is the internal path length and n is the
total number of internal node, then E=I+2n.
A
A A
A
A A
A
A
A
A
A
A
A A
A A

20. Proof- If a tree contains only its root and no other vertices then E=I=N=0 and it is
trivial. Now let us consider a non leaf vertex v but for which both of the children
are leaves. Let k be the length of the path from the root to the vertex.
Now if we delete the children of v from the 2-tree, then the number of non leaf
node goes down from N to N-1, the internal path length will reduced by the
distance to v that is I=I-k, and the distance to the child of the vertex k is k+1, so
the external path length will be reduced to E=E-2(k+1). But now the vertex v also
a leaf, so the distance of v should be added to the external path length. So the
actual external path length will be, E=E-2(k+1) + k=E-K-2. If the retains the
property, then
E-K-2= (I-K) +2(N-1)
Or, E-K-2=I-k+2N-2
Or, E=I+2N (Proved)
• BINARY SEARCH TREE:: A binary search tree is an import data-structure,
when a two way decision must be made at each point of data insertion,
searching and deletion in a tree. It is-
i. Either empty or
ii. Consist of root, right and left sub-tree where all the keys in the left
sub tree are less than the key of the root and all the keys in the right
sub tree are greater than the key of the root, and the left and right
sub tree both are also binary search tree.





Binary Search Trees
5
2 8
B
A C
5
6
7
C
A
B

21. INSERTION INTO BINARY SEARCH TREE:
Ex1: 4 2 6 1 3 5 7
i.

ii.


iii.

iv.


v.



vi. vii.




4
4
2
4
6 2
4
2 6
1
4
2 6
1 3
5
2
1 3
6
4 4
2
6
1 5 3 7

22. Ex2: M B T G P E S
i.

ii.

iii.

iv.


v.



vi. vii.





M
M
B
T B
M
M
T
P
T
G
B
B
G
M
E
P
M
T
G
B T
S
G P
E
M
B

23. • BINARY TREE TRAVERSING:
Traversing in binary tree means visiting each node of the tree exactly once.
Traversing of trees gives the linear order of the nodes. The task of
traversing the tree consists of visiting the root, left and right sub trees.
Among the 3! =6 ways, we generally follow 3 of it. Depending on the
position of the root, a binary tree traversing can be classified into following
three forms-
➢ INORDER- left->root->right
➢ PREORDER-root->left->right
➢ POSTORDER-left->right->root
Ex1:




INORDER—DBEAFCG PREORDER—ABDECFG POSTORDER-- DEBFGCA
Ex2:






A
C B
D E

F G
C B
H
F
A
E D
K
G
L I J

24. INORDER—DIGJBAECKHLF PREORDER—ABDGIJCEFHKL POSTORDER—
IJGDBEKLHFCA

Ex3:







INORDER—BFDLJMGAHENKPIC PREORDER—ABDFGJLMCEHIKNP
POSTORDER—FLMJGDBHNPKIECA
In case of preorder traversing of the tree the roots are lies from the left to the
right and in case of postorder traversing the roots are lies from the right to the
left.
• CREATION OF BINARY TREE FROM INORDER AND PREORDER TRAVERSALS
PREORDER: ABDHECFIGJK INORDER: DHBEAIFCJGK
i) The root of the tree is the 1
st
element of the preorder. Here it is A. Now
from inorder expression the elements on the left and on the right are
the left and right sub trees of the root respectively.


A
B C
D
F G
J
L M
E
H I
K
N P
A
DHBE IFCJGK

25. ii) Now we will move from the left to the right of the preorder expression
to get the next root. Here it is B. The elements D and H are on the left
and the element E is on the right of B in the inorder expression. Thus we
can conclude,




iii) Next root in the preorder is D. The only element on the right side
between D and the previous root B is H, and no elements on the left
hand side of D. Thus,






iv) The next two roots after D in the expression are H and E that are already
being accessed. The root after E in the expression is C. the left elements
of C are I and F and the right elements are J, G and K. Thus,





IFCJGK B
A
E DH
D E
H
B
A
IFCJGK
E
H
JGK
A
C
D
IF
B

26. v) The next root F, having a single element I on the left and no right
element. Thus,







vi) The next root after F is I, and is already being accessed. The next root
after I is G, having left element J, and right element K in the inorder
expression. Thus,







CREATION OF BINARY TREE FROM INORDER AND POSTORDER TRAVERSAL
POSTORDER: HIDJEBKFGCA INORDER: HDIBEJAKFCG
i) The root of the tree is the last element of the postorder expression.
Here it is A. all the elements on the right and left side of A are the right
and the left sub trees respectively.

JGK F
H
E D
C
B
A
I
E
B
A
D
H
C
F
I
G
K J

27. ii) The next root is the 2
nd
last element, here it is C. the right and the left
elements in the expression are G and K, F.





iii) The next root is G and already is being accessed. The root after G is F
and has only one left child K.






iv) The next root K is already accessed. The root after K is B, having two left
child E, J and three right children H, D, I in the inorder expression.




A
HDIBEJ KFCG
A
HDIBEJ C
G KF
A
K
F
G
C HDIBEJ
C
G
HDI
B
A
F
K
EJ

28. v) The next root E having only one right child J.






vi) The next root J is already accessed. The root after J is D and having one
left child H and one right child I.






• EXPRESSION TREES:
Any algebraic expression can be represented by a binary tree, in which the
leaf nodes are the operands, and the non leaf nodes are unary or binary
operators. The left child represents the left operands and the right child
represents the right operands. Although the parentheses do not appear in
the tree, but the tree retains the purpose of parenthesis.
Ex: (A*B) + (C/D)


A
B C
F
K
G HDI E
J
A
B C
F G
K
D E
J H I
+
* /
A B C D

29. TRAVERSING IN EXPRESSION TREES
EXPRESSION—(A-B*C) / (D+E/F)




INORDER—A - B * C / D + E / F PREORDER-- / - A * B C + D / E F
POSTORDER—A B C * - D E F / + /
The inorder, preorder and postorder traversing gives the corresponding infix,
prefix and the postfix expression of an algebraic expression. The inorder
traversing gives the actual order which the expression should be evaluated or the
operations to be performed.
TREE REPRESENTATION OF THE FOLLOWING PREFIX EXPRESSION
i) *A+*B-CDE ii) *A+B*C-DE









/
-- +
A *
B C
D /
F E
*
B
A
+
*
B
--
A
E
*
C
*
C
+
E
--
D
D

30. TREE REPRESENTATION OF THE FOLLOWING POSTFIX EXPRESSION
i) A C D * + ii) C D * A B / +




• ARRAY REPRESENTATION OF BINARY TREE
A binary tree can be represented by using a one dimensional array. Let us
consider the following binary tree. 0

1 2

3 4 5

6 7 8
To represent the above binary tree in an array we store the contents of the
each node in an array named data.
0 1 2 3 4 5 6 7 8
data [ ] =

Now to define the parent child relationship we have to maintain two other arrays,
say left and right, such that left [0] holds the index of the left child of data [0] and
right [0] holds the index of the right child of data [0]. So the right array is,
0 1 2 3 4 5 6 7 8
right [ ] =

And the left array is, 0 1 2 3 4 5 6 7 8

left [ ] =
+
A *
B A C D
/ *
+
D C
A
I
E
B
D
C
F
H G
A B C D E F G H I
2 4 -1 6 -1 8 -1 -1 -1
1 3 5 -1 7 -1 -1 -1 -1

31. We have used the value -1 to represent an empty sub tree. The above
representation requires 3*n spaces to represent a binary tree having n number of
nodes. However we can represent the above tree using a single array. To
represent a binary tree using a single one dimensional array, the nodes of the tree
need to be numbered sequentially, level by level, starting with 0. All the nodes are
should be numbered from the left to the right of a level, including the empty
nodes. 0

1 2

3 4 5 6

7 8 9 10 11 12

Now, it can be noted that, if the n umber appearing for any node is n is I, then the
left and the right child of node n has the number 2*i+1 and 2*i+2 respectively. We
can simulate the above tree in an array,
0 1 2 3 4 5 6 7 8 9 10 11 12

tree[ ] =

The size of the array will be minimum, if the height h is minimum, and it will be
maximum if the height h is maximum. The height is minimum for a complete
binary tree, which is log2 (n+1), and total number of nodes are 2
log(n+1)
-1.

• LINKED LIST REPRESENTATION OF BINARY TREE
The linked representation overcomes the problems encountered in an array
representation. Unlike the implicit representation in an array, in this
representation the pointers are used explicitly to link the nodes of the tree. In
linked representation we take three members of a node. First member is the left
pointer of node type to store the address of the left sub tree, the second member
A
B C
D E F
H G I
A B C D E F -1 -1 G H -1 -1 I

32. is the data or the information and third member is the right pointer of node type
to store the address of the right sub tree.
struct node{ struct node* left; int info;struct node * right;};
This is a self-referential structure (A structure having members of the same type
as the structure). If any of the children is empty, then the corresponding pointers
will be set to NULL (A macro having value 0).
To store the address of the first node or the root node of the tree, we use a
pointer root of node type. If the content of root pointer is NULL, then we can
conclude that the tree is empty.










C IMPLEMEMTATIONS OF DIFFERENT OPERATIONS
// RECURSIVE FUNCTION FOR INORDER TRAVERSING IN BINARY TREE
void inorder(struct node *root)
{
while (root!=NULL)
{
inorder (root->left);
printf(“%d”,root->info);
50 2 100
150 4 200
NULL 8 NULL NULL 5 NULL NULL 3 NULL
250 6 300
NULL 1 NULL

33. inorder( root->right);
}
}

// RECURSIVE FUNCTION FOR PREORDER TRAVERSING
void preorder (struct node *root)
{
while ( root!=NULL)
{
printf(“%d”,root->info);
preorder(root->left);
preorder(root->right);
}
}
// RECURSIVE FUNCTION FOR THE POSTORDER TRAVERSING
void postorder(struct node*root)
{
while(root!=NULL)
{
postorder (root->left);
postorder (root->right);
printf(“%d”,root->info);
}
}
// NON RECURSIVE INORDER TRAVERSING
void inorder( struct node * * rt)
{
struct node *p;
if(*rt==NULL)
{
printf(“\n tree is empty”);return;

34. }
p=*rt;
while(1)
{
while(p->left!=NULL)
{
push(&s,p); p=p->left;
}
while( p->right==NULL)
{
printf(“%d”,p->info);
if(s.top==-1)
return;
p=pop(&s);
}
printf(“%d”,p->info);
p=p->right;
}
// NON RECURSISVE PREORDER TRAVERSING
void preorder(struct node * *rt)
{
struct node * p;
if(*rt==NULL)
{
printf(“\n tree is empty”); return;
}
p=*rt;
while( 1)
{
while(p!=NULL)
{

35. printf(“%d”,p->info);
if(p->right!=NULL)
push(&s,p->right);
p=p->left;
}
if(s.top==-1)
return;
p=pop(&s);
}
}


// NON RECURSIVE POSTORDER TRAVERSING
void postorder( struct node * * rt)
{
struct node *p, *q;
if(*rt==NULL)
{
printf(“\n tree is empty”);return;
}
p=*rt; q=NULL;
while(1)
{
while(p->left!=NULL)
{
push(&s,p); p=p->left;
}
while((p->right==NULL)||(p->right==q))
{
printf(“%d”,p->info); q=p;
if(s.top==-1)

36. return;
p=pop(&s);
}
push(&s,p); p=p->right;
}
// RECURSIVE FUNCTION FOR IN SERTION INTO BINARY SEARCH TREE
void insert( struct node **rt, int val)
{
struct node * p;
p=(struct node*) malloc(sizeof(struct node));
if(p==NULL)
{
printf(“\n no space in memory”); return;
}
p->info=val;p->right=NULL;p->left=NULL;
if(*rt==NULL)
*rt=p;
else if( val>(*rt)->info)
insert((&(*rt)->right),val);
else if(val<(*rt)->info)
insert((&(*rt)->left),val);
}
// NON RECURSIVE FUNCTION FOR INSERTION INTO BINARY SEARCH TREE

void insert(struct node* rt, int val)
{
struct node * p,* current,*parent;
p=(struct node*) malloc(sizeof(struct node));
if(p==NULL)
{
printf(“\n no space in memory”); return;

37. }
current=*rt; parent=NULL;
while(current!=NULL)
{
parent=current;
if(val>current->info)
current=current->right;
else if(val>current->info)
current=current->left;
else
{
printf(“\n duplicate key”);return;
}
}
p->info=val;p->right=NULL;p->left=NULL;
if(parent==NULL)
*rt=p;
else if(val->parent->info)
parent->right=p;
else if(val<parent->info)
parent->left=p;
}
// NON RECURSIVE SEARCHING IN BINARY SEARCH TREE
struct node * search( struct node**rt,int target)
{
struct node * p;
if(*rt==NULL)
{
printf(“\n tree is empty”);return;
}
p=*rt;

38. while(p!=NULL)
{
if(p->info==target)
break;
else if(target>p->info)
p=p->right;
else if(target<p->info)
p=p->left;
}
return p;
}

// RECURSIVE SEARCHING IN BINARY SEARCH TREE

struct node * search( struct node**rt,int target)
{
struct node * p;
if(*rt==NULL)
{
printf(“\n tree is empty”);return;
}
if( target==(*rt)->info)
return (*rt);
else if(target>(*rt)->info)
return (((&(*rt)->right),target);
else if (target<(*rt)->info)
return ((&(*rt)->left),target);
}
// NON RECURSIVE DELETION IN BINARY SEARCH TREE
void fresh(struct node **rt, int target)
{

39. struct node * current,* parent,*temp;
if(*rt==NULL)
{
printf(“\n tree is empty”);return;
}
current=* rt; parent=NULL;
while(current!=NULL)
{
if (current->info==target)
break;
parent=current;
if(target>current->info)
current=current->right;
else if(target>current->info)
current=current->left;
}
if(current==NULL)
{
printf(“\n target not found”);return;
}
if(current->right!=NULL&&current->left!=NULL)
{
temp=current; current=current->right;
while(current->left!=NULL)
{
parent=current; current=current->left;
}
temp->info=current->info;parent->left=NULL; free(current);
return;
}
if(current==*rt)

40. {
if(current->right!=NULL&&current->left==NULL)
{
*rt=current->right; free(current);
}
else if(current->right==NULL&&current->left!=NULL)
{
*rt=current->left; free(current);
}
else if(current->right==NULL&&current->left==NULL)
free(current);
return;
}
else {
if(current->right!=NULL&&current->left==NULL)
{
if(parent->right==current)
parent->right=current->right;
else
parent->left=current->right;
}
if(current->right==NULL&&current->left!=NULL)
{
if(parent->right==current)
parent->right=current->left;
else
parent->left=current->left;

}
if(current->right==NULL&&current->left==NULL)
{

41. if(parent->right==current)
parent->right=current->NULL;
else
parent->left=current->NULL;

}
return;
}
}

42. TREE EXTENDED

INTRODUCTION: The first balanced binary search tree was the AVL tree (named after its discoveries,
Adelson Velskii and Landis). The AVL tree is a binary search tree that as an additional balance condition
must be easy to maintain and ensures that the depth of the tree is O (log N). The simplest idea is to
require that the left and right sub-trees have the same height. Recursion dictates that this idea applies
to all nodes in the tree, since each node is itself a root of some sub-tree. This balance condition ensures
that the depth of the tree is logarithmic, but it is too restrictive because it is too difficult to insert new
items while maintaining balance. Thus the AVL trees use a notion of balance that is somewhat weaker
but still strong enough to guarantee logarithmic depth.
12
8 16
4 10 14
2 6
1


EXMPLE: Insert the following keys in order shown to construct an AVI, tree
10, 20, 30, 40, 50
Delete the last two keys in the order of LIFO
: Insert 10, 20




Insert 30 RR-rotation





10
20
10
10
10
10
10
10

43. TREE EXTENDED

Insert 40




Insert 50
RR-rotation





Advantages of an AVL tree :
Since AVL trees are height balanced trees , operations like insertion and deletion have less time
complexity.
Let us consider an example . If we have the following trees with keys 10,20,30,40,50,60,70, then a
binary tree would look like this.
10 40
20
30 20 60
40
50 10 30 50 70
60
(a) BST 70 (b) AVL TREE



10
10 10
10
10
10
10
10
10
10
10 10
10
10

44. TREE EXTENDED


In order to insert a node with a key ‘k’ in the binary tree (a) , the algorithm requires 7 comparisons , but
if we insert the same key in AVL tree(b) ,the algorithm will just require 3 comparisons , which is less than
half of the binary search tree.
Thus ,AVL search trees will increase the efficiency of the programs.

INSERTION IN B-TREE :
the insertion of a key in a B-tree requires first traversal in B-tree. Through traversal it will find that key
to be inserted is already existing or not. Suppose key does not exist in tree then through traversal it will
reach leaf node. Now we have two cases for inserting the key.
1. Node is not full.
2. Node is already full.
If the leaf node in which the key is to be inserted is not full, then the insertion is done in the node. A
node is said to be full if it contains a maximum of ( m-1 ) keys, given the order of the B-tree to be m.
If the node werw to be full, then insert the key in order into the existing set of keys in the node, split
the node at its median into two nodes at the same level, pushing the median up by one
level. Note that the split nodes are only half full. Accommodate the median element in the parent
node if it is not full. Otherwise repeat the same procedure and this may even call for rearrangement
of the keys in the root node or the formation of a roof itself.
Thus a major observation pertaining to insertion in a B-tree is tht, since the leaf nodes are all at the
same level, unlike m-wy search trees, the tree grows upwards.
EXAMPLE . Let us take a list of keys and create a B-tree of order 5.
10, 20, 50, 60, 40, 80, 100, 70, 130, 90, 30, 120, 140, 25, 35, 160, 180
Solution :
1. Insert 10 10
2. Insert 20 10 20
3. Insert 50 10 20 50
4. Insert 60 10 20 50 60

45. TREE EXTENDED


40
5. Insert 40
10 20 50 60
Here node was already full , so after insertion of 40 , it is splitted into two nodes , 40 is the median
key so it will go into parent node and it will become root.
Insert 80 40
10 20 50 60 80
Insert 100 40
10 20 50 60 80 100

Insert 70




Here node was already full, so after insertion of 70 it splitted into two nodes, 70 is the median key, so it
will go to the parent node.
Insert 130




Insert 90



40 70
10 20 50 60 80 100
40 70
10 20 50 60 80 100 130
40 70
10 20
50 60 80 90 100 130

46. TREE EXTENDED


Here after insertion of 90, the keys in node will be sorted.
Insert 30



Insert 120




Here node was already full, so after insertion of 120 it splitted in two nodes, 100 is the median
key so it will go into parent.
Insert 140




DELETION IN B-TREE:
Deletion of key also requires first traversal in B-tree , After reaching on particular node , two cases may
occur :
1. Node is leaf node.
2. Node is non-leaf node




40 70
10 20 30 50 60 80 90 100 130
10 20 30
40 70 100
50 60 80 90 120 130
40 70 100
10 20 30 120 130 140 50 60
30
80 90
30

47. TREE EXTENDED


Delete 60.






Here 60 is in no leaf node. So first it will be deleted from the node and then the element of the right
child will come in that node.
Delete 40.








Here first 40 will be deleted from leaf node then left side element in the parent node will come in leaf
node and then last element of the left side node of the parent node will come in parent node.





105
30 70 135 185
5 15

20 40

50

80

90

110

120

140

160

200


250



105
70 20 135 185
5 15

30 50

80

90

110

120

140

160

200


250

48. TREE EXTENDED


Delete 140.







But at least two elements should be in child node so it will go in root node.





EXAMPLE : Suppose a B-tree of order-5 is shown in the Fig.









105
20 70 185

5 15

30 50

80

90

110

120

135 160

200


250



20 70 105 185

5 15

30 50

80

90

110

120

135 160

200


250



10
3

6 13

18

1

2

4

5

7

8

9

11

12

14

16

19

20

21

24

49. TREE EXTENDED


Delete 8.







Deletion of 8 is from a leaf node with more than the minimum number of elements and hence leaves no
problem.
Delete-18.





Deletion of 18 is from non-leaf node and therefore the immediate successor is placed at 18, i.e.. 19.
Delete-16.







2

10
3

6 13

18

1

4

5

7

9

11

12

14

16

19

20

21

24

10
3

6 13

19

1

2

4

5

7

9

11

12

14

16

20

21

24

10
3

6

13

20

1

2

4

5

7

9

11

12

14

19

21

24

50. TREE EXTENDED


Deletion of 16 leaves its nodes with too few elements. The element 19 from parent node is therefore
brought down and replaced by the element 20.
Delete- 4
The deletion of 4 leaves the node with less than minimum number of elements and neither of its sibling
nodes can spare an element. The node therefore is combined with one of the siblings and with the
median element from the parent node.






But at least two elements should be in the child of root so it will go in root node.




It reduces the height of tree also.
APPLICATION OF A B-TREE
The main application of a B-tree is the organization of a huge collection of records into a file structure.
The organization should be in such a way that any record in it can be searched very efficiently I.e.,
insertion, deletion and modification operations can be carried out perfectly and efficiently




10
6

13

20

1

2

3

5

7

9

11

12

14

19

21

24

6 10 13 20
1

2

3

5

7

9

11

12

14

19

21

24

51. TREE EXTENDED

B
+
-TREES
The B-tree structure is the standard organization for indexes in a database system. There are several
variations of the B-tree, most well known being the B*-tree and the B+ - tree. The B -tree guarantees at
least 50% storage utilization, that is, at any given time, the tree has each of its nodes at least 50% full.
The B+ -tree is a slightly different data structure, which in addition to indexed access, also allows
sequential data processing and stores all data in the lowest level of the tree.
One of the major drawbacks of the B-tree is the difficulty of traversing the keys sequentially.
B+ tree retains the rapid random access property of the B-tree, while also allowing rapid sequential
access. In the B+ tree, all keys are maintained in leaves and keys are replicated in non-leaf nodes to
define paths for locating individual records. The leaves are linked together to provide a sequential path
for traversing the keys in the tree.
The b+ -Tree is called a balanced tree because every path from the root node to a leaf node is
the same length. A balanced tree means that all searches for individual values require the same number
of nodes to be read from the disk.

B+ tree
• Is a structure of nodes linked by pointers
• Is anchored by a special node called the root and bounded by leaves
• Has a unique path to each leaf, and all paths are equal length
• Stores keys only at leaves, and stores reference value in other, internal nodes
• Guides key search, via the reference values, from the root to the leaves
A B + tree of order M (M>3) is an M-ary tree with the following properties:
1. The data items are stored at leaves.
2. The root is either a leaf or has between two and M children.
3. Node :
• The (internal) node (non-leaf) stores up to M – 1 keys (redundant) to guide the
searching; keyi represents the smallest key in subtree i + 1.
• All nodes (except the root) have between M\2 and M children
4. Leaf :
• A leaf has between L\2 and L data items, for some L(usually L << M, but we will
assume M = L in most example).
• All leaves are at the same depth.
5. Less disk access due to fewer levels in the tree.
6. B*tree provides faster sequential access of data.

52. TREE EXTENDED







Index set




Sequence set



As we can see in the figure, the leaves have been connected to from a linked list of keys is sequential
order. The B
+
tree has two parts the first part is the index setthat constitutes interior nodes and the
second part is theSequence set that constitutes leaves.
B
+
-Tree Structure
B
+
-tree consists of two parts :
Index Set
• Provides indexes for fast access of data.
• Consist of internal nodes that store only key & sub tree pointers.
Sequence set
• Consists of leaf nodes that contain data pointers.
• Provides efficient sequential access of data (using doubly linked list).

98
36 53 81 10
4
36
8 17
36 42 53 56 65 72 81 83 96 98 102 104 107 112 119 125 127

53. TREE EXTENDED






Sequential search Sequence set


B
+
-Tree: Index Node Structure
The basic structure of the B
+
-tree index node of order m is same as that of B-tree node of order m.
The root has at least two sub-trees unless it is a leaf.
Each non-root index node holds q – 1 keys and q subtree pointers, where m\2 < q<m
Only difference is that index node does not contain data pointers.







B
4
- Tree : Sequence Node Structure
The structure of the B+ - tree sequence node is as follows :
K1 D1 KI-1 DI-1 KI DI KQ-1 DQ-1




Index set
P1 K1 P2 Ki-1 Pi Ki Kq-1 Pq

54. TREE EXTENDED

.If an internal node is reached :
.Search KEY among the keys in that node
.Linear search or binary search
.If KEY ≤ smallest key , follow the leftmost child pointer down
.If KEY > largest key , follow the rightmost child pointer down
.If Ki ≤ KEY < Kj ,follow the child pointer between Ki and Kj
.If a leaf is reached :
.Search KEY among the keys stored in that leaf
.Linear search or binary search
.If found , return the corresponding record ; otherwise report not found.

INSERTION INTO A B
+
TREE
In order to insert a key into a B
+
tree ,first a B
+
tree search is performed to find the correct location for
the key . Actually , the procedure to insert a new key value into a B
+
- Tree is almost as for B- Tree .
The sequence of steps required to insert a node in a B+ Tree are as follows :
1. The search operation is used to find the leaf node in which the key value of the node has to be
inserted.
2. If the key value already exist in a leaf node , no more insertion is needed . Else if the said key value
does not exist , insert the value in the leaf node in an ordered fashion.
3. When a node is split , the middle key is retained in the left half-node as well as being promoted to
the father.

DELETION FROM A B+ TREE
The sequence of steps required to delete a key value from the B+ Tree is as follows :
1. Search the B+ Tree for the key value.
2. If the key value is in the B+ Tree , remove it from the tree as that of B Tree .

55. TREE EXTENDED

3. When a key value is deleted from a leaf there is no need to delete that key from the index set of
the key. That key value still can direct searches to proper leaves , since it still a valid separator between
the keys in the nodes below .



COMPARISON BETWEEN B- TREE AND B+ TREE
B- TREE B+ TREE
1. Data pointers are stored in all nodes. 1. Data pointers are stored only in leaf nodes .
2. Search can end at any node. 2. Search always ends at leaf node.
3. No redundant keys. 3. Redundant keys may exist.
4. Slow sequential access. 4. Efficient sequential access.
5. Higher trees. 5. Flatter TREES. No data pointers in index set node.

56. GRAPH THEORY
Q1. WHAT IS GRAPH? WHAT ARE THE DIFFERENT MEMORY REPRESENTATIONS OF IT?
A graph G (V, E) is a pair of sets V and E, where V is the finite set of vertices or nodes or points together
with a set of unordered pairs of these vertices for an undirected graph and ordered pairs for a directed
graph and E is the finite set of edges.
The different memory representations of a graph are-
Adjacency Matrix Representation:
A square matrix n*n, where n is the number of vertices that is used to represent the adjacency
relation of the vertices in a graph is known as adjacency matrix representation. In case of directed
graph, A[i,j]= 1 if there is an edge from vertex i to j, otherwise 0 and in case of undirected graph
A[i,j]=1 if there exist an edge between i to j.

Ex1:



Ex2:




Incident Matrix Representation:
A square matrix n*m, where n is the number of vertices and m is the number of edges that is used to
represent the direction or incidence to from relation of the edges in a graph is known as incidence
matrix representation.
A[i,j]=1 if there is an outgoing edge j from vertex i, and A[i,j]=-1 if if there is an incoming edge j to
vertex i.

57. Ex:


Adjacency List Representation:
A linked list representation of the list of adjacent vertices of a vertex is known as the Adjacency List
Representation.

Ex:


Q2. WHAT IS SPANNING TREE OF A GRAPH? WHAT DOU YOU MEAN BY MINIMUM SPANNING TREE?
A spanning tree of a graph G (V,E) is a sub-graph of G let G1(V1,E1), which has all the set of vertices
covered with minimum number of possible edges. Hence a spanning tree does not have any cycle and
cannot be disconnected.
A spanning tree (as there could be more than one spanning trees) is said to be the minimum spanning tree of
a graph, if it is having the minimum possible total edge weight among the other spanning trees.

58. Q3. EXPLAIN THE KRUSKALS ALGORITHM TO FIND THE MINIMUM SPANNING TREE OF A GRAPH.
Kruskal's algorithm:

Step1: sort the edges of G in increasing order by weight
Step2: keep a subgraph S of G, initially empty
Step3: for each edge e in sorted order until n-1 no. of edges are encountered
if the endpoints of e are disconnected in S
add e to S
Step4: return S

Example:




Time complexity: O(E logV)

59. Q4. EXPLAIN THE PRIMS ALGORITHM TO FIND THE MINIMUM SPANNING TREE OF A GRAPH.
Prims Algorithm:
Step1: Construct a matrix of order n*n where n is the no. of vertices and assign the weight of the edges in
the respective cells.
Step2: keep a subgraph S of G, initially empty
Step3: for each edge e in the matrix until n-1 no. of edges are encountered

Step4: Select the next minimum cost edge from the rows of the already selected vertices
if the endpoints of e are disconnected in S
then add it to S.
Step4: Return S.
Example:


Time Complexity: O((V+E)log V)

60. Q5. WHAT IS GRAPH TRAVERSAL? DEFINE THE DIFFERENT GRAPH TRAVERSAL TECHNIQUES.
Graph traversal means visiting of every vertex and edges of a graph exactly once in a well defined order.
The order in which the vertices are visited is important and may depend upon the algorithm being used.
The general ways of traversing a graph are-
Breadth First Search:
In BFS we start traversing from a selected node and traverse the graph layer-wise or breadth-wise
thus exploring the neighboring nodes.
Mechanism:

BFS Algorithm:
Step1: Set the status of all the nodes to 1.
Step 2: Insert the source node in the rear of the queue and change the status to 2.
Step3: Repeat step 4 to 5 until the queue is empty
Step4: Retrieve the node from the front of the queue and change its status to 3
Step 5: Insert all the neighbors having status 1 into the rear of the queue and change their status
to 2.

Example:

61. S1: Adjacency list
S: 1,2 1: 3,4,5 2:6 6:7
S2: Queue status & Output

S 1 2 3 4 5 6 7

BFS O/P: s,1, 2,3,4,5,6,7

Depth First Search:
In DFS we start traversing from a selected node and traverse the graph depth-wise or height-wise
thus exploring all the children nodes of the source node.

Mechanism:

Algorithm:
Step1: Set the status of all the nodes to 1.
Step 2: Insert the source node in the top of the stack and change the status to 2.
Step3: Repeat step 4 to 5 until the stack is empty
Step4: Retrieve the node from the top of the stack and change its status to 3
Step 5: Insert all the neighbors having status 1 into the top of the stack and change their status to
2.

Example:

62. S1: Adjacency list
S: 1, 2 1: 3, 4, 5 2:6 6:7
S2: Queue status & Output

S 1 2 6 7 3 4 5

DFS O/P: s, 2, 6, 7, 1, 3, 4, 5

Q6. EXPLAIN THE DIJKSTRAS ALGORITHM TO FIND THE SHORTEST PATH FROM THE SOURCE TO
DESTINATION.
Algorithm:
Step1: Initialize the cost of the source vertex by 0 and every other vertex to infinity.
Step2: Initialize the S, n*2 matrix by 0.
Step3: Repeat Step 3 to
Step4: Select the next min cost vertex.
Step5:
Update the cost of each vertex by min {previous cost, cost of selected vertex + cost from selected vertex}
If updated, store the updated value and the parent vertex in S.
Step6: Determine the change values and their parent from S and put it in matrix P traversing backward from
the goal state to source vertex.
Step7: Return the matrix P.
Example:
3
4 6

2 6 8
9
1 12


Source Vertex: A
Destination Vertex: F

B D
C E
F A

63. VS A B C D E F

0 ∞ ∞ ∞ ∞ ∞
A
0 4A 1A ∞ ∞ ∞
C
0 3C 1A 7C 13C ∞
B
0 3C 1A 6B 13C ∞
D
0 3C 1A 6B 13C 12D

Therefore the Shortest Path:
F D B C A
12D 6B 3C 1A 0
A->C->B->D->F