Data Structures and Algorithms

1
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reference Books
• A. V. Aho, J. E. Hopcroft, J. D. Ullman, “Data Structures and
Algorithm”, Pearson.
• D. Samanta, “Classic Data Structure”, PHI.
• S. Lipscutz, “Data Structures with C”, TMH.
• R. Kruse, C.L. Tondo, B. Leung, S. Mogalla, “Data Structures and
Program Design in C”, Pearson.
• D. E. Knuth, “The Art of Computer Programming”, Addison-Wesley
• S. Chattopadhyay, D.G. Dastidar, M. Chattopadhyay, “Data
Structures through C Language”, BPB Publications.

2
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Introduction

3
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Algorithms
• A finite set of instructions executed in
sequence in finite time
• Algorithm for finding GCD
step 1: read two positive integers x and y
step 2: divide x by y to get remainder r and quotient q
step 3: if r is zero go to step 7
step 4: assign y to x
step 5: assign r to y
step 6: go to step 2
step 7: y is the required GCD, print y
step 8: stop

4
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Algorithms
• Properties of an algorithm
– Input
– Output
– Finiteness
• For all input data, the algorithm must terminate after a
finite number of steps
– Definiteness
– Clear and unambiguous steps
– Effectiveness
• Steps must be very basic

5
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Algorithms
• Expressing an algorithm
– Natural language, flowchart, programming languages
• Designing an algorithm
– Innovative exercise, no methodology to automatically generate
algorithms
– Use of new techniques and strategies for good algorithms
• Depends heavily on the organization of data
• Analyzing an algorithm
– Validation
– Complexity evaluation
• Both time and space

6
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Abstract Data Type
• Data type defines a set of values and
permitted operations
• Built-in data types are not enough for most
applications
– Create new data types in terms of structure
• Operations applicable to structure variables can not be
specified
– Concept of abstract data type (ADT) introduced
• A mathematical model with collection of operations
defined on that model

7
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Abstract Data Type
• Define a new data type “SET”
• Operations on ADT “SET”
– assign (SET A, SET B)
– SET union (SET A, SET B)
– SET Intersection (SET A, SET B)
– int cardinality (SET A)
• No limit on the number of operations
• Implementation aspect is not considered
8
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Data Structure
• A scheme to organize data
– Stack, queue, tree, graph etc.
• Affects the performance of a program for
different tasks
• Choice of data structure depends on:
– Nature of data
– Processes to be performed on the data

9
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms

10
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Used to compare number of algorithms and
choose the best one
• Typically, two quantitative metrics:
– Space complexity
• Run time storage requirement
– Time complexity
• Time required to complete execution
– Usually depends on input size, i.e., time complexity is a
function of input size

11
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Types of analysis
– Best Case
• Lower bound on cost
• Determined by “easiest” input
• Provides a goal for all inputs
– Worst Case
• Upper bound on cost
• Determined by most “difficult” input
• Provides a guarantee for all inputs
– Average Case
• Expected cost for random input
• Provides a way to predict performance

12
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Time complexity
– Very difficult to compute exact time
• Several factors influence execution time which are
outside the domain of programmers
– Programs are translated to machine code

– Define a function f(n) that gives an estimate of

volume of work done by the algorithm on input
size n

13
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Big-Oh notation
– T(n)=O( f(n) ) if T(n) ≤ c f(n) ie for sufficiently
for some constant, c > 0, and n ≥ n0 large n

f is an upper bound for T

– If T(0)=0, T(1)=4, and in general T(n)=(n+1)2, then

T(n)=O(n2)
• Let n0=1, c=4, i.e., "n ≥1, (n+1)2 ≤ 4n2
14
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Constant factors may be ignored
 " k > 0, kf is O( f)
• Higher powers grow faster
– nr is O( ns) if 0  r  s
Fastest growing term dominates a sum
e.g., 3n3 + 2n2 is O(n3 )
c + cn + cnlogn is O(nlogn)
Polynomial’s growth rate is determined by leading term
– If T is a polynomial of degree d,
then T is O(nd)

15
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• T is O(g) is transitive
– If T is O(g) and g is O(h) then T is O(h)
• Product of upper bounds is upper bound for the product
– If f is O(g) and h is O(r) then fh is O(gr)
• Two additional notations
 W( g(n) )
 T(n) ≥ c g(n) g(n) is a lower
for some constant, c, and n > n0 bound for T
 ( g(n) ), for some constants, c1,c2 and n > n0
 c2g(n) ≥ T(n) ≥ c1 g(n) Best and worst case complexities are
same
16
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Simple statement
S=p+q
– Time Complexity is O(1)
• Simple loops
for(i=0;i<n;i++) { s=p+q; }
– Time complexity is n O(1) or O(n)
• Nested loops
for(i=0;i<n;i++)
This part is
for(j=0;j<n;j++) { s=p+q; }
O(n)
– Time Complexity is n O(n) or O(n )
2

17
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Loop index doesn’t vary linearly
h = 1;
while ( h <= n ) {
s;
h = 2 * h;
}
– h takes values 1, 2, 4, … until it exceeds n
– There are 1 + log2n iterations
– Complexity O(log n)
18
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Loop index depends on outer loop index
for(j=0;j<n;j++)
for(k=0;k<j;k++){
s;
}
– Inner loop executed
• 1, 2, 3, …., n times
n(n+1)
S i =
i=1 2
 Complexity O(n2)
19
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Algorithms
• Common computing times are
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n)
• log n
• Logarithmic algorithm, cuts down the problem to smaller one
• n
• Linear algorithm
• n log n
• Breaks the large problem into sub-problems, solve sub-problems
independently, combine the results
• 2n
• Exponential running time, not suitable for practical use

20
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 The LIST ADT

21
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 LIST ADT
• Ordered sequence of data items called
elements
– A1, A2, A3, …,AN is a list of size N
• Size of an empty list is 0
• First element is A1 called “head”
• Last element is AN called “tail”

Operations ?

22
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 LIST ADT
• Operations
– PrintList
– Search
– FindKth
– Insert
– Delete
– Reverse
– Sorting
– MakeEmpty

23
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 LIST ADT
• Example:
the elements of a list are
34, 12, 52, 16, 12

– Search (52)  3
– Insert (20, 3)  34, 12, 20, 52, 16, 12
– Delete (52)  34, 12, 20, 16, 12
– FindKth (3)  20
24
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 LIST ADT
• You can see the difference between arrays and
lists when you delete items.

25
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of LIST
• Need to define a size for array
– High overestimate (waste of space)

• Operations Running Times

PrintList O(N)
Search

Insert O(N) (on avarage half needs to be moved)

Delete

FindKth
Next O(1)
Previous
26
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of LIST
int search (int a[], int n, int val) Best Case: O(1)
{ Average Case:
int i=0; number of comparisons
for (i=0; i<n;i++) could be 1,2,..,n depending
if (a[i] = = val) If a match is found come on the position of val.
break; out of the for loop =(1+2+…+n)/n
if (i = = n) =(n+1)/2
return -1; Val not found in a[ ] =O(n)
else Worst Case: O(n)
return i; Return the index of
val in a[ ]
}

27
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of LIST
iii ii i

5 2 1 6 9 4
Initial array; arrow shows
shifting of elements

5 2 1 6 6 9 4 Array after shifting

5 2 1 8 6 9 4 Array after inserting 8 at

position 3

void insert (int a [], int n, int j, int val)

{
int i;
for ( i = n-1; i >= j; i-- )
a[i+1] = a[i]; Shifting of elements to the right
a[j] = val;
}
28
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of LIST
i ii iii

5 2 1 8 6 9 4
Initial array; arrow shows
shifting of elements

5 2 1 6 9 4 Array after shifting

Void delete (int a [], int n, int j)

{
int i;
for ( i = j+1; i < n; i++ )
a[i-1] = a[i]; Shifting of elements to the left
}

29
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of LIST
1 2 3 4 5 6 7 8 9

Arrows indicate
required exchange
void reverse (int a [], int n)
{
int i, temp;
for ( i = 0; i < n/2 ; i++ )
{
temp = a [i];
a [i] = a [n-1-i];
a [n-1-i] = a [i];
}
}
30
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• Polynomial, P(x) of degree n is:
P(x) = a0 + a1x + a2x2 + …….. + anxn
• Treat Polynomials as ADT
– Operations
• Initialization
• Copy
• Add
• Multiply
• Evaluate

31
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• Representation:
typedef struct poly
{
float coeff [1000];
int degree;
} poly

• Polynomial 1 + 4x2 + 2x8 is stored as:

1 0 4 0 0 0 0 0 2

Wasteful representation, most of

the elements are Zero

32
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• Store only non-zero terms aixi
• Define the terms:
typedef struct term
{
float coeff;
int expo;
} term;
• Now, define the polynomial:
typedef struct poly
{
term a[ 1000];
int no_of_terms;
}poly;
33
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• Polynomial 1 + 4x2 + 2x8 is stored as:
1,0 4,2 2,8 ……

• Addition of polynomials 1 + 4x2 + 2x8 and 3x +

5x2 + 6x7

1,0 4,2 2,8 …… 3,1 5,2 6,7 ……

34
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• Addition of polynomials:
1,0 4,2 2,8 …… 3,1 5,2 6,7 ……

1,0

1,0 4,2 2,8 …… 3,1 5,2 6,7 ……

1,0 3,1

35
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• Addition of polynomials:
1,0 4,2 2,8 …… 3,1 5,2 6,7 ……

1,0 3,1 9,2

1,0 4,2 2,8 …… 3,1 5,2 6,7 ……

1,0 3,1 9,2 6,7

36
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• Addition of polynomials:
1,0 4,2 2,8 …… 3,1 5,2 6,7 ……

1,0 3,1 9,2 6,7 2,8

37
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
for ( i = 0, j = 0, k=0; ( i < P1no_of_terms) && ( j < P2no_of_terms); k++)
{
if (P1 a [i].expo == P2 a[j].expo)
{
P3a[k].coeff = P1a[i].coeff + P2a[j].coeff;
P3a[k].expo = P1a[i].expo;
For remaining terms in P1 and P2
i++; j++;
} if (i < P1no_of_terms)
else if (P1 a [i].expo < P2 a[j].expo) for (l = i; l < P1no_of_terms; l++, k++)
{ {
copy the term in P1 to P3; i++; copy the terms in P1 to P3;
} }
else else
{ for (l = j; l < P2no_of_terms; l++, k++)
copy the term in P2 to P3; j++; {
} copy the terms in P2 to P3;
} }
Complexity: O(m+n), m and n are degree of the polynomials P3no_of_terms = k;
38
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• Very large numbers can not be stored in
variables of type “int” or “long”!!!!
– 80 digit number is greater than the maximum
value in “long”

• A number can be represented as a polynomial

– e.g., 12345 = 1x104 + 2x103 + 3x102 + 4x101 + 5x100
– Equivalent to P(x) = x4 + 2x3 + 3x2 + 4x + 5, for x=10

39
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials using Arrays
• An integer of n digits is a polynomial of degree
n-1:
P(x)= S aixi for x=10, 0  ai  
i=0,n-1

• 2000020000000800009000000001 can be
represented as:

1,0 9,9 9,2 8 , 14 2 , 22 2 , 27

40
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sparse Matrix
• Most of the elements are zero in a matrix
0 0 1 0 


2 0 5 0 

0 0 0 3 
 
0 4 0 0

• Two dimensional array representation is

inefficient
• Solution:
– Store only non-zero elements
41
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sparse Matrix
• Treat a sparse matrix as a ordered LIST of non-
zero elements
• Information regarding each element:
– row, col, val
• Define the elements:
typedef struct element
{
int row, col, val;
} element;

42
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sparse Matrix
• Define the sparse matrix:
typedef struct sparsemat
{
int no_of_nonzero_elements;
int no_of_rows, no_of_cols;
element a [100];
}sparsemat;

• Example matrix can be represented as follows:

0, 2, 1 1, 0, 2 1, 2, 5 2, 3, 3 3, 1, 4

43
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sparse Matrix
• Saving in Space
– Space required to store m x n matrix of integers is
m x n x (size of an integer)
– Space required in ordered LIST
3 x p x (size of an integer), p is size of array
– LIST is advantageous if
3xp<mxn i.e., p < m x n/3

44
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sparse Matrix
• Finding number of non-zero elements in each
column:
for ( i = 0; i < sno_of_cols; i ++)
Number of comparisons = p x n
{ In worst case p = O(mn)
count = 0; So, complexity is O (mn2)

for (j = 0; j < sno_of_nonzero_elements; j ++)

if (sa[j].col == i)
count ++;
printf (“number of no-zero elements in column %d is %d”, i, count);
} However, a function using two dimensional
representation takes O(mn) time !!!!!!!

45
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sparse Matrix
• Use of programming trick helps to reduce the
complexity
• Use an array column so that column [i] stores
number of elements in ith column
for ( i = 0; i < sno_of_nonzero_elements; i ++)
{
j = sa[i].col; Complexity is now O(mn)
col [j] = col [j] + 1;
}

46
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Multi-dimensional Array
• Computer memory is one dimensional
– Multi-dimensional arrays are represented as one
dimensional array
e.g., int a[5][10][4][10][5] may be stored as b[10000]
A difficult question:
Which element in “b” contains a particular
element of “a”??

• Consider the following example:

47
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Multi-dimensional Array
• Two dimensional array a[m][n] converted to
one dimensional array b[mxn] as follows.

0 1 ….. n-1 n ….. 2*n-1 ….. i*n ….. i*n+n-1 ….. (m-1)*n ….. m*n-1

Row 0 of a Row 1 of a Row i of a Row m-1 of a

• This is row-major ordering

• Element a[i][j] is mapped to (i x n + j)th
element in array b
48
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Multi-dimensional Array
• Three dimensional array a[2][3][2] looks as
follows:
(0,0,0) (0,0,1) (0,1,0) (0,1,1) (0,2,0) (0,2,1)
(1,0,0) (1,0,1) (1,1,0) (1,1,1) (1,2,0) (1,2,1)
• To reach a[i][j][k], go to a[i][0][0]
– Number of elements between a[0][0][0] and a[i][0][0] is i x n x p
• From a[i][0][0] go to a[i][j][0]
– Number of elements j x p
• From a[i][j][0] go to a[i][j][k]
– Number of elements k

• So, a[i][j][k] mapped to i x n x p + j x p + k

49
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Multi-dimensional Array
• Consider the following m-dimensional array
a[u0][u1]….[um-1]

• The position of a[i0][i1]….[im-1] is

  i j *  ui   im 1
m2  m 1 

j 0 

i  j 1 

50
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists

51
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Limitations of Arrays
• Simple, Fast
but
• Must specify size at construction time
• Construct an array with space for n
– n = twice your estimate of largest collection
• Actual size is much less than n, wastage of space
• Tomorrow you’ll need n+1, overflow
• Shifting of elements during insertion and deletion
–More flexible system?
52
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
• Flexible space use
– Dynamically allocate space for each element as needed
• Series of nodes
– Each node of the list contains
• the data item
• a pointer to the next node
• Avoids the linear cost of insertion and deletion !

53
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
• Define a node
typedef Struct node
{
int val;
struct node *next; Recursive type definition
} node;

• Create the Header

node* create_header( int item )
{
Node* header = (node*) malloc( sizeof(node) );
header->val = item;
header->next = NULL;
Header keeps track of the entire list;
return header;
Carefully handle the header
}
54
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
• Creation of list with n nodes:
void create_list (node *header, int n) {
Header
node *temp = header, *last; Val Next
For ( i = 0; i < n; i++) temp
{
last = (node* ) malloc (sizeof (node));
New node is
scanf ( “%d”, &(lastval) ); created Val Next

lastnext = NULL; last

tempnext = last; Attached to the end of the list

temp = last; temp and last points to the last node
}
temp

} header
Val Next Val Next
last
55
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
• Printing content of a list is simple…
Void printlist (node *header)
{
node *temp=header;
while (temp != NULL)
{
printf (“%d”, tempval);
temp = temp  next;
}
}

56
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
• Insert a node in a linked list
Val Next Val Next Val Next Val Next
header
target

Val Next
temp

Val Next
temp
i
ii

Val Next Val Next Val Next Val Next

header
target

57
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
void insert (node * header, int i, node *t) {
int k; node *temp = header;
if ( i == 0)
{
tnext = temp; Insert at the first position
header = t;
return;
}
for ( k = 1; ( k < i ) && ( temp != NULL ); k++)
temp = tempnext; Move to the target node in question
If ( ( temp == NULL ) && i > 0) return;
tnext = tempnext;
tempnext = t;
return; }
58
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
• Delete a node from linked list

Val Next Val Next Val Next Val Next

header
prev target

Val Next Val Next Val Next

header
prev

59
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
void delete ( node * header, int k) {
int i; node *temp = header, *target;
If ( k == 0 )
{
header = headernext; free ( temp ); return;
}
target = tempnext;
for ( i = 1; i < k && target != NULL; i ++)
{
temp = target; target = targetnext;
}
if ( target == NULL && i > 0) return;
tempnext = targetnext; targetnext = NULL;
free (target); return; }
60
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
• Printing a linked list in reverse order
Void printreverse ( node *header ) {
node * target, *temp = NULL; Node n is printed after visiting n nodes
Node n-1 is printed after visiting n-1 nodes
if ( header == NULL) return; So, complexity=n(n+1)/2 = O(n2)
while ( temp != header)
{ target

target = header; header Val Next Val Next Val Next Val Next

while ( targetnext != temp )

temp

target = targetnext;
printf ( “%d”, targetval ); After one
temp = target;
iteration of outer
while loop
} target

}
Val Next Val Next Val Next Val Next
header
temp

61
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
• Reverse a linked list
prev curr future
Val Next Val Next Val Next Val Next
header

prev curr future

Val Next Val Next Val Next Val Next
header

62
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Lists
node * reverse ( node * header) {
node *prev = NULL, *future, *curr = header;
future = currnext;
while ( currnext != NULL)
{
currnext = prev;
prev = curr;
curr = future;
future = futurenext;
}
currnext = prev;
return ( curr ); }

63
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Doubly Linked Lists

• Traversing list backwards

– not easy with regular lists
• Insertion and deletion more pointer fixing
• Deletion is easier
– Previous node is easy to find

64
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Doubly Linked Lists
• Define a node:
typedef struct node
{
int val;
struct node *prev;
struct node *next;
} node;

65
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Doubly Linked Lists
• Insert a node after target node:
Void insert ( node *header, node *new, node *target)
{
newnext = targetnext; Set the pointers of
newprev = target; node “new”

if ( targetnext != NULL) Inserting at the end

targetnextprev = new;
targetnext = new;
}

66
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Doubly Linked Lists
• Delete a node pointed to by target:
void delete( node *header, node *target) {
if ( target != header )
targetprevnext = targetnext;
else
{
header = targetnext; Deleting the first
headerprev = NULL; node

}
if ( targetnext != NULL ) Deleting the last node
targetnextprev = targetprev;
free ( target ); }
67
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Doubly Linked Lists
• Reverse a doubly linked list:
void reverse ( node *header) {
node *last = header, *start = header;
while ( lastnext != NULL) last = lastnext; Move to the last node
while ( start != last )
{
swap ( startval , lastval);
start = startnext;
if ( start == last) break; Check for even number of nodes
last = lastprev;
}
}
68
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circular Linked Lists

• Last node points to the first node

• Traversing a circular linked list
– Different than singly linked list
• NULL pointer is missing
• Save the starting pointer and traverse until the next
field of a node becomes equal to the start node
69
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circular Linked Lists
• Identify a circular list by the pointer to the last
node
– Insertion at the start or end of a list takes O(1)
time
– Concatenating two lists also takes O(1) time

70
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Josephus Problem
• “n” children arranged a in a circle
– Children are numbered in clockwise fashion
• Choose a lucky number “m”
• Start counting from child 1 in clockwise fashion
– The mth child is eliminated
• Start the next round from the child next to the
eliminated child
– Continue until you are left with one child who is the
winner

71
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Josephus Problem
• Define a child:
typedef struct child
{
int position;
struct child *nextchild;
} child;

72
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Josephus Problem
int findwinner ( int n, int m)
{
create a circular linked list with n children;
while ( the list contain more than one child)
{
set a counter to zero;
go to the next child and increment the counter as long as it is less
than m;
delete the current child;
}
get the position of the only child in the list;
return the position; }

73
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Polynomials
• The polynomial P(x) = 3x6 + 5x3 - 4x can be
represented as:
1 -4 Next 3 5 Next 6 3 Next
header

typedef struct poly

{
int expo, coeff;
struct poly * next;
}

74
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stacks

75
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 What is a Stack
• Special form of linear list
• Principle: Last In First Out
– the last element inserted is the first one to be
removed
• Like a plate stacker

76
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stack Applications
• Real life
– Pile of books
– Plate trays
• More applications related to computer science
– Recursive function calls
– Evaluating expressions

77
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Stack Operations
• construct a stack (usually empty)
• check if it is empty
• Push: add an element to the top
• Top: retrieve the top element
• Pop: remove the top element

78
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Last In First Out

E top
D top D D
C top C C C
B top B B B B
A top A A A A A

79
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of Stack
• Allocate an array of some size (pre-defined)
– MAX_STACK_SIZE elements in stack
– Bottom stack element stored at position 0
– Last element in the stack is the top
• Define the stack:
typedef struct stack
{
int a [MAX_STACK_SIZE];
int top;
} stack;
80
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of Stack
• Push Operation
void push ( stack *s, int item)
{
if ( stop == MAX_STACK_SIZE - 1 ) return; Stack is full
else
{
stop = stop + 1; Increment the top

sa [stop] = item; Insert the element

}
}
81
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of Stack
• Pop Operation
int pop ( stack *s, int *x )
{
if ( stop == -1) return 0; Stack is empty
else
{
*x = sa[stop]; Remove topmost element
stop = stop - 1; Decrement the top
return 1;
}
}

82
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked List Implementation
• Define the nodes:
typedef struct node
{
int item;
struct node *next;
} node;

• Define the top:

typedef struct stack
{
node *mytop;
} stack;
83
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked List Implementation
• Push Operation

void push ( stack *s, int data )

{
node *newnode = ( node *) malloc ( sizeof ( node ) );
newnodeitem = data;
newnodenext = smytop; New node inserted

smytop = newnode; New node becomes the top

84
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked List Implementation
• Pop Operation
int pop ( stack *s, int *x )
{
node *temp;
if ( smytop == NULL ) Empty stack

{ x = NULL; return 0; }

*x = smytopitem; Remove item from top

temp = smytop;
smytop = smytopnext; Advance top to the next node
free ( temp ); return 1;
}
85
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Application of Stacks

86
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Function Calls
Consider events when a function begins
execution
• Stack frame is created
• Copy of stack frame pushed onto run-time stack
• Arguments copied into parameter spaces
• Control transferred to starting address of body of
function

87
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Function Calls
When function terminates
• Run-time stack popped
– Removes stack frame of terminated function
– exposes stack frame of previously executing function

• Stack frame used to restore environment of

interrupted function
• Interrupted function resumes execution

88
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Function Calls
function f( int x, int y) {
int a;
if ( term_cond ) return …;
a = ….;
return g( a );
}

function g( int z ) {
int p, q;
p = …. ; q = …. ;
return f(p,q);
}
Context
for execution of f
89
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Evaluation of Arithmetic Expression
INFIX POSTFIX PREFIX
A+B A B + + A B
A*B+C A B * C + + * A B C
A * (B + C) A B C + * * A + B C
A - (B - (C - D)) A B C D--- -A-B-C D
A-B-C-D A B-C-D- ---A B C D

• Most compilers convert an expression in infix notation

to postfix notation

• Advantage:
 expressions can be written without parentheses
90
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Evaluation of Arithmetic Expression
• Evaluating Postfix Expression
– "By hand" (Underlining technique):
• Scan the expression from left to right
to find an operator. 2 3 4 + 5 6 - - *
2 3 4 + 5 6 - - *
• Locate ("underline") the last two
preceding operands and combine 2 7 5 6 - - *
them using this operator. 2 7 5 6 - - *
• Repeat until the end of the 2 7 -1 - *
expression is reached. 2 7 -1 - *
2 8 *
2 8 *
16
91
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Evaluation of Arithmetic Expression
• Evaluating Postfix Expression
1. Initialize an empty stack
2. Repeat the following until the end of the expression is
encountered
1. Get the next element from the expression
2. Operand – push onto stack
Operator – do the following
1. Pop 2 values from stack
2. Apply operator to the two values
3. Push resulting value back onto stack
3. When end of expression encountered, value of
expression is the (only) number left in stack

92
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Evaluation of Arithmetic Expression
• Evaluating Postfix
Expression

93
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Evaluation of Arithmetic Expression
• Infix to Postfix Conversion
– By hand: "Fully parenthesize-move-erase" method:
• Fully parenthesize the expression.
• Replace each right parenthesis by the corresponding operator.
• Erase all left parentheses.

A * B + C  ((A * B) + C) A * (B + C)  (A * (B + C) )
 ((A B * C +  (A (B C + *
 A B * C +  A B C + *

94
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Evaluation of Arithmetic Expression
1. Initialize an empty stack of operators Operator In-Stack Input
2. While !end of expression Priority Priority
a) Get next input "token" from infix expression +, - 1 1
b) If token is … *, / 2 2
^ 3 4
i. operand display it
( 0 4
ii. operator
if operator has higher priority than top of stack
push token onto stack
else
pop and display top of stack
repeat comparison of token with top of stack
iii. "(" : push onto stack
iv. ")" : pop and display stack elements until
"(" occurs, do not display it
3. When end of infix reached, pop and display stack items until empty

95
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Evaluation of Arithmetic Expression
• (A+B)^(C-D)^E

+ top + top
( top ( top ( ( top
top ^

A A AB AB+ AB+

- top - top
( top ( top ( ( ^ top
^ ^ ^ ^ ^ top ^
AB+ AB+C AB+C AB+CD AB+CD- AB+CD-

^ top
^ ^ top
top
AB+CD-E AB+CD-E^ AB+CD-E^^

96
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Queues

97
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 What is a queue
• Stores a set of elements in a particular order
• Stack principle: FIRST IN FIRST OUT
• = FIFO
• It means: the first element inserted is the first one to
be removed
• Example

• The first one in line is the first one to be served

98
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Queue Applications
• Real life examples
– Waiting in line
– Waiting on hold for tech support

• Applications related to Computer Science

– Threads
– Job scheduling (e.g. Round-Robin algorithm for
CPU allocation)

99
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 First In First Out
Front Rear

Front Rear

A B

Front Rear

A B C

Front Rear

B C

Front Rear
100
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Job Scheduling

front rear Q[0] Q[1] Q[2] Q[3] Comments

-1 -1 queue is empty
-1 0 J1 Job 1 is added
-1 1 J1 J2 Job 2 is added
-1 2 J1 J2 J3 Job 3 is added
0 2 J2 J3 Job 1 is deleted
1 2 J3 Job 2 is deleted

101
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Queue Operations
• Create a queue
• Check if a queue is full or not
• Check if a queue is empty or not
• Add an element to a queue (enqueue)
• Remove an element from queue (dequeue)

102
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of Queue
• As with the array-based stack implementation, the
array is of fixed size
– A queue of maximum N elements
• Slightly more complicated
– Need to maintain track of both front and rear
• Define the queue:
typedef struct queue
{
int a[MAX_SIZE];
int rear, front;
} queue;
103
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of Queue
• Enqueue Operation
int enqueue (queue *q, int data)
{
if (qrear == MAX_SIZE – 1) Queue is full
return 0;
else
{
qrear == qrear + 1; Increment the rear
qa[qrear] = data; Insert the element
return 1;
}
}

104
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Array Implementation of Queue
• Dequeue Operation
int dequeue (queue *q, int *data)
{
if (qrear == qfront)
{
Queue is empty
qfront = -1;
qrear = -1;
*data = NULL;
return 0;
}
else
{
qfront = qfront + 1; Increment the front
*data = qa[qfront]; Remove the element
return 1;
}
}
105
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circular Queue
EMPTY QUEUE
[2] [3] [2] [3]
J2 J3

[1] [4] [1] J1 [4]

[0] [5] [0] [5]

front = 0 front = 0
rear = 0 rear = 3

Can be seen as a circular queue

106
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circular Queue
Leave one empty space when queue is full. Why?
FULL QUEUE FULL QUEUE
[2] [3] [2] [3]
J2 J3 J8 J9

[1] J1 J4 [4][1] J7 [4]

J5 J6 J5

[0] [5] [0] [5]

front =0 front =4
rear = 5 rear =3
How to test when queue is empty?
How to test when queue is full?
107
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circular Queue
• Enqueue Operation

void enqueue (queue *q, int data)

{
qrear = (qrear +1) % MAX_SIZE;
if (qfront == qrear)
return;
qa[qrear] = item;
}

108
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Circular Queue
• Dequeue Operation

void dequeue (queue *q, int *data)

{
if (qfront == qrear)
return;
qfront = (qfront+1) % MAX_SIZE;
*data = qa[qfront];
}

109
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked List Implementation
• Define the nodes
Val Next Val Next Val Next Val Next
front
rear
typedef struct node
{
int item;
struct node *next;
} node;
• Define the rear and front
typedef struct queue
{
node *rear;
node *front;
}
110
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked List Implementation
• Enqueue Operation
void enqueue (queue *q, int data)
{
node *temp = (node *) malloc (size of (queue));
tempitem = data; New node
tempnext = NULL; created
if (qfront == NULL)
Queue is empty
{
qfront = temp;
qrear = temp;
return;
}
qrearnext = temp; Insert at the rear
qrear = temp; New node becomes rear
}
111
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked List Implementation
• Dequeue Operation
int dequeue (queue *q, int *data)
{
node *temp;
if (qfront == NULL)
{
data = NULL; Queue is empty
return 0;
}
temp = qfront;
*data = tempitem;
qfront = qfrontnext;
if (qrear == temp) Only node in
qrear = NULL; the Queue
free (temp);
return 1;
}
112
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Trees

113
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Introduction
• Non-linear data structure
• Depicts hierarchical relationship between the nodes
– Parent-child is typical relation
President-CEO Root

Production Sales
Manager Manager
Personnel
Manager

Purchasing Warehouse Shipping

Supervisor Supervisor Supervisor

leaf HIERARCHICAL TREE STRUCTURE

114
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Another Example
• Unix / Windows file structure

115
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definition
 A tree T is a finite set of one or more nodes
such that:
 There is a specially designated node called
the root.
 The remaining nodes are partitioned into n>=0
disjoint sets T1, ..., Tn, where each of these sets is
a tree.
 We call T1, ..., Tn the subtrees of the root.

116
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Terminology
Degree of a node: number of Level
nodes connected of that node
– The node with degree 1 is a leaf or A 1
terminal node.
Children of the same parent are
siblings. B C D 2
Ancestors of a node: all the nodes
along the path from the root to
the node.
E F G H I J 3
Level: level of a node is one more
than its parent. Root node has a K L M
level 1. 4
Height of a tree: maximum level
of any node

117
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree
A special class of trees: max number of child for
each node is 2.
Recursive definition: A binary tree is a finite set
of nodes that is either empty or consists of a root
and two disjoint binary trees called the left
subtree and the right subtree.
Any tree can be transformed into binary tree.
by left child-right sibling representation
Total number of binary trees possible with n
nodes is 2nCn - 2nCn-1
118
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Examples
A A
A
B B

C B C

D
D E F G

E
H I
119
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Examples
Left Child - Right Sibling A

A B
E C
B C D

F G D
K
E F G H I J

L H
K L M

M I
General Tree
Binary Tree J
120
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Properties
The maximum number of nodes on level i
of a binary tree is 2i-1, i>=1.
The maximum number of nodes in a
binary tree of depth h is 2h-1, h>=1.

Prove by induction

2
h
i 1
 2 1 h
In other words
i 1 h=log(n+1)
121
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Properties
For any nonempty binary tree, T, if n0 is the
number of leaf nodes and n2 the number of
nodes with 2 children, then n0=n2+1
proof:
Let n and B are the total number of nodes & branches in T.
Let n0, n1, n2 represent the nodes with no children, single
child, and two children respectively.
n= n0+n1+n2, B+1=n, B=n1+2n2 ==>
n1+2n2+1= n,
n1+2n2+1= n0+n1+n2 ==> n0=n2+1
122
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Full Binary Tree
• If all non-leaf nodes of a binary tress have exactly
two non-empty children and all leaf nodes are at
the same level.
• A full binary tree of depth h is a binary tree of
depth h having 2h -1 nodes, h>=1.
A

B C

D E F G

H I J K L M N O

123
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Complete Binary Tree
• A full binary tree or Full up A
to level h-1 and if any node
at level h-1 has one child, B C

that must be a left child. D E F G

H I J K L M N O

A Complete Binary Trees A

B C B C

D E F G D E F G

H I H I J

124
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Complete Binary Tree
• A full binary tree or Full up
to level h-1 and if any node A
at level h-1 has one child,
B C
that must be a left child.
D E

H I
A

B C Non-Complete Binary Trees

D E F G

H I K

125
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Representation
If a complete binary tree with n nodes is
represented sequentially, then for
any node with index i, 1<=i<=n, we have:
parent(i) is at i/2 if i!=1. If i=1, i is at the root and has no parent.
leftChild(i) is at 2i if 2i<=n. If 2i>n, then i has no left child.
rightChild(i) is at 2i+1 if 2i +1 <=n. If 2i +1 >n, then i has no
right child.
Relationships between labels
1
of children and parent:
1 2 3
i
2 3
2i 2i+1
4 5 6 7
126
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Representation
A [1] A
[1] A
[2] B
Wastage of space [2] B
[3] -- [3] C
B
[4] C [4] D
[5] -- [5] E
C [6] -- A [6] F
[7] G
[7] -- H
[8]
D [8] D B C
[9] I
[9] --
. . D E F G
E
[16] E
H I
127
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Linked Representation
typedef struct btnode
{
int data;
btnode *lchild, *rchild;
}btnode;

data
left data right

left right

128
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Creation of Binary Tree
p=(btnode*)malloc(sizeof(btnode));
main () pdata=3;
{ plchild=prchild=NULL;
qlchild=p;
btnode *Root=NULL; q=p;
btnode *p, *q;
q=Root;
p=(btnode*)malloc(sizeof(btnode)); p=(btnode*)malloc(sizeof(btnode));
pdata=1; pdata=4;
plchild=prchild=NULL;
plchild=prchild=NULL; qrchild=p;
Root=p; q=p; }

p=(btnode*)malloc(sizeof(btnode)); 1
pdata=2;
plchild=prchild=NULL;
2 3
qlchild=p; q=p;
4
129
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Traversal
Traversal is the process of visiting every node
once
Let l, R, and r denotes moving left, visiting
the node, and moving right.
Six possible combinations of traversal
lRr, lrR, Rlr, Rrl, rRl, rlR
Adopt convention that we traverse left before
right, only 3 traversals remain
lRr, lrR, Rlr
inorder, postorder, preorder
130
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Traversal
Inorder Traversal
1. Traverse left subtree
2. Visit the root
3. Traverse right subtree

Postorder Traversal Preorder Traversal

1. Traverse left subtree 1. Visit the root
2. Traverse right subtree 2. Traverse left subtree
3. Visit the root 3. Traverse right subtree
131
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Traversal

• Inorder: A
HDIBEAFCG
• Postorder: B C

HIDEBFGCA D E F G
• Preorder:
ABDHIECFG H I

132
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Traversal
+
Inorder
A/B*C*D+E
* E infix expression

* D postorder
AB/C*D*E+
postfix expression
/ C
preorder
A B +**/ABCDE
prefix expression

133
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Traversal
void inorder(btnode *Root)
{
if (Root) {
inorder(Root->lchild);
printf(“%d”,Root->data);
inorder(Root->rchild);
}
}
134
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Traversal
void postorder(btnode *Root)
{
if (Root) {
postorder(Root->lchild);
postorder(Root->rchild);
printf(“%d”,Root->data);
}
}
135
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Tree Traversal
void preorder(btnode *Root)
{
if (Root) {
printf(“%d”,Root->data);
preorder(Root->lchild);
preorder(Root->rchild);
}
}
136
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reconstruction of Binary Tree
• It is impossible to reconstruct binary tree from
inorder or preorder or postorder traversals
alone.
• However, if inorder and preorder traversals
are given, a unique binary tree can be
reconstructed

137
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reconstruction of Binary Tree
A

B C

D E F G

Inorder: D B E A F C G

Preorder: A B D E C F G
138
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Reconstruction of Binary Tree
A
A

B C
I.T: D B E I.T: F C G
P.T: B D E P.T: C F G
I.T: D I.T: E I.T: F I.T: G
P.T: D P.T: E P.T: F P.T: G

B C

D E F G
139
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Search Trees
• Definition
– The keys in a nonempty left subtree (right
subtree) are smaller (larger) than the key in
the root of subtree.
– The left and right subtrees are also binary
search trees. K

All < K All > K

140
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Binary Search Trees
• Binary Search Trees (BST) are a type of
Binary Trees with a special organization
of data.

• Leads to O(log n) complexity for searches,

insertions and deletions in certain types of
BST (balanced trees).
– O(h) in general

141
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Examples and Counter Examples

8 5

5 11 4 8

2 6 10 12 1 7 11

4 7 9 14 3

13

142
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Examples and Counter Examples
8

5 11

2 4 10 18

4 15 20

21

143
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Inorder Traversal
10

5 15

2 9 20

7 17 30

25791015172030

What does this guarantee

with a BST?
144
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 rRl Traversal
10

5 15

2 9 20

7 17 30

30 20 17 15 109752

What does this guarantee

with a BST?
145
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 BST Representation
typedef struct bstnode
{
int data;
bstnode *lchild, *rchild;
}bstnode;

146
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Searching in a BST
bstnode *search(int key, bstnode * root)
{
if (root == NULL) return root; 8
else if (key < rootdata)
5 11
return search(key, rootlchild);
else if (key > rootdata) 2 6 10 12
return find(key, rootrchild);
else 4 7 9 14
return root;
13
}

147
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into a BST
 based on comparisons of the new item and
values of nodes in the BST
 starting at the root probe down the tree till
you find a node whose left or right pointer is
empty and is a logical place for the new value
 In other words, all inserts take place at a leaf
or at a leaflike node – a node that has only
one null subtree.

148
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into a BST

30 30 30

40 5 40 5 40
5

2 2 80 2 35 80

Insert 80 Insert 35

149
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into a BST
void insert(bstnode * newnode, bstnode * root)
{
if (rootdata > newnodedata)
{
if (rootlchild == NULL)
rootlchild=newnode;
else
insert( newnode, rootlchild );
}
else
{
if (rootrchild == NULL)
rootrchild=newnode;
else
insert( newnode, rootrchild );
}
}

150
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into a BST
 The order of supplying the data determines where it
is placed in the BST , which determines the shape of
the BST
 Create BSTs from the same set of data presented
each time in a different order:
a) 17 4 14 19 15 7 9 3 16 10
b) 9 10 17 4 3 7 14 16 15 19

c) 19 17 16 15 14 10 9 7 4 3 can you guess this shape?

151
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Inorder Successor
10
bstnode * successor(bstnode * n)
{
5 15
bstnode *iosuccessor;
if (nrchild == NULL)
iosuccessor= ???; 2 9 20
else
{ 7 17 30
iosuccessor=nrchild;
while (iosuccessorlchild != NULL)
iosuccessor=iosuccessorlchild;
}
return iosuccessor; How many children can the
} inorder successor of a node have?
152
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Inorder Predecessor
10
bstnode * predecessor(bstnode * n)
{
5 15
bstnode *iopredecessor;
if (nlchild == NULL)
iopredecessor= ???; 2 9 20
else
{ 7 17 30
iopredecessor=nlchild;
while (iopredecessorrchild != NULL)
iopredecessor=iopredecessorrchild;
}
return iopredecessor; How many children can the inorder
} predecessor of a node have?
153
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from a BST
• Following are the possible cases when we delete
a node:
– The node to be deleted has no children.
• Set the respective pointer of its parent to NULL.
– The node to be deleted has only a right subtree.
• Attach respective pointer of node’s parent to right subtree.
– The node to be deleted has only a left subtree.
• Attach respective pointer of node’s parent to left subtree.
– The node to be deleted has two subtrees.
• Replace node’s data with data in inorder successor
(predecessor) and delete the inorder successor
(predecessor).
154
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from a BST
Case 1: deleting a node with 2 EMPTY SUBTREES

8 8

Delete 9

5 11 5 11

2 6 10 12 2 6 10 12

4 7 9 14 4 7 14

13 13
155
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from a BST
Case 2: deleting a node with only RIGHT SUBTREES

8 8

Delete 6

5 11 5 11

2 6 10 12 2 7 10 12

4 7 9 14 4 9 14

13 13
156
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from a BST
Case 3: deleting a node with only LEFT SUBTREES

8 8

Delete 6

4 11 4 11

2 6 10 12 2 5 10 12

3 5 9 14 3 9 14

13 13
157
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from a BST
Case 4: deleting a node with 2 NON-EMPTY SUBTREES

8 9

Delete 8

5 11 5 11

2 6 10 12 2 6 10 12

4 7 9 14 4 7 9 14

13 13
158
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from a BST
bstnode * delete (bstnode * root, bstnode * n, bstnode * parent)
{
bstnode *iosuccessor, *retval;
if (nlchild != NULL && nrchild != NULL)
{ This function takes node to be deleted, its parent
successor (n, &parent, &iosuccessor); iosuccessor
as argument. When the function terminates
contains the inorder successor of n,
ndata = iosuccessordata; parent becomes the parent of iosuccessor

n=iosuccessor; Now delete the inorder successor

}
if (nlchild == NULL) n does not have left subtree
{
if (parent != NULL) Check for deleting root

159
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from a BST
Check to see whether n belongs
if (parentlchild == n) to the left subtree of parent

parentlchild=nrchild;
else
parentrchild=nrchild;
retval=root;
}
else
retval=nrchild; Deleting root
}
if (nrchild == NULL)
{
if (parent != NULL)

160
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from a BST
{
if (parentlchild == n)
parentlchild=nlchild;
else
parentrchild=nlchild;
retval=root;
}
else
retval=nlchild; Deleting root
}
return retval;
}

161
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of BST Operations
 The complexity of operations search,
insert and delete in BST is O(h) , where
h= O(log n), the height of BST.

But, the BST can take a linear shape and the

operations will become O (n)

162
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Height Balanced or AVL Trees
• Unbalanced Binary Search Trees are bad. Worst
case: operations take O(n).
• Height Balanced or AVL (Adelson-Velskii &
Landi) trees maintain balance.
– For each node in BST, height of left subtree and height
of right subtree differ by a maximum of 1.

A A

h
h-2
h-1

163
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Height Balanced or AVL Trees
typedef struct avlnode
{
int data;
int balancefactor;
bstnode *lchild, *rchild;
}avlnode;

164
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Examples of AVL trees
10 10

5 20 5 20

3 3 43

1
2

1 3
165
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
Insert 1 in the following AVL tree

12

8 16

4 10 14

2 6

166
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
After inserting 1 +2
12

+2
8 16

4 10 14

2 6

1
167
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
• Insertion of a node into AVL tree may result in
imbalance.
• To ensure balance condition, after insertion of a
new node, back up the path from the inserted
node to root and calculate balance factor for
each node.
– If the balance condition does not hold in a
certain node, we do one of the following
rotations:
• Single rotation
• Double rotation
168
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
hP=hQ=hR k1 k1

k2 k2

R P
P Q Q R

Possible cases of insertions that may result imbalance

• An insertion into the subtree: • An insertion into the subtree:
– Case 1: insert into P (outside) – Case 3: insert into Q (inside)
– Case 2: insert into Q (inside) – Case 4: insert into R (outside)

169
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
Case 1: Single Rotation
avlnode* rotateright (avlnode *y)
{
avlnode *x;
hA=hB+1 x=ylchild;
ylchild=xrchild;
hB=hC xrchild=y;
k2 k1 }
return x;

k1 k2

C
B A B C
A
170
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
Case 4: Single Rotation
avlnode* rotateleft (avlnode *y)
{
avlnode *x;
x=yrchild; hA=hB
yrchild=xlchild;
xlchild=y; hC=hB+1
return x; k2 k1
}
k1 k2

A
A B C B
C
171
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
Case 2 & 3 (inside case): Single Rotation does not work

k2 k1

k1 k2

C A
A C
B B

hB=hA+1
hA=hC
172
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
Case 2 & 3 (inside case): Double Rotation
+2 +2
k3 k3

-1 +1
k1 k2

k2 k1

D D
A C
B C A B

hA=hB=hC=hD
173
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
Case 2 & 3 (inside case): Double Rotation

k2

k1 k3

A B C D

174
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
Double Rotation

k3 k2

k1 k1 k3
k2

D A B C D
A
B C

hA=hB=hC=hD
175
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree
Double Rotation
k2 k1

k1 k3 k3
k2

A B C D A
D
B C

hA=hB=hC=hD
176
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree

Insert 3 into the AVL tree

11 11

8 20 4 20

4 16 27 3 8 16 27
3

177
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Insertion into an AVL Tree

Insert 5 into the AVL tree

11 11

8 20 5 20

4 16 27 4 8 16 27
5

178
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
• Deleting a node from an AVL Tree is similar to
that of deleting a node from a binary search
tree. However, it may unbalance the tree.
• Starting from the deleted node, check all the
nodes in the path up to the root for the first
unbalance node.
– Use appropriate single or double rotation.
– May need to continue searching for unbalanced
nodes all the way to the root.
179
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
• Deletion:
– Case 1: if X is a leaf, delete X
– Case 2: if X has 1 child, use it to replace X
– Case 3: if X has 2 children, replace X with its
inorder predecessor (and recursively
delete it)
• Rebalancing

180
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 55
60

20 70

10 40 65 85

5 15 30 50 80 90

55

181
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 55
60

20 70

10 40 65 85

5 15 30 50 80 90

55

182
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 50
60

20 70

10 40 65 85

5 15 30 50 80 90

55

183
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 50
60

20 70

10 40 65 85

5 15 30 50 80 90

55

184
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 60
60

20 70

10 40 65 85

5 15 30 50 prev 80 90

55

185
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 60
55

20 70

10 40 65 85

5 15 30 50 80 90

186
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 55
55

20 prev 70

10 40 65 85

5 15 30 50 80 90

187
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 55
50

20 70

10 40 65 85

5 15 30 80 90

188
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 50
50

20 prev 70

10 40 65 85

5 15 30 80 90

189
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 50
40

20 70

10 30 65 85

5 15 80 90

190
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 40
40

20 prev 70

10 30 65 85

5 15 80 90

191
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
Delete 40
30

20 70

10 Case ? 65 85

5 15 80 90

192
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Delete a Node from AVL Tree
After Rebalancing
30

10 70

5 20 65 85

15 80 90

193
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Graph Algorithms

194
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
• A graph G = (V,E) is composed of:
V: Finite, non-empty set of vertices
E: set of edges connecting the vertices in V
= Subset of VxV
• An edge e = (u,v) is a pair of vertices.
a b
V= {a, b, c, d, e}
c
E= {(a,b), (a,c), (a,d), (b,e),
(c,d), (c,e), (d,e)}
d e
195
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
• An undirected graph is one in which the pair of
vertices in a edge is unordered, (v0, v1) = (v1,v0)
• A directed graph is one in which each edge is a
directed pair of vertices, <v0, v1> != <v1,v0>
• If (v0, v1) is an edge in an undirected graph,
– v0 and v1 are adjacent
– The edge (v0, v1) is incident on vertices v0 and v1
• If <v0, v1> is an edge in a directed graph
– v0 is adjacent to v1, and v1 is adjacent from v0

196
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
The degree of a vertex is the number of edges
incident to that vertex
For directed graph,
the in-degree of a vertex v is the number of
edges that have v as the end vertex
the out-degree of a vertex v is the number of
edges that have v as the start vertex
if di is the degree of a vertex i in a graph G
with n vertices and e edges, the number of
edges is

n 1

e  ( di) / 2
0

197
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
3 0
0 2
1 2
3 1 2 3 3 3
3 3 4 5 6
3
1 1 1 1
0 in:1, out: 1

1 in: 1, out: 2

2 in: 1, out: 0
198
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
• path: sequence of
3 2

vertices v1,v2,. . .vk

such that consecutive
3

vertices vi and vi+1 are 3 3

adjacent.
a b a b

c c

d e d e
abedc bedc

199
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
• simple path: no repeated vertices
• cycle: simple path, except that the last vertex
is the same as the first vertex
a b a b

bec adca
c c

d e d e

200
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
• connected graph: any two vertices are connected by some path

• subgraph: subset of vertices and edges forming a graph

• connected component: collection of subgraphs which are not
connected. e.g., the graph below has 3 connected
components.

201
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
• A weighted graph associates weights with the
edges
– e.g., a road map: edges might be weighted with
distance
10

7
8 8
6
6
10

202
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Definitions
• We will typically express running times in
terms of |E| and |V|
– If |E|  |V|2 the graph is dense
– If |E|  |V| the graph is sparse

• If you know you are dealing with dense or

sparse graphs, different data structures may
make sense

203
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Graph Representation

• Adjacency Matrix
• Adjacency Lists
• Incidence Matrix

204
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Adjacency Matrix
 Let G=(V,E) be a graph with n vertices.
 The adjacency matrix of G is a two-dimensional
nxn array, say adj_mat
 If the edge (vi, vj) is in E(G), adj_mat[i][j]=1
 If there is no such edge in E(G), adj_mat[i][j]=0

 The adjacency matrix for an undirected graph is

symmetric; the adjacency matrix for a directed
graph need not be symmetric

205
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Adjacency Matrix
0 1
a
1 2 2 d 4
3 b c
A 0 1 2 3
3
0 0 1 1 1 A 1 2 3 4
1 1 0 1 1 1 0 1 1 0
2 1 1 0 1 2 0 0 1 0
3 1 1 1 0 3 0 0 0 0
4 0 0 1 0
206
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Adjacency Matrix
• From the adjacency matrix, to determine the connection
of vertices is easy
– The degree of a vertex i is the number of 1’s in ith row
– For a directed graph, the number of 1’s in ith row is the
out_degree, while the number of 1’s in ith column in_degree.
• Time: to list all vertices adjacent to u: O(V).
• Time: to determine if (u, v)  E: O(1).
• Space: O(V2).
– Not memory efficient for large graphs.
• Parallel edges cannot be represented
• Can store weights instead of bits for weighted graph.
207
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Adjacency Lists
• Adjacency list: for each vertex v  V, store a
list of vertices adjacent to v
0
0
1 2
3 0 1
1 0 2 1
0 1 2 3
2
1 0 2 3
2 0 1 3 2
3 0 1 2
208
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Adjacency Lists
typedef struct adjvertex
{
int vertex;
struct node *next;
}adjvertex;

typedef struct graph

{
int no_of_Vertices;
adjvertex *adjlist [100];
}graph;
209
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Adjacency Lists
• How much storage is required?
– The degree of a vertex v = # incident edges
• Directed graphs have in-degree, out-degree
– For directed graphs, # of items in adjacency lists is
S out-degree(v) = |E|
takes O(V + E) storage
– For undirected graphs, # items in adjacency lists is
S degree(v) = 2 |E|
also O(V + E) storage
• So: Adjacency lists take O(V+E) storage
210
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Incidence Matrix
• Consider a matrix A = (aij), rows corresponds
to vertices, column corresponds to edges.
• For undirected graph:
• aij= 1 if ej is incedent to vi
= 0 otherwise
• For directed graph:
• aij= 1 if ej is incedent out of vi
= -1 if ej is incedent into vi
= 0 otherwise

211
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Incidence Matrix
0

1 2
3

A (0,1) (0, 2) (0, 3) (1, 2) (1, 3) (2, 3)

0 1 1 1 0 0 0
1 1 0 0 1 1 0
2 0 1 0 1 0 1
3 0 0 1 0 1 1
212
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Graph Traversal
• Given: a graph G = (V, E), directed or
undirected
• Goal: systematically explore every vertex and
every edge
• Ultimately: build a tree on the graph
– Pick a vertex as the root
– Choose certain edges to produce a tree

213
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Graph Traversal
• Depth First Search
– Once a possible path is found, continue the search
until the end of the path
– Think of a Stack
• Breadth First Search
– Start several paths at a time, and advance in each
one step at a time
– Think of a Queue

214
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
• We start at vertex s, and mark s “visited”. Next
we label s as our current vertex called u.
• Now we travel along an arbitrary edge (u, v).
• If edge (u, v) leads us to an already visited
vertex v we return to u.
• If vertex v is unvisited, we move to v, mark v
“visited”, set v as our current vertex, and
repeat the previous steps.

215
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
void DFS (int start)
{
int v;
adjvertex *adj;
visited [start] = 1;
printf (“%d”, start);
adj = gadjlist [start];
while (adj ! = NULL)
{
v = adjvertex;
if (! visited [v])
DFS (v);
adj = adj next;
}
} Total running time: O(V+E)
216
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

Adjacency Lists
D E
A: F C B G
B: A
C: A
F D: F E
E: G F D
F: A E D
G: E A

217
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

D E
F newly
discovered
F
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Stack
Finished
218
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

A already
marked B C G

D E

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

219
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

E newly
D EE
discovered

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

220
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

G newly
discovered
B C G

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

221
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

visit(G)
E already B C G
marked (G, E) (G, A)

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

222
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

visit(G)
A already B C G
marked (G, E) (G, A)

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

223
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A
Finished G

visit(G)
B C G (G, E) (G, A)

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

224
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

F already B C G
marked

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

225
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

D newly visit(E)
D E
discovered (E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

226
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

F already visit(D)
B C G
marked (D, F) (D, E)

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
Marked visit(A)
(A, F) (A, C) (A, B) (A, G)
Active
Finished Stack

227
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

E already visit(D)
B C G
marked (D, F) (D, E)

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
Marked visit(A)
(A, F) (A, C) (A, B) (A, G)
Active
Finished Stack

228
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A
Finished D

visit(D)
B C G
(D, F) (D, E)

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
Marked visit(A)
(A, F) (A, C) (A, B) (A, G)
Active
Finished Stack

229
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

Finished E
B C G

visit(E)
D E
(E, G) (E, F) (E, D)

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

230
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

D already B C G
marked

D E

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

231
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

Finished F
D E

visit(F)
F
(F, A) (F, E) (F, D)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

232
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

C newly
discovered

B C G

D E

F
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

233
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

A already B C G
marked

D E

visit(C)
F
(C, A)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

234
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

Finished C
D E

visit(C)
F
(C, A)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

235
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B newly
BB C G
discovered

D E

F
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

236
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

A already B C G
marked

D E

visit(B)
F
(B, A)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

237
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

Finished B
D E

visit(B)
F
(B, A)
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

238
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

G already B C G
finished

D E

F
Undiscovered
visit(A)
Marked
(A, F) (A, C) (A, B) (A, G)
Active
Finished
Stack

239
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

D E

Finished A
F
Undiscovered
Marked visit(A)
(A, F) (A, C) (A, B) (A, G)
Active
Finished Stack

240
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Depth First Search
A

B C G

D E

F
Undiscovered
Marked
Active
Finished
241
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
• Breadth-First Search (BFS) traverses a graph, and in doing so
defines a tree with several useful properties.
• The starting vertex s has level 0, and, as in DFS, defines that
point as an “anchor.”
• In the first round, all of the edges that are only one edge away
from the anchor are visited.
• These vertices are placed into level 1;
• In the second round, all the new edges from level 1 that can
be reached are visited and placed in level 2.
• This continues until every vertex has been assigned a level.
• The label of any vertex v corresponds to the length of the
shortest path from s to v.
242
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
void BFS (int start) {
int v, result; queue q; adjvertex *adj;
visited [start] = 1; enqueue (start, &q);
while ((result = dequeue (&v, &q)) != -1) { Nodes dequeued
printf (“%d”, v); adj = gadjlist [v];
while (adj != NULL) {
if (! visited [adjvertex])
{
visited [adjvertex] = 1; Nodes enqueued
enqueue (adjvertex, &q);
exactly once
}
adj = adjnext;
} } }
Total running time: O(V+E)
243
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
2 4 8

s 5 7

3 6 9

244
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1
2 4 8

0 s 5 7

3 6 9

Undiscovered
Discovered
Top of queue Queue: s
Finished
245
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1
Current node = s 2 4 8

0 s 5 7

3 6 9

Undiscovered
Discovered
Top of queue Queue:
Finished
246
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1
Current node = s 2 4 8

0 s 5 7

3 6 9

Undiscovered
Discovered
Top of queue Queue: 2
Finished
247
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1
Current node = s 2 4 8

0 s 5 7
1

3 6 9

Undiscovered
Discovered
Top of queue Queue: 2 3
Finished
248
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1
Current node = s 2 4 8

0 s 5 7
1

3 6 9

Undiscovered
Discovered
Top of queue Queue: 2 3 5
Finished
249
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 2 2 4 8

0 s 5 7
1

3 6 9

Undiscovered
Discovered
Top of queue Queue: 3 5
Finished
250
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 2 2 4 8

5 already discovered:
0 s 5 7
don't enqueue
1

3 6 9

Undiscovered
Discovered
Top of queue Queue: 3 5 4
Finished
251
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 2 2 4 8

0 s 5 7
1

3 6 9

Undiscovered
Discovered
Top of queue Queue: 2 3 5 4
Finished
252
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 3 2 4 8

0 s 5 7
1

3 6 9

Undiscovered
Discovered
Top of queue Queue: 5 4
Finished
253
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 3 2 4 8

0 s 5 7
1

3 6 9

1 2

Undiscovered
Discovered
Top of queue Queue: 5 4
Finished
254
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 3 2 4 8

0 s 5 7
1

3 6 9

1 2

Undiscovered
Discovered
Top of queue Queue: 5 4 6
Finished
255
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 5 2 4 8

0 s 5 7
1

3 6 9

1 2

Undiscovered
Discovered
Top of queue Queue: 4 6
Finished
256
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 5 2 4 8

0 s 5 7
1

3 6 9

1 2

Undiscovered
Discovered
Top of queue Queue: 4 6
Finished
257
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2
Current node = 4 2 4 8

0 s 5 7
1

3 6 9

1 2

Undiscovered
Discovered
Top of queue Queue: 6
Finished
258
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 4 2 4 8

0 s 5 7
1

3 6 9

1 2

Undiscovered
Discovered
Top of queue Queue: 6
Finished
259
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 4 2 4 8

0 s 5 7
1

3 6 9

1 2

Undiscovered
Discovered
Top of queue Queue: 6 8
Finished
260
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 6 2 4 8

0 s 5 7
1 3

3 6 9

1 2

Undiscovered
Discovered
Top of queue Queue: 8
Finished
261
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 6 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue: 8 7
Finished
262
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 6 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue: 8 7 9
Finished
263
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 6 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue: 7 9
Finished
264
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 7 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue: 9
Finished
265
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 7 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue: 9
Finished
266
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 7 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue: 9
Finished
267
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 7 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue: 9
Finished
268
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 9 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue:
Finished
269
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 9 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue:
Finished
270
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 9 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue:
Finished
271
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
Current node = 9 2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

Undiscovered
Discovered
Top of queue Queue:
Finished
272
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Breadth First Search
1 2 3
2 4 8

0 s 5 7
1 3

3 6 9

1 2 3

BFS Tree

273 273
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Single Source Shortest Path Problem

• The problem of finding shortest paths from

a source vertex v to all other vertices in
the graph.

274
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm
solution to the single-source shortest path problem in
graph theory.

Works on both directed and undirected graphs. However,

all edges must have nonnegative weights.

Approach: Greedy : makes local optimum choice in each

step hoping to reach global optimum.

Input: Weighted graph G={E,V} and source vertex v V,

such that all edge weights are nonnegative

Output: Lengths of shortest paths (or the shortest paths

themselves) from a given source vertex v V to all other
vertices 275
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm
dist[s] ←0 (distance to source vertex is zero)
for all v ∈ V–{s}
do dist[v] ←∞ (set all other distances to infinity)
S←∅ (S, the set of visited vertices is initially empty)
Q←V (Q, the queue initially contains all vertices)
while Q ≠∅ (while the queue is not empty)
do u ← mindistance(Q,dist) (select the element of Q with the min. distance)
S←S∪{u} (add u to list of visited vertices)
for all v ∈ neighbors[u]
do if dist[v] > dist[u] + w(u, v) (if new shortest path found)
then d[v] ←d[u] + w(u, v) (set new value of shortest path)
return dist

Total running time: O(n2)

276
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

277
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

278
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

279
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

280
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

281
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

282
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

283
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

284
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

285
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Dijkstra’s Algorithm

286
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Spanning Trees

A spanning tree of a graph is a subgraph that contains all

the vertices and is a tree.
A graph may have many spanning trees.

Graph A Some Spanning Trees from Graph A

or or or

287
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Minimum Spanning Trees
The Minimum Spanning Tree for a given graph is the Spanning Tree of
minimum cost for that graph.

Graph Minimum Spanning Tree

7
2 2
5 3 3
4
1 1

7 7 7 7

7 7

288
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
Algorithms for Obtaining the Minimum Spanning Tree

• Kruskal's Algorithm

• Prim's Algorithm

289
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Kruskal's Algorithm

o This algorithm creates a forest of trees.

o Initially the forest consists of n single node trees (and no edges).
o At each step, we add one edge (the cheapest one) so that it joins two
trees together.
o If it were to form a cycle, it would simply link two nodes that were
already part of a single connected tree, so that this edge would not be
needed.

290
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Kruskal's Algorithm
The steps are:

1. The forest is constructed - with each node in a separate tree.

2. Sort the edges.
3. Until we've added n-1 edges,
3.1. Extract the next cheapest edge.
3.2. If it forms a cycle, reject it.
3.3. Else add it to the forest. Adding it to the forest will join
two trees together.

Every step will join two trees in the forest together, so that at the
end, there will only be one tree in T.
291
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph

B 4 C
4
2 1

A 4 E
1 F

D 2 3
10
G 5

5 6 3

4
I
H

2 3
J

292
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 A 4 B A 1 D

B 4 C B 4 D

B 4 C B 10 J C 2 E
4
2 1
C 1 F D 5 H
A 4 E
1 F

2 D 6 J E 2 G
D 3
10
G 5
F 3 G F 5 I
5 6 3

4
I G 3 I G 4 J
H

2 3
J H 2 J I 3 J

293
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Sort Edges A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

294
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

295
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

296
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

297
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

298
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

299
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Cycle
Don’t Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

300
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

301
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

302
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

303
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Cycle
Don’t Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

304
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Add Edge A 1 D C 1 F

C 2 E E 2 G

B 4 C H 2 J F 3 G
4
2 1
G 3 I I 3 J
A 4 E
1 F

2 A 4 B B 4 D
D 3
10
G 5
B 4 C G 4 J
5 6 3

4
I F 5 I D 5 H
H

2 3
J D 6 J B 10 J

305
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Minimum Spanning Tree Example Graph

B 4 C 4
B C
4 4
2 1 2 1
A E A 4
1 F E F
1

D 2 2
D 3
10
G G 5

3 5 6 3

4
I I
H H
2 3 3
J 2 J

306
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Analysis of Kruskal's Algorithm

The algorithm starts with sorting edges (O (E log E)).

We consider all E edges.

For each edge we check for possibility of cycle (O(logn))

Total running time is O(ElogE) + O (Elogn)

307
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Prim's Algorithm

• This algorithm starts with one node.

• It then, one by one, adds a node that is unconnected to the new
graph to the new graph.
• Each time selects the node whose connecting edge has the
smallest weight out of the available nodes’ connecting edges.

308
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Prim's Algorithm
The steps are:

1. The new graph is constructed - with one node from the old
graph.
2. While new graph has fewer than n nodes,
2.1. Find the node from the old graph with the smallest
connecting edge to the new graph,
2.2. Add it to the new graph 2 Complexity: O(n )
In every step one node is added, so that at the end we will have
one graph with all the nodes and it will be a minimum spanning
tree of the original graph.

309
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph

B 4 C
4
2 1

A 4 E
1 F

D 2 3
10
G 5

5 6 3

4
I
H

2 3
J

310
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

311
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

312
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

313
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

314
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

315
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

316
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

317
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

318
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

319
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph New Graph

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A 4
1 F E F
1

D 2 3 2
D 3
10 10
G 5 5
G
5 6 3 5 6 3
4 4
I I
H H
2 3 3
J 2 J

320
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Example Graph Minimum Spanning Tree

B 4 C 4
B C
4 4
2 1 2 1
A 4 E A
1 F E F
1

D 2 3 2
D
10
G 5
G
5 6 3 3
4
I I
H H
2 3 3
J 2 J

321
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 322
Bhaskar Sardar, Information Technology Department, Jadavpur University, India
 Any Doubt ?
• Please feel free to
write to me:

bhaskargit@[Link]

323
Bhaskar Sardar, Information Technology Department, Jadavpur University, India