MRCET-CSE

Divide and Conquer

General Method:

Divide and conquer is a design strategy which is well known to breaking down efficiency
barriers. When the method applies, it often leads to a large improvement in time complexity. For
example, from O (n2) to O (n log n) to sort the elements.

Divide and conquer strategy is as follows: divide the problem instance into two or more smaller
instances of the same problem, solve the smaller instances recursively, and assemble the
solutions to form a solution of the original instance. The recursion stops when an instance is
reached which is too small to divide. When dividing the instance, one can either use whatever
division comes most easily to hand or invest time in making the division carefully so that the
assembly is simplified.

Divide and conquer algorithm consists of two parts:

Divide : Divide the problem into a number of sub problems. The sub problemsare
solved recursively.
Conquer : The solution to the original problem is then formed from the solutionsto the
sub problems (patching together the answers).

Traditionally, routines in which the text contains at least two recursive calls are called divide and
conquer algorithms, while routines whose text contains only one recursive call are not. Divide–
and–conquer is a very powerful use of recursion.

Control Abstraction of Divide and Conquer

A control abstraction is a procedure whose flow of control is clear but whose primary
operations are specified by other procedures whose precise meanings are left undefined. The
control abstraction for divide and conquer technique is DANDC(P), where P is the problem to be
solved.

DANDC (P)
{
if SMALL (P) then return S (p);
else
{
divide p into smaller instances p1, p2, …. Pk
apply DANDC to each of these sub problems;
return (COMBINE (DANDC (p1) , DANDC (p2),…., DANDC (pk));
}
}

SMALL (P) is a Boolean valued function which determines whether the input size is small
enough so that the answer can be computed without splitting. If this is so function „S‟ is invoked
otherwise, the problem „p‟ into smaller sub problems. These sub problems p1, p2, . . . , pk are
solved by recursive application of DANDC.

DAA Digital Notes Page 15

 MRCET-CSE
If the sizes of the two sub problems are approximately equal then the computingtime of
DANDC is:

Where, T (n) is the time for DANDC on „n‟ inputs

g (n) is the time to complete the answer directly for small inputs andf (n) is
the time for Divide and Combine

Binary Search:

If we have „n‟ records which have been ordered by keys so that x 1 < x2 < … < xn .
When we are given a element „x‟, binary search is used to find the corresponding
element from the list. In case „x‟ is present, we have to determine a value „j‟ such
that a[j] = x (successful search). If „x‟ is not in the list then j is to set to zero (un
successful search).

In Binary search we jump into the middle of the file, where we find key a[mid], and
compare „x‟ with a[mid]. If x = a[mid] then the desired record has been
found. If x < a[mid] then „x‟ must be in that portion of the file that precedes a[mid],
if there at all. Similarly, if a[mid] > x, then further search is only necessary in
that past of the file which follows a[mid]. If we use recursive procedure of finding
the middle key a[mid] of the un-searched portion of a file, then every un-
successful comparison of „x‟ with a[mid] will eliminate roughly half the un-searched
portion from consideration.

Since the array size is roughly halved often each comparison between „x‟ and
a[mid], and since an array of length „n‟ can be halved only about log2n times before
reaching a trivial length, the worst case complexity of Binary search is about log2n

low and high are integer variables such that each time through the loop either
„x‟ is found or low is increased by at least one or high is decreased by at least one.
Thus we have two sequences of integers approaching each other and eventually low
will become greater than high causing termination in a finite number of steps if „x‟ is
not present.

DAA Digital Notes Page 16

 MRCET-CSE

DAA DIGITAL NOTES Page 17

 MRCET-CSE
Example for Binary Search

Let us illustrate binary search on the following 9 elements:

Index 1 2 3 4 5 6 7 8 9
Elements -15 -6 0 7 9 23 54 82 101

The number of comparisons required for searching different elements is as follows:

1. Searching for x = 101 low high mid

1 9 5
6 9 7
8 9 8
9 9 9
found

DAA DIGITAL NOTES Page 18

 MRCET-CSE

Number of comparisons = 4

2. Searching for x = 82 low high mid

1 9 5
6 9 7
8 9 8
found
Number of comparisons = 3

3. Searching for x = 42
low high mid5
1 9
6 9 7
6 6 6
7 6 Not found
Number of comparisons = 4

4. Searching for x = -14

low high mid5
1 9
1 4 2
1 1 1
2 1 Not found

Number of comparisons = 3
Continuing in this manner the number of element comparisons needed to find each of nine
elements is:

Index 1 2 3 4 5 6 7 8 9
Elements -15 -6 0 7 9 23 54 82 101
Comparisons 3 2 3 4 1 3 2 3 4

No element requires more than 4 comparisons to be found. Summing the comparisons

needed to find all nine items and dividing by 9, yielding 25/9 or approximately 2.77 comparisons
per successful search on the average.

There are ten possible ways that an un-successful search may terminate depending upon the
value of x.

If x < a[1], a[1] < x < a[2], a[2] < x < a[3], a[5] < x < a[6], a[6] < x < a[7] or
a[7] < x < a[8] the algorithm requires 3 element comparisons to determine that
„x‟ is not present. For all of the remaining possibilities BINSRCH requires 4 element
comparisons. Thus the average number of element comparisons for an unsuccessful
search is:

(3 + 3 + 3 + 4 + 4 + 3 + 3 + 3 + 4 + 4) / 10 = 34/10 = 3.4

DAA DIGITAL NOTES Page 19

 MRCET-CSE

The time complexity for a successful search is O(log n) and for an

unsuccessful search is Θ(log n).

Successful searches un-successful searches

Θ(1), Θ(log n), Θ(log n) Θ(log n)
Best average worst best, average and worst

Analysis for worst case

Let T (n) be the time complexity of Binary

searchThe algorithm sets mid to [n+1 / 2]

Therefore,
T(0) = 0
T(n) = 1 if x = a [mid]
= 1 + T([(n + 1) / 2] – 1) if x < a [mid]
= 1 + T(n – [(n + 1)/2]) if x > a [mid]

Let us restrict „n‟ to values of the form n = 2K – 1, where „k‟ is a non-negative

integer. The array always breaks symmetrically into two equal pieces plus middle
element.

-1 -1
2K – 1 2K – 1

2K 1
 n  1
Algebraically this is  2 K  1  1  = 2 K – 1 for K > 1
  
 2   2 
Giving,

T(0) = 0
T(2k – 1) = 1 if x = a [mid]
= 1 + T(2K - 1
– 1) if x < a [mid]
k - 1
= 1 + T(2 – 1) if x > a [mid]

In the worst case the test x = a[mid] always fails,
sow(0) = 0
w(2k – 1) = 1 + w(2k - 1
– 1)
This is now solved by repeated

substitution:w(2k – 1) = 1

+ w(2k - 1 – 1)

DAA DIGITAL NOTES Page 20

 MRCET-CSE
= 1 + [1 + w(2k - 2 –1)]
= 1 + [1 + [1 + w(2k - 3 –1)]]
= ........
= ........
= i + w(2k - i
– 1)

For i < k, letting i = k gives w(2k –1) = K + w(0) =

K
kBut as 2 – 1 = n, so K = log2(n + 1), so
w(n) = log2(n + 1) = O(log n)

for n = 2K–1, concludes this analysis of binary search.

Although it might seem that the restriction of values of „n‟ of the form 2 K–1 weakens
the result. In practice this does not matter very much, w(n) is a monotonic
increasing function of „n‟, and hence the formula given is a good approximation even
when „n‟ is not of the form 2K–1.

Merge Sort:

Merge sort algorithm is a classic example of divide and conquer. To sort an array,
recursively, sort its left and right halves separately and then merge them. The time
complexity of merge mort in the best case, worst case and average case is O(n log
n)and the number of comparisons used is nearly optimal.

This strategy is so simple, and so efficient but the problem here is that there
seemsto be no easy way to merge two adjacent sorted arrays together in place (The
result must be build up in a separate array).

The fundamental operation in this algorithm is merging two sorted lists. Because the
lists are sorted, this can be done in one pass through the input, if the output is put
in a third list.

Algorithm

Algorithm MERGESORT (low, high)

// a (low : high) is a global array to be sorted.
{
if (low < high)
{
mid := (low + high)/2 //finds where to split the
setMERGESORT(low, mid); //sort one subset
MERGESORT(mid+1, high); //sort the other subset
MERGE(low, mid, high); // combine the results
}
}

DAA DIGITAL NOTES Page 21

 MRCET-CSE
Algorithm MERGE (low, mid, high)
// a (low : high) is a global array containing two sorted subsets
// in a (low : mid) and in a (mid + 1 : high).
// The objective is to merge these sorted sets into single sorted
// set residing in a (low : high). An auxiliary array B is used.
{
h :=low; i := low; j:= mid + 1;
while ((h < mid) and (J < high)) do
{
if (a[h] < a[j]) then
{
b[i] := a[h]; h := h + 1;
}
else
{
b[i] :=a[j]; j := j + 1;
}
i := i + 1;
}
if (h > mid) then
for k := j to high do
{
b[i] := a[k]; i := i + 1;
}
else
for k := h to mid do
{
b[i] := a[K]; i := i + l;
}
for k := low to high do
a[k] := b[k];
}
Example

For example let us select the following 8 entries 7, 2, 9, 4, 3, 8, 6, 1 to

illustratemerge sort algorithm:

7, 2, 9, 4 | 3, 8, 6, 1  1, 2, 3, 4, 6, 7, 8, 9

7, 2 | 9, 4  2, 4, 7, 9 3, 8 | 6, 1  1, 3, 6, 8

7 | 2  2, 7 9 | 4  4, 9 3 | 8  3, 8 6 | 1  1, 6

7 7 2 2 9 9 4 4 3 3 8 8 6 6 1 1

DAA DIGITAL NOTES Page 22

 MRCET-CSE
Tree Calls of MERGESORT(1, 8)

The following figure represents the sequence of recursive calls that are produced by
MERGESORT when it is applied to 8 elements. The values in each node are the
valuesof the parameters low and high.

1, 8

1, 4 5, 8

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

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

Tree Calls of MERGE()

The tree representation of the calls to procedure MERGE by MERGESORT is

asfollows:

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

1, 2, 4 5, 6, 8

1, 4, 8

Analysis of Merge Sort

We will assume that „n‟ is a power of 2, so that we always split into even halves, so
we solve for the case n = 2k.

For n = 1, the time to merge sort is constant, which we will be denote by 1.

Otherwise, the time to merge sort „n‟ numbers is equal to the time to do two
recursive merge sorts of size n/2, plus the time to merge, which is linear. The
equation says this exactly:

T(1) = 1
T(n) = 2 T(n/2) + n

This is a standard recurrence relation, which can be solved several ways. We will
solve by substituting recurrence relation continually on the right–hand side.

We have, T(n) = 2T(n/2) + n

DAA DIGITAL NOTES Page 23

 MRCET-CSE
Since we can substitute n/2 into this main equation

2 T(n/2) = 2 (2 (T(n/4)) + n/2)

= 4 T(n/4) + n
We have,

T(n/2) = 2 T(n/4) + n
T(n) = 4 T(n/4) + 2n

Again, by substituting n/4 into the main equation, we see that

4T (n/4) = 4 (2T(n/8)) + n/4

= 8 T(n/8) + n
So we have,

T(n/4) = 2 T(n/8) + n
T(n) = 8 T(n/8) + 3n

Continuing in this manner, we obtain:

T(n) = 2k T(n/2k) + K. n

As n = 2k, K = log2n, substituting this in the above equation

= n T(1) + n log n
= n log n + n

Representing this in O

notation:

T(n) = O(n log n)

We have assumed that n = 2k. The analysis can be refined to handle cases
when „n‟is not a power of 2. The answer turns out to be almost identical.

Although merge sort‟s running time is O(n log n), it is hardly ever used for
main memory sorts. The main problem is that merging two sorted lists
requires linear extra memory and the additional work spent copying to the
temporary array and back, throughout the algorithm, has the effect of slowing
down the sort considerably. The Best and worst case time complexity of Merge
sort is O(n log n).

DAA DIGITAL NOTES Page 24

 MRCET-CSE

Strassen’s Matrix Multiplication:

The matrix multiplication of algorithm due to Strassens is the most dramatic

exampleof divide and conquer technique (1969).

The usual way to multiply two n x n matrices A and B, yielding result matrix „C‟ as
follows :

for i := 1 to n do
for j :=1 to n do
c[i, j] := 0;
for K: = 1 to n do
c[i, j] := c[i, j] + a[i, k] * b[k, j];

This algorithm requires n3 scalar multiplication‟s (i.e. multiplication

ofsinglenumbers) and n3 scalar additions. So we naturally cannot improve
upon.

We apply divide and conquer to this problem. For example let us considers
threemultiplication like this:

A A  B B 12  C 11 C 12 
11 12 11 
A 
A  B B C C
 21 22   21 22   21 22 

Then cij can be found by the usual matrix multiplication algorithm,

C11 = A11 . B11 + A12 . B21

C12 = A11 . B12 + A12 . B22
C21 = A21 . B11 + A22 . B21
C22 = A21 . B12 + A22 . B22

This leads to a divide–and–conquer algorithm, which performs nxn matrix

multiplication by partitioning the matrices into quarters and performing eight
(n/2)x(n/2) matrix multiplications and four (n/2)x(n/2) matrix additions.

T(1) = 1
T(n) = 8 T(n/2)

Which leads to T (n) = O (n3), where n is the power of 2.

Strassens insight was to find an alternative method for calculating the C ij, requiring
seven (n/2) x (n/2) matrix multiplications and eighteen (n/2) x (n/2) matrix
additions and subtractions:

P = (A11 + A22) (B11 + B22)

Q = (A21 + A22) B11

DAA DIGITAL NOTES Page 25

 MRCET-CSE
R = A11 (B12 – B22) S = A22

(B21 - B11) T = (A11 + A12) B22

U = (A21 – A11) (B11 + B12)

V = (A12 – A22) (B21 + B22)

C11 = P + S – T + V

C12 = R + T

C21 = Q + S

C22 = P + R - Q + U.

This method is used recursively to perform the seven (n/2) x (n/2) matrix
multiplications, then the recurrence equation for the number of scalar
multiplications performed is:

T(1) = 1
T(n) = 7 T(n/2)

Solving this for the case of n = 2k is easy:

T(2k) = 7 T(2k–1)

= 72 T(2k-2)

= ------
= ------

= 7i T(2k–i)

Put i = k
= 7k T(1)

= 7k
n
That is, T(n) = 7 log

= n log 7

log 7
= O(n 2 ) = O(2n.81)

DAA DIGITAL NOTES Page 26

 MRCET-CSE

So, concluding that Strassen‟s algorithm is asymptotically more efficient than the
standard algorithm. In practice, the overhead of managing the many small matrices
does not pay off until „n‟ revolves the hundreds.

Quick Sort

The main reason for the slowness of Algorithms like SIS is that all comparisons and
exchanges between keys in a sequence w1, w2, . . . . , wn take place between
adjacent pairs. In this way it takes a relatively long time for a key that is badly out
ofplace to work its way into its proper position in the sorted sequence.

Hoare his devised a very efficient way of implementing this idea in the early
1960‟s that improves the O(n2) behavior of SIS algorithm with an expected
performance that is O(n log n).

In essence, the quick sort algorithm partitions the original array by rearranging it
into two groups. The first group contains those elements less than some arbitrary
chosen value taken from the set, and the second group contains those elements
greater than or equal to the chosen value.

The chosen value is known as the pivot element. Once the array has been
rearranged in this way with respect to the pivot, the very same partitioning is
recursively applied to each of the two subsets. When all the subsets have been
partitioned and rearranged, the original array is sorted.

The function partition() makes use of two pointers „i‟ and „j‟ which are moved
toward each other in the following fashion:

 Repeatedly increase the pointer „i‟ until a[i] >= pivot.

 Repeatedly decrease the pointer „j‟ until a[j] <= pivot.

DAA DIGITAL NOTES Page 27

 MRCET-CSE
 If j > i, interchange a[j] with a[i]

 Repeat the steps 1, 2 and 3 till the „i‟ pointer crosses the „j‟ pointer. If „i‟
pointer crosses „j‟ pointer, the position for pivot is found and place pivot
element in „j‟ pointer position.

The program uses a recursive function quicksort(). The algorithm of quick

sortfunction sorts all elements in an array „a‟ between positions „low‟ and
„high‟.

 It terminates when the condition low >= high is satisfied. This

conditionwill be satisfied only when the array is completely sorted.

 Here we choose the first element as the „pivot‟. So, pivot = x[low]. Now
it calls the partition function to find the proper position j of the element
x[low] i.e. pivot. Then we will have two sub-arrays x[low], x[low+1], . . .
.
. . . x[j-1] and x[j+1], x[j+2], x[high].

 It calls itself recursively to sort the left sub-array x[low], x[low+1], . . . . .

. . x[j-1] between positions low and j-1 (where j is returned by
thepartition function).

 It calls itself recursively to sort the right sub-array x[j+1], x[j+2], . . . . . .

. . . x[high] between positions j+1 and high.

DAA DIGITAL NOTES Page 28

 MRCET-CSE

Example

Select first element as the pivot element. Move „i‟ pointer from left to right in search
of an element larger than pivot. Move the „j‟ pointer from right to left in search of an
element smaller than pivot. If such elements are found, the elements are swapped.
This process continues till the „i‟ pointer crosses the „j‟ pointer. If „i‟ pointer crosses
„j‟ pointer, the position for pivot is found and interchange pivot and element at „j‟
position.

DAA DIGITAL NOTES Page 29

 MRCET-CSE
Let us consider the following example with 13 elements to analyze quick sort:

1 2 3 4 5 6 7 8 9 10 11 12 13 Remarks

38 08 16 06 79 57 24 56 02 58 04 70 45
pivot i j swap i & j
04 79
i j swap i & j
02 57
j i
swap pivot
(24 08 16 06 04 02) 38 (56 57 58 79 70 45) &j
swap pivot
pivot j, i
&j
(02 08 16 06 04) 24
pivot, swap pivot
i
j &j
02 (08 16 06 04)
pivot i j swap i & j
04 16
j i
swap pivot
(06 04) 08 (16)
&j
pivot,
j i
swap pivot
(04) 06
&j
04
pivot,
j, i
16
pivot,
j, i
(02 04 06 08 16 24) 38
(56 57 58 79 70 45)
pivot i j swap i & j
45 57
j i
swap pivot
(45) 56 (58 79 70 57)
&j
45
pivot, swap pivot
j, i &j
(58 79 57)
pivot i 70 j swap i & j

57 79
j i

DAA DIGITAL NOTES Page 30

 MRCET-CSE
swap pivot
(57) 58 (70 79)
&j
57
pivot,
j, i
(70 79)
pivot, swap pivot
i
j &j
70
79
pivot,
j, i
(45 56 57 58 70 79)
02 04 06 08 16 24 38 45 56 57 58 70 79

DAA DIGITAL NOTES Page 31

 MRCET-CSE
Analysis of Quick Sort:

Like merge sort, quick sort is recursive, and hence its analysis requires solving a
recurrence formula. We will do the analysis for a quick sort, assuming a random
pivot(and no cut off for small files).

We will take T (0) = T (1) = 1, as in merge sort.

The running time of quick sort is equal to the running time of the two recursive calls
plus the linear time spent in the partition (The pivot selection takes only constant
time). This gives the basic quick sort relation:

T (n) = T (i) + T (n – i – 1) + C n - (1)

Where, i = |S1| is the number of elements in S1.

Worst Case Analysis

The pivot is the smallest element, all the time. Then i=0 and if we ignore T(0)=1,
which is insignificant, the recurrence is:

T (n) = T (n – 1) + C n n > 1 - (2)

Using equation – (1) repeatedly, thus

T (n – 1) = T (n – 2) + C (n – 1)

T (n – 2) = T (n – 3) + C (n – 2)

------- -

T (2) = T (1) + C (2)

Adding up all these equations yields

= O (n2) - (3)

DAA DIGITAL NOTES Page 32

 MRCET-CSE
Best and Average Case Analysis

The number of comparisons for first call on partition: Assume left_to_right

moves over k smaller element and thus k comparisons. So when right_to_left
crosses left_to_right it has made n-k+1 comparisons. So, first call on partition
makes n+1 comparisons. The average case complexity of quicksort is

T(n) = comparisons for first call on quicksort

+
{Σ 1<=nleft,nright<=n [T(nleft) + T(nright)]}n = (n+1) + 2 [T(0) +T(1) + T(2) +
----- + T(n-1)]/n

nT(n) = n(n+1) + 2 [T(0) +T(1) + T(2) + ----- + T(n-2) + T(n-1)]

(n-1)T(n-1) = (n-1)n + 2 [T(0) +T(1) + T(2) +------ + T(n-2)] \

Subtracting both sides:

nT(n) –(n-1)T(n-1) = [ n(n+1) – (n-1)n] + 2T(n-1) = 2n + 2T(n-

1)nT(n) = 2n + (n-1)T(n-1) + 2T(n-1) = 2n + (n+1)T(n-1)
T(n) = 2 + (n+1)T(n-1)/n
The recurrence relation obtained is:
T(n)/(n+1) = 2/(n+1) + T(n-1)/n

Using the method of subsititution:

T(n)/(n+1) = 2/(n+1) + T(n-1)/n

T(n-1)/n = 2/n + T(n-2)/(n-1)
T(n-2)/(n-1) = 2/(n-1) + T(n-3)/(n-2)
T(n-3)/(n-2) = 2/(n-2) + T(n-4)/(n-3)
. .
. .
T(3)/4 = 2/4 + T(2)/3
T(2)/3 = 2/3 + T(1)/2 T(1)/2 = 2/2 + T(0)
Adding both sides:
T(n)/(n+1) + [T(n-1)/n + T(n-2)/(n-1) + --------------+ T(2)/3 + T(1)/2]
= [T(n-1)/n + T(n-2)/(n-1) + -------------- + T(2)/3 + T(1)/2] + T(0) +
[2/(n+1) + 2/n + 2/(n-1) + ----------- +2/4 + 2/3]
Cancelling the common terms:
T(n)/(n+1) = 2[1/2 +1/3 +1/4+ --------------- +1/n+1/(n+1)]

T(n) = (n+1)2[  2k n 1

1/ k
=2(n+1) [ ]
=2(n+1)[log (n+1) – log 2]
=2n log (n+1) + log (n+1)-2n log 2 –log 2
T(n)= O(n log n)

DAA DIGITAL NOTES Page 33

 UNIT 3 GRAPH ALGORITHMS
Structure Page Nos.

3.0 Introduction 82
3.1 Objectives 82
3.2 Basic Definition and Terminologies 83
3.3 Graph Representation 85
3.3.1 Adjacency Matrix
3.3.2 Adjacency List
3.4 Graph Traversal Algorithms 87
3.4.1 Depth First Search
3.4.2 Breadth First Search
3.5 Summary 98
3.6 Solutions/Answers 98
3.7 Further Readings 100

3.0 INTRODUCTION

The vast majority of computer algorithm operate on data. Organsing these data in a
certain way (i.e. data structure) has a significant role is design and analysis of
algorithm. Graph is one such fundamental data structure. Array, linked list, stack,
queue, tree, sets are other important data structures. A graph is generally used to
represent connectivity information i.e. connectivity between cities for example.
Graphs have been used and considered very interesting data structures with a large
number of applications for example the shortest path problem. While several
representations of a graph are possible, we discuss in the unit the two most common
representations of a graph: adjacency matrix and adjacency list. Many graph
algorithms requires visiting nodes and vertices of a graph. This kind of operation is
also called traversal. You must have read various traversal methods for tree such as
preorder, postorder and inorder In this unit we present two graph traversal algorithms
which are called as Depth first search and Breadth first search algorithm.

3.1 OBJECTIVES

After going through this unit you will be able to

define a graph,

differentiate between an undirected and a directed graph,

represent a graph though a adjacency matrix and an adjacency list and;

traverse a graph using DFS and BFS.

82
 Graph Algorithms
3.2 BASIC DEFINITION AND TERMINOLOGIES

A graph G = (V. E) is a set of vertices V, with edges connecting some of the vertices
(edge set E). An edge between vertex u and v is denoted as (u, v). There are two types
of a graph: (1) undirected a graph and directed graph (digraph). In a undirected graph
the edges have no direction whereas in a digraph all edges have direction.

You can notice that edges have no direction. Let us have an example of an undirected
graph (figure 1) and a directed graph (figure 2)

1 3 4

2 5

Figure.1 Undirected graph

V = {0, 1, 2, 3, 4, 5}

E = {(0, 1) , (0, 2),

(1,2), or (2, 2) both are same

(2, 3),

(3, 4), (3, 5)

(4, 5)

1 3 4

2 5

Figure 2: Diagraph

V = {0, 1, 2, 3, 4, 5, }

E = { (0, 1),

(1, 2)

(2, 0), (2, 3),

83
Design Techniques (3, 4), (3, 5)

(4, 5) and (5, 4) are not the same. These are two different edges.

(5, 4)

You can notice in Figure 2 that edges have direction

You should also consider the following graph preparations.

The geometry of drawing has no particular meaning: edges of a graph can be drawn
“straight” or “curved”.

A vertex v is adjacent to vertex u, if there is an edge (u, v). In an undirected graph,

existence of edge (u, v) means both u and v are adjacent to each other. In a digraph,
existence of edge (u, v) does not mean u is adjacent to v.

PATH

An edge may not have a weight. A path in a graph is sequence of vertices V1 V2….Vn
such that consecutive vertices Vi Vi + 1 have an edge between them, i.e., Vi + 1 is
adjacent to Vi

A path in a graph is simple if all vertices are distinct i.e. no repetition of a path of any
vertices (and therefore edges) in the sequence, except possibly the first and the last
one. Length of a path is the number of edges in the path. A cycle is a path of length at
least 1 such that the first and the last vertices are equal. A cycle is a simple path with
the same vertex as the first and the last vertex in the sequence if the path is simple. For
undirected graph, we require a cycle to have distinct edges. Length of a cycle is the
number of edges in the cycle.

There are many problems in computer science such as of route with minimum time
and diagnostic: minimum shortcut path routing, traveling sales problem etc. can be
designed using paths obtained by marking traversal along the edges of a graph.

CONNECTED GRAPHS

Connectivity: A graph is connected if there is a path from every vertex to every other
vertex. In an undirected graph, if there is a path between every pair of distinct vertices
of the graph, then the undirected graph is connected. The following example
illustrates this:

a b

a c

b c
d e

f
G1 G2
d e

(a) Connected (b) Unconnected

Figure 3: The connected and unconnected undirected graph

84
In the above example G, there is a path between every pair of distinct vertices of the Graph Algorithms
graph, therefore G1 is connected. However the graph G2 is not connected.

In directed graph, two vertices are strongly connected if there is a (directed) path
from one to the other.

Undirected: Two vertices are connected if there is a path that includes them.

Directed: Two vertices are strongly-connected if there is a (directed) path from any
vertex to any other.

3.3 GRAPH REPRESENTATION

In this section, we will study the two more important data structure for graph
representation: Adjacency matrix and Adjacency list.

3.3.1 ADJACENCY MATRIX

The adjacency matrix of a graph G = {V, E} with n vertices is a n x n boolean/matrix.

In this matrix the entry in the ith row and jth column is 1 if there is an edge from the
ith vertex to the jth vertex in the graph G. If there is no such edge, then the entry will
be zero. It is to be noted that
(i) the adjacency matrix of a undirected graph is always symmetric, i.e., M [i,j] = M [j,
i]

(ii) The adjacency matrix for a directed graph need not be symmetric.

(iii) The memory requirement of an adjacency matrix is n2 bits

For example for the graph in the following figure (a) is adjacency matrix is given in
(b)

1 4 5

2 3

Figure. 4 (a)

1 2 3 4 5
1 0 1 0 1 0

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

Figure.4 (b) Adjacency Matrix

85
Design Techniques Let us answer the following questions:

(i) Suppose if we want to know how much time will take in finding number of edges a
graph with n vertices?

Since the space needed to represent a graph is n2 bits where n is a number of vertices.
All algorithm will require at least 0 (n2) time because n2 – n entries of the matrix have
to be examined. Diagonal entries are zero.

(ii) Suppose the most of the entries in the adjacency matrix are zeros, i.e., when a
graph is a sparse... How much time is needed to the find m number of edges in a
graph? It will take much less time if say 0 (e + n), where e is the number of edges is a
graph and e << n2/2. But this can be achieved if a graph is represented through an
adjacency list where only the edges will be represented.

3.3.2 ADJACENCY LIST

The adjacency list of a graph or a diagraph is a set of linked lists, one linked list for
each vertex. The nodes in the linked list i contain all the vertices that are adjacent to
vertex i of the list (i.e. all the vertices connected to it by an edge). The following
figure.5 represents adjacency list of the graph in figure 4 (a).

Vertex 1 2 4
Vertex 2
1 3
0
Vertex 3
2 4 5
Vertex 4
Vertex 5 1 3 5

4 3

Figure. 5 Adjacency List

Putting it in another way of an adjacency list represents only columns of the adjacency
matrix for a given vertex that contains entries as 1’s. It is to be observed that
adjacency list compared to adjacency matrix consumes less memory space if a graph
is sparse. A graph with few edges is called sparse graph. If the graph is dense, the
situation is reverse. A dense graph, is a graph will relatively few missing edges. In
case of an undirected graph with n vertices and e edge adjacency list requires n head
and 2 e list nodes (i.e. each edges is represented twice).

What is the storage requirement (in terms of bits) for a adjacency list of any graph!
(i) For storing n (n vertices) head nodes – we require – log2 n bits –
(ii) For storing list nodes for each head n nodes – we require log n + log e

Therefore total storage requirement in item of bits for adjacency matrix is 2log2n
(2log2n + log2e)

Question. What is time complexity in determining number of edges in an undirected

graph.

It may be done in just 0 (n + e) because in degree of any vertex (i.e. number of edges
incident to that vertex) in an undirected graph may be determined by just counting the
number of nodes in its adjacency list.

86
Use of adjacency matrix or adjacency list for representing your graph – depends upon Graph Algorithms
the type of a problem; type of algorithm to be used for solving a problem and types of
a input graph (dense or sparse)

3.4 GRAPH TRAVERSAL ALGORITHMS

3.4.1 DEPTH-FIRST SEARCH

You are aware of tree traversal mechanism. Give a tree, you can traverse it using
preorder, inorder and postorder. Similarly given an undirected graph you can traverse
it or visit its nodes using breadth first-search and depth-first search.

Searching in breadth-first search or depth first search means exploring a given graph.
Through searching a graph one can find out whether a graph is connected or not?
There are many more applications of graph searching algorithms. In this section we
will illustrate Depth First Search algorithm followed by Breadth first Search algorithm
in the next section.

The logic behind this algorithm is to go as far as possible from the given starting node
searching for the target. In case, we get a node that has no adjacent/successor node,
we get back (recursively) and continue with the last vertex that is still not visited.

Broadly it is divided into 3 steps:

 Take a vertex that is not visited yet and mark it visited

 Go to its first adjacent non-visited (successor) vertex and mark it visited
 If all the adjacent vertices (successors) of the considered vertex are
already visited or it doesn’t have any more adjacent vertex (successor) –
go back to its parent vertex

Before starting with an algorithm, let us discuss the terminology and structure used in
the algorithm. The following algorithm works for undirected graph and directed graph
both.

The following color scheme is to maintain the status of vertex i.e mark a vertex is
visited or unvisited or target vertex:

white- for an undiscovered/unvisited vertex

gray - for a discovered/visited vertex
black - for a finished/target vertex
The structure given below is used in the algorithm.
p[u]- Predecessor or parent node.
Two (2) timestamps referred as
t[u] – First time discovering/visiting a vertex, store a counter or number of times
f[u]= finish off / target vertex

Let us write the algorithm DFS for any given graph G. In graph G, V is the vertex set
and E is the set of edges written as G(V,E). Adjacency list for the given graph G is
stored in Adj array as described in the previous section.

color[] - An array color will have status of vertex as white or gray or black as defined
earlier in this section.
87
Design Techniques DFS(G)
{
for each v in V, //for loop V+1 times
{
color[v]=white; // V times
p[v]=NULL; // V times
}
time=0; // constant time O(1)
for each u in V, //for loop V+1 times
if (color[u]==white) // V times
DFSVISIT(u) // call to DFSVISIT(v) , at most V times O(V)

DFSVISIT(u)
{
color[u]=gray; // constant time
t[u] = ++time;
for each v in Adj(u) // for loop
if (color[v] == white)
{
p[v] = u;
DFSVISIT(v); // call to DFSVISIT(v)
}
color[u] = black; // constant time
f[u]=++time; // constant time
}
Complexity analysis

In the above algorithm, there is only one DFSVISIT(u) call for each vertex u in the
vertex set V. Initialization complexity in DFS(G) for loop is O(V). In second for loop
of DFS(G) , complexity is O(V) if we leave the call of DFSVISIT(u).
Now, Let us find the complexity of function DFSVISIT(u)
The complexity of for loop will be O(deg(u)+1) if we do not consider the recursive
call to DFSVISIT(v). For recursive call to DFSVISIT(v), (complexity will be O(E) as
Recursive call to DFSVISIT(v) will be at most the sum of degree of adjacency for all
vertex v in the vertex set V. It can be written as |Adj(v)|=O(E) v V
Hence, overall complexity for DFS algorithm is O(V + E)

88
The strategy of the DFS is to search “deeper” in the graph whenever possible. Graph Algorithms
Exploration of vertex is in the fashion that first it goes deeper then widened.
Let us take up an example to see how exploration of vertex takes place by Depth First
Search algorithm.

Adjacency list of the above graph is as below:

Let us explore the vertices of the graph using DFS algorithm.

89
Design Techniques

90
 Graph Algorithms

Now each vertex of the given graph is visited/explored by DFS algorithm and DFS
tree is as follows:

91
Design Techniques

Data structure used for implementing DFS algorithm is stack. In the diagram along
with each vertex start and finish time is written in the format a/b here a represent start
time and b represent finish time. This will result in to tree or forest. The order of
vertices explored by DFS algorithm according to adjacency list considered for given
graph is 1,2,3,4,5.

3.4.2 BREADTH-FIRST SEARCH

In this section, we will discuss breadth first search algorithm for graph. This is very
well known searching algorithm. A traversal depends both on the starting vertex, and
on the order of traversing the adjacent vertices of each node. The analogy behind
breadth first search is that it explores the graph wider then deeper. The method starts
with a vertex v then visit all its adjacent nodes v1,v2,v3…then move to the next node
which is adjacent to v1, v2, v3 …. This also referred as level by level search.

Basic steps towards exploring a graph using breadth-first search:

Mark all vertices as "unvisited".

Start with start vertex v
Find an unvisited vertex that are adjacent to v , mark them visited
Next consider all recently visited vertices and visit unvisited vertices adjacent
to them
Continue this process till all vertices in the graph are explored /visited

Now, let us see the structure used in this algorithm and color scheme for status of
vertex.

Color scheme is same as used in DFS algorithm i.e to maintain the status of vertex i.e
mark a vertex is visited or unvisited or target vertex:

white- for an undiscovered/unvisited vertex

gray - for a discovered/visited vertex

black - for a finished/target vertex

The structure given below is used in the algorithm. G will be the graph as G(V,E) with
set of vertex V and set of edges E.

p[v]-The parent or predecessor of vertex

d[v]-the number of edges on the path from s to v.

Data structure used for breadth-first search is queue, Q (FIFO), to store gray vertices.

color[v]- This array will keep the status of vertex as white, grey or black

92
The following algorithm for BFS takes input graph G(V,E) where V is set of vertex Graph Algorithms
and E is the set of edges. Graph is represented by adjacency list i.e Adj[]. Start vertex
is s in V.

Line BFS(G,s)
No. {
1. for each v in V - {s} // for loop
{
2. color[v]=white;
3. d[v]= INFINITY;
4. p[v]=NULL;
}
5. color[s] = gray;
6. d[s]=0;
7. p[s]=NULL;
8. Q= ; // Initialize queue is empty
9. Enqueue(Q,s); /* Insert start vertex s in Queue Q */
10. while Q is nonempty // while loop
{
11. u = Dequeue[Q]; /* Remove an element from Queue Q*/

12. for each v in Adj[u] // for loop

{
13. if (color[v] == white) /*if v is unvisted*/
{
14. color[v] = gray; /* v is visted */
15. d[v] = d[u] + 1; /*Set distance of v to no. of edges
from s to u*/
16. p[v] = u; /*Set parent of v*/
17. Enqueue(Q,v); /*Insert v in Queue Q*/
}
}
18. color[u] = black; /*finally visted or explored vertex
u*/
}
}
Complexity Analysis

93
Design Techniques In this algorithm first for loop executes at most O(V) times.

While loop executes at most O(V) times as every vertex v in V is enqueued only once
in the Queue Q. Every vertex is enqueued once and dequeued once so queuing will
take at most O(V) time.

Inside while loop, there is for loop which will execute at most O(E) times as it will be
at most the sum of degree of adjacency for all vertex v in the vertex set V.

Which can be written as |Adj(v)|=O(E)

v V

Let us summarize the number of times a statement will execute in the algorithm for
BFS.

Line no. No. of times statement will Cost

execute

1 V O(V)

2 V-1

3 V-1

4 V-1 O(1)

5 1

6 1

7 1

8 1

9 1

10 V+1 O(V)

11 V

12 V+E+1 O(V+E)

13 V+E

14 V

15 V

16 V

17 V

18 V

Thus overall complexity of BFS will be V + V + E, i.e. O(V+E)

94
Let us take up an example to see how exploration of vertex takes place by Breadth Graph Algorithms
First Search algorithm.

The adjacency list of the above graph is as below:

Let us explore vertices of the graph by BFS algorithm.

Consider initial vertex as vertex 1.

Initial status of the Queue is Q = Ø

95
Design Techniques

96
 Graph Algorithms

Q = Ø

After exploring the vertex of given graph by BFS algorithm, BFS traversal sequence
is

1, 2, 3, 4, 5

In this algorithm sequence of vertex visited or explored may vary. The final sequence
of vertex visited is dependent on adjacency list. But the array d[] will have same
number irrespective of order of vertices in adjacency list. In the above diagram
distance is shown along the vertex. According to adjacency list drawn in the diagram,
exploration sequence of vertex by BFS algorithm is 1,2,3,4,5.

 Check Your Progress 1

1. What is the complexity of graph search algorithms if graph is represented by
adjacency matrix and adjacency list?
2. Enlist few applications where DFS and BFS can be used?

97
Design Techniques 3. Consider a graph with 5 vertices and 6 edges. Write its adjacency matrix and
adjacency list.
V1

V3
V2

V4 V5

4. For the following graph write DFS and BFS traversal sequence.

C
B

D G
E F

3.5 SUMMARY

A graph G(V,E) where V is the finite set of vertices i.e { v1,v2,v3….} and E is the
finite set of edges {(u,v),(w,x)….}. Graph is known as directed graph if the each edge
in the graph has ordered pair of vertices i.e (u,v) means an edge from u to v. In
Undirected graph each edge is unordered pair of vertices i.e (u,v) and (v,u) refers to
the same edge. A graph can be represented by adjacency matrix and adjacency list. In
adjacency, list memory requirement is more as compared to adjacency list
representation. Graph searching problem has wide range of applications. Breadth First
search and Depth first search are very well known searching algorithms. In breadth
first search, exploration of vertex is wider first then deeper. In depth first search it is
deeper first and then it is widened. By exploration of vertex in any search algorithm,
implies visiting or traversing each vertex in the graph. Data structure used for Breadth
first search is queue and depth first search is stack. By using these search algorithms,
connected components of graph can be found. Breadth first search method, gives
shortest path between two vertices u and v. Depth first search is used in topological
sorting. There are many more applications where these searching algorithms are used.

3.6 SOLUTIONS/ANSWERS

Check Your Progress 1

1. For BFS algorithm complexity will be as follows:

Adjacency Matrix – O(V2)
Adjacency List – O(V+E)

98
 For DFS algorithm complexity is as follows: Graph Algorithms
Adjacency Matrix – O(V2)
Adjacency List – O(V+E)

2. Application where DFS can be used:

 Finding connected component of the graph
 Finding shortest path between two vertices
Application where BFS can be used:

 Finding connected component of the graph

 Topological sorting
 For finding cycle existence in the graph or not
3.

Adjacency Matrix

V1 V2 V3 V4 V5

V1 0 1 1 0 0

V2 1 0 1 1 0

V3 1 1 0 0 1

V4 0 1 0 0 1

V5 0 0 1 1 0

Adjacency List

V1
V2 V3

V2
V1 V3 V4

V3
V1 V2 V5

V4
V2 V5

V5
V3 V4

99
Design Techniques 4. For the given graph

C
B

D G
E F

BFS traversal sequence is ABCDEFG

DFS traversal sequence is ABDECFG

3.7 FURTHER READINGS

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein, “Introduction to

Algorithms”, 2 nd Ed., PHI, 2004.
2. Robert Sedgewick, “Algorithms in C”, , Pearson Education, 3rd Edition 2004
3. Ellis Horowitz, Sartaj Sahani, Sanguthevar Rajasekaran, “Fundamentals of
Computer algorithms”, 2nd Edition, Universities Press, 2008
4. Anany Levitin, “Introduction to the Design and Analysis of Algorithm”, Pearson
Education, 2003.

100
 SCS1201 Advanced Data Structures Unit IV
UNIT 4 ADVANCED GRAPH CONCEPTS

MINIMUM SPANNING TREES

Weight of an edge: Weight of an edge is just of the value of the edge or the cost of the edge.
For example, a graph representing cities, has the distance between two cites as the edge cost or
its weight.
Network: A graph with weighted edges is called a network.
Spanning Tree: Any tree consisting of edges in the graph G and including all vertices in G is
called a spanning tree.
Given a network, we should try to connect all the nodes in the nodes in the graph with
minimum number of edges, such that the total weight is minimized. To solve this problem, we
shall devise an algorithm that converts a network into to tree structures called the minimum
spanning tree of the network.
Given a network, the edges for the minimum spanning tree are chosen in such a way that:
(1) Every node in the network must be included in the spanning tree.
(2) The overall edge weight of the spanning tree is the minimum possible that will allow
the existence of a path between any 2 nodes in the tree.
The two algorithms which are used for finding the minimum spanning tree for a graph are:
1. Kruskal’s Algorithm
2. Prim’s Algorithm
3. Sollin’s Algorithm
KRUSKAL’S ALGORITHM

The Kruskal’s algorithm follows greedy approach. At every stage of the solution, it takes
that edge which has the minimum cost and builds the minimum spanning tree.
Example:

Consider the above graph. Now let us apply the Kruskal’s

algorithm to construct a minimum spanning tree.
Step 1:
Construct a queue with the cost of edges, such that the edges are placed in the queue in
the ascending order of the cost as shown.
Queue of edge costs
10 12 14 16 18 22 24 26 28
Step 2:
Create N sets each consisting one node. N is the number of nodes in the graph. Then for
the above problem, the sets which will be created are
S1 = {1}
S2 = {2}
S3 = {3}
S4 = {4}
S5 = {5}
S6 = {6}
S7 = {7}
Step 3:
Delete a cost from the queue. Let the nodes associated with that edge be (u,v). Now, 10
is deleted first from the queue. The nodes associated with 10 is (u,v) = (1,6). Check if u and v
belong to the same set or different set. If they belong to the different set then enter that into the
output matrix as shown. Since 1 belongs to S1 and 6 belong to S6, they can be entered into the T
matrix. If the nodes belong to the same set, then entering them into the matrix will give an
output which may form a cycle. Hence that is avoided. The T matrix has n-1 rows and 2
columns.
T matrix
u v
1 1 6
2
3
4
5
6

After entering them in the T matrix, the sets S1 and S6 are merged.
S8 = {1, 6}

The above process in step 3 is repeated till the queue becomes empty. The solution is derived as
shown.
Queue of edge costs
 12 14 16 18 22 24 26 28
Delete 12 from the queue. The nodes associated with 12 are (u,v) = (3,4). The node 3
belongs to S3 and node 4 belongs to S4. As they are in different sets, they are entered in the T
matrix.
T matrix
u v
1 1 6
2 3 4
3
4
5
6
The sets S3 and S4 are merged.
S9 = {3, 4}
Queue of edge costs

14 16 18 22 24 26 28
Delete 14 from the queue. The (u,v) = (2,7). 2 belong to S2 and 7 belong to S7. As they belong
to different sets, they are entered into the T matrix and the sets S2 and S7 are merged.
T matrix
u v
1 1 6
2 3 4
3 2 7
4
5
6
S10 = {2, 7}
Queue of edge costs
16 18 22 24 26 28

Delete 16 from the queue. The (u,v) = (2,3). 2 belong to S10 and 3 belong to S9. As they are
from different sets, they are entered into the T matrix. The sets S9 and S10 are merged.
T matrix
u v
1 1 6
2 3 4
3 2 7
4 2 3
5
6
S11 = {2, 3, 4, 7}
Queue of edge costs
18 22 24 26 28
Delete 18. The (u, v) = (4, 7). 4 and 7 belong to same set S11. Hence they are not entered into
the T matrix.
Queue of edge costs
22 24 26 28
Delete 22. The (u,v) = (4, 5). 4 belong to S11 and 5 belong to S5. As they belong to different
set, they are entered into the T matrix. The sets S11 and S5 are merged.
T matrix
u v
1 1 6
2 3 4
3 2 7
4 2 3
5 4 5
6
S12 = {2, 3, 4, 5, 7}
Queue of edge costs
24 26 28
Delete 24. (u, v) = (5, 7). Both 5 and 7 belong to S12. Hence they are not entered into the T
matrix.
26 28
Delete 26. (u, v) = (5, 6). 5 belong to S12 and 6 belong to S8. As they are from different set,
they are entered into the T matrix.

T matrix
u v
1 1 6
2 3 4
3 2 7
4 2 3
5 4 5
6 5 6
S13 = {1, 2, 3, 4, 5, 6, 7}
As all T matrix is completely filled, the algorithm comes to an end.
Step 4:
Using the edges in the T matrix connect the nodes of the graph. The resulting tree is the
required minimum spanning tree.

Algorithm
KRUSKAL(E, cost, n, t)
Construct a queue with edge costs such that they are in ascending order
i = 0, mincost = 0
while i < n – 1 and queue is not empty
Delete minimum cost edge (u, v) from queue
j = Find(u), k = Find(v)
If j ≠ k
i=i+1
t[i, 1] = u, t[i, 2] = v
mincost = mincost + cost[u, v]
Union(j, k)
End if
End while
If i ≠ n – 1
Print “No spanning tree”
Else
Return mincost
End if
End KRUSKAL

PRIM’S ALGORITHM
The other popular algorithm used for constructing the minimum spanning tree is the
Prim’s algorithm, which also follows the greedy approach. We can consider the same example
as above and solve it using Prim’s algorithm.
Example:

Cost Matrix is
1 2 3 4 5 6 7
1 0 28 ∞ ∞ ∞ 10 ∞
2 28 0 16 ∞ ∞ ∞ 14
3 ∞ 16 0 12 ∞ ∞ ∞
4 ∞ ∞ 12 0 22 ∞ 18
5 ∞ ∞ ∞ 22 0 26 24
6 10 26 ∞ ∞ ∞ 0 ∞
7 ∞ 14 ∞ 18 24 ∞ 0

Step 1:
Select the least cost edge from the graph and enter into the T matrix. The least cost edge
is (1, 6) with cost 10.
T matrix
u v
1 1 6
2
3
4
5
6
Let us consider an array NEAR[ ], which is filled as follows:
If cost[i, l] < cost[i, k]
Near[i] = l
Else
Near[i] = k

In the first iteration i = 1 and (k, l) = (1, 6). Using the above condition the NEAR array is filled
as follows.
NEAR

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

Step 2:
 Make the entries in the NEAR array corresponding to 1 and 6 as 0. For all non-zero
entries in the near array, find out the cost[j][near[j]]. Select the minimum among these costs and
enter the corresponding nodes into the T matrix.
NEAR

1 0
2 1 28
3 1 ∞
4 1 ∞
5 6 26
6 0
7 1 ∞
Among the costs, 26 is minimum. Hence (5, 6) is entered into the T matrix. The corresponding
entry into the NEAR array is made 0.
T matrix
u v
1 1 6
2 5 6
3
4
5
6

Step 3:
Now in every iteration the NEAR array is updated using the following condition and
procedure in step 2 is followed to fill up the T matrix. The solution is as follows:
If Near[k] ≠ 0 and cost[k, Near[k]] > cost[k, j]
Near[k] = j
Updated NEAR

1 0
2 1 28
3 1 ∞
4 5 22
J=5 0
6 0
7 5 24
Among the cost computed, 22 is minimum and hence (4,5) is selected as the minimum edge.
T matrix
u v
1 1 6
2 5 6
3 4 5
4
5
6
Updated NEAR

1 0
2 1 28
3 4 12
J=4 0
5 0
6 0
7 4 18
Among the cost computed, 12 is minimum and hence (3, 4) is selected as the minimum edge.
T matrix
u v
1 1 6
2 5 6
3 4 5
4 3 4
5
6
Updated NEAR

1 0
2 3 16
J=3 0
4 0
5 0
6 0
7 4 18

Among the cost computed, 16 is minimum and hence (2, 3) is selected as the minimum edge.
T matrix
u v
1 1 6
2 5 6
3 4 5
4 3 4
5 2 3
6

Updated NEAR

1 0
J=2 0
3 0
4 0
5 0
6 0
7 2 14

The last edge (7, 2) is selected and entered into the T matrix.
T matrix
u v
1 1 6
2 5 6
3 4 5
4 3 4
5 2 3
6 7 2

Step 4:
Now using the edges in the T matrix connect the nodes in the graph. The resulting tree is
the minimum spanning tree.
Algorithm

PRIM(E, cost, n, t)
Let (k, L) be an edge of minimum cost in E
mincost = cost[k, L]
t[1, 1] = k, t[1, 2] =L
For i = 1 to n
If cost[i, L] < cost[i, k]
Near[i] = L
Else
Near[i] = k
End if
End for
Near[k] = Near[L] = 0
For i = 2 to n -1
Let j be an index such that near[j] ≠ 0 and cost[j, near[j]] is minimum
T[i, 1] = j, t[i, 2] = Near[j]
 mincost = mincost + cost[j, near[j]]
Near[j] = 0
For k = 1 to n
If Near[k] ≠ 0 and cost[k, Near[k]] > cost[k, j]
Near[k] = j
End if
End for
Return mincost
End PRIM

SOLLIN’S ALGORITHM

A minimum spanning tree (MST) of a weighted graph G is a spanning tree of G whose

edges sum to minimum weight. In other words, a minimum spanning tree is a tree formed from a
subset of the edges in a given undirected graph, with two properties: (1) it spans the graph, i.e., it
includes every vertex in the graph, and (2) it is a minimum, i.e., the total weight of all the edges
is as low as possible.

Sollin’s algorithm selects several edges at each stage. At the start of a stage, the selected
edges, together with all n graph vertices, form a spanning forest. During a stage we select one
edge for each tree in this forest. The edge is a minimum-cost edge that has exactly one vertex in
the tree. This selected edges are added to the spanning tree being constructed . Note that it is
possible for two trees in the forest to select the same edge. So , multiple copies of the same edge
are to be eliminated . Also , when the graph has several edges with the same cost , it is possible
for two trees to select two different edges that connect them together . At the start of the first
stage , the set of selected edges is empty . The algorithm terminates when there is only one tree
at the end of a stage or when no edges remain to be selected.
The Sollin’s Algorithm based on two basic operations:

Nearest Neighbor – This operation takes a an input a tree spanning the nodes Nk and
determines an arc (ik , jk) with the minimum cost among all arcs emanating from Nk.
Merge (ik jk) – This operation takes as an input two nodes ik and jk,and if the two nodes
belong to two different trees, then merge these two trees into a single tree
Algorithm
Sollin’s Algorithm
{
Form a forest consisting of the nodes of the graph while the forest has more than one tree
For each tree in the forest
Choose the cheapest edge
 COL758: Advanced Algorithms Spring 2019

Lecture 13: February 21

Lecturer: Naveen Garg Scribe: Anant Chhajwani

Note: LATEX template courtesy of UC Berkeley EECS dept.

Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications.
They may be distributed outside this class only with the permission of the Instructor.

13.1 Shortest Paths

In this lecture, we first revised combinatorial algorithms for shortest path problem on weighted directed
graphs with negative edges, this included Bellman-Ford for single source shortest path (SSSP) and Floyd-
Warshall for all pairs shortest path (APSP). Later we studied Seidel’s algorithm, which is an algebraic
algorithm to solve all pairs shortest path problem on unweighted, undirected graphs.

The table below shows standard algorithms with their running time for variants of shortest path problem:

l : E → R+ l: E → R
Single Source Dijkstra (m + n log n) Bellman-Ford (mn)
All Pairs n× Dijkstra (mn + n2 log n) Floyd-Warshall (n3 )

13.2 Bellman-Ford (SSSP with negative edges)

We use an array di [v] to store an upper bound on the distance of v from s after ith round.

Input: A directed graph G = (V, E), a length function l : E → R, and a source vertex s ∈ V .
Result: ∀v ∈ V, dn−1 [v] stores distance of v from s
d0 [s] ← 0; d0 [v] ← ∞;
for i ← 1 to n − 1 do
for all u ∈ V do
di [u] ← min(di−1 [u], min (di−1 [v] + l(v, u));
(v,u)∈E
end
end
Algorithm 1: Bellman-Ford

Note: We assume there are no negative weight cycles in graph, as it can cause shortest path length to
be −∞ for some vertex v.

Invariant: di [v] is the length of the shortest path from s to v having at most i edges.

Proof by Induction: Since d0 [s] = 0 and d0 [v] = ∞, the invariant holds for i = 0. To verify for i + 1,
suppose the shortest s − v path containing at most i + 1 edges has
1. exactly i + 1 edges, then there is a neighbour w of v that lies on s − v path and has i edges on its
s − w path. Since the length of shortest s − w path with at most i edges is given by di [w], the length
of shortest s − v path with i + 1 edges is di+1 [v] = di [w] + l(w, v).

2. less than i + 1 edges, then the length of shortest s − v path will be same as previous iteration, hence
di+1 [v] = di [v].

13-1
Lecture 13: February 21 13-2

Since any shortest path can use at most n − 1 edges, dn−1 [v] stores the length of shortest s − v path.

Running Time: Every iteration of inner for loop takes time equal to in-degree of u, therefore each
iteration of outer for loop takes time equal to sum of in-degree over all vertices u ∈ V , which equals O(m).
Therefore, total time taken is O(mn).

13.3 Floyd-Warshall (APSP with negative edges)

We use an array di [u, v] to store an upper bound on the distance of v from u after ith round.

Input: A directed graph G = (V, E) and a length function l : E → R.

Result: ∀(u, v) ∈ V × V, dn [u, v] stores distance of v from u
d0 [u, u] ← 0;
if (u, v) ∈ E then d0 [u, v] ← l(u, v), else d0 [u, v] ← ∞;
i ← 0;
for all w ∈ V do
i ← i + 1;
for all (u, v) ∈ V × V do
di [u, v] ← min(di−1 [u, v], di−1 [u, w] + di−1 [w, v]);
end
end
Algorithm 2: Floyd-Warshall

Let w1 , w2 , . . . , wn be the vertices in the order of execution of outer for-loop in above algorithm.

Invariant: di [u, v] is the length of the shortest path from u to v which is only allowed to use vertices
{w1 , w2 , . . . , wi } as internal vertices in a path.

Proof by Induction: For i = 0, no vertex is allowed to be an internal vertex in a path, therefore the
shortest path can only be an edge. Hence, d0 [u, u] = 0, d0 [u, v] = l(u, v) if (u, v) ∈ E, otherwise d0 [u, v] = ∞.
To check for i + 1, suppose the shortest path from u to v which is allowed to use only w1 , w2 , . . . , wi+1 as
internal vertices

1. uses wi+1 as internal vertex, then consider two parts of this shortest u − v path, one path is
u − wi+1 and other is wi+1 − v. Both these paths use only w1 , . . . , wi as internal vertices, therefore
length of these paths are di [u, w] and di [w, v]. So, total length of shortest u − v path is di+1 [u, v] =
di [u, wi+1 ] + di [wi+1 , v].

2. does not use wi+1 as internal vertex, then it uses only w1 , . . . , wi as internal vertices, therefore
di+1 [u, v] = di [u, v].

Running Time: Since outer for loop performs n iterations and inner for loop performs n2 iterations,
total time taken is O(n3 ).

13.4 Seidel’s Algorithm (APSP on undirected, unweighted graphs)

Seidel’s algorithm is an algebraic algorithm to solve all pairs shortest path problem in undirected, unweighted
graphs in time O(nω log n), where O(nω ) is time for multiply two n × n square matrices. The current best
known value for ω is 2.373. Also, naive matrix multiplication has ω = 3, and using Strassen’s algorithm we
can get ω = log2 7 = 2.81.
 MRCET-CSE

The Single Source Shortest-Path Problem: DIJKSTRA'S ALGORITHMS:

In the previously studied graphs, the edge labels are called as costs, but here we
think them as lengths. In a labeled graph, the length of the path is defined to be
the sum of the lengths of its edges.

In the single source, all destinations, shortest path problem, we must find a
shortest path from a given source vertex to each of the vertices (called
destinations) in the graph to which there is a path.

Dijkstra‟s algorithm is similar to prim's algorithm for finding minimal spanning

trees. Dijkstra‟s algorithm takes a labeled graph and a pair of vertices P and Q,
and finds the

DAA DIGITAL NOTES Page 62

 MRCET-CSE
shortest path between then (or one of the shortest paths) if there is more than
[Link] principle of optimality is the basis for Dijkstra‟s algorithms.

Dijkstra‟s algorithm does not work for negative edges at all.

The figure lists the shortest paths from vertex 1 for a five vertex weighted digraph.

8 0 1

4 2 2 1 3
1 5

2 4 5 3 1 3 4

3 4 3
1 4 1 2
Graph
6 1 3 4 5

Shortest Paths

Algorithm:

Algorithm Shortest-Paths (v, cost, dist, n)

// dist [j], 1 < j < n, is set to the length of the shortest path
// from vertex v to vertex j in the digraph G with n vertices.
// dist [v] is set to zero. G is represented by its
// cost adjacency matrix cost [1:n, 1:n].
{
for i :=1 to n do
{
S [i] := false; //
Initialize [Link] [i] :=cost [v, i];
}
S[v] := true; dist[v] := 0.0; // Put
v in [Link] num := 2 to n – 1 do
{
Determine n - 1 paths from v.
Choose u from among those vertices not in S such that dist[u] is
minimum;S[u] := true; // Put u is S.
for (each w adjacent to u with S [w] = false) do
if (dist [w] > (dist [u] + cost [u, w]) then // Update
distancesdist [w] := dist [u] + cost [u, w];
}
}

Running time:
Depends on implementation of data structures for dist.

 Build a structure with n elements A

 at most m = E  times decrease the value of an item mB
 „n‟ times select the smallest value nC
 For array A = O (n); B = O (1); C = O (n) which gives O (n2) total.
 For heap A = O (n); B = O (log n); C = O (log n) which gives O (n + m
log n)total.

DAA DIGITAL NOTES Page 63

Lecture 13

Network Flow
Supplemental reading in CLRS: Sections 26.1 and 26.2

When we concerned ourselves with shortest paths and minimum spanning trees, we interpreted the
edge weights of an undirected graph as distances. In this lecture, we will ask a question of a different
sort. We start with a directed weighted graph G with two distinguished vertices s (the source) and
t (the sink). We interpret the edges as unidirectional water pipes, with an edge’s capacity indicated
by its weight. The maximum flow problem then asks, how can one route as much water as possible
from s to t?
To formulate the problem precisely, let’s make some definitions.

Definition. A flow network is a directed graph G = (V , E) with distinguished vertices s (the source)
and t (the sink), in which each edge (u, v) ∈ E has a nonnegative capacity c(u, v). We require that E
never contain both (u, v) and (v, u) for any pair of vertices u, v (so in particular, there are no loops).
Also, if u, v ∈ V with (u, v) 6∈ E, then we define c(u, v) to be zero. (See Figure 13.1).

In these notes, we will always assume that our flow networks are finite. Otherwise, it would be
quite difficult to run computer algorithms on them.

Definition. Given a flow network G = (V , E), a flow in G is a function f : V × V → R satisfying

1. Capacity constraint: 0 ≤ f (u, v) ≤ c(u, v) for each u, v ∈ V

12

16 20

s 9
4 7 t

13 4
14

Figure 13.1. A flow network.

 2. Flow conservation: for each u ∈ V \ { s, t}, we have1
X X
f (v, u) = f (u, v) .
v∈V v∈V
| {z } | {z }
flow into u flow out of u

In the case that flow conservation is satisfied, one can prove (and it’s easy to believe) that the net flow
out of s equals the net flow into t. This quantity is called the flow value, or simply the magnitude,
of f . We write X X X X
|f | = f (s, v) − f (v, s) = f (v, t) − f (t, v).
v∈V v∈V v∈V v∈V
|{z}
flow value

Note that the definition of a flow makes sense even when G is allowed to contain both an edge
and its reversal (and therefore is not truly a flow network). This will be important in §13.1.1 when
we discuss augmenting paths.

13.1 The Ford–Fulkerson Algorithm

The Ford–Fulkerson algorithm is an elegant solution to the maximum flow problem. Fundamen-
tally, it works like this:

1 while there is a path from s to t that can hold more water do

2 Push more water through that path

Two notes about this algorithm:

• The notion of “a path from s to t that can hold more water” is made precise by the notion of an
augmenting path, which we define in §13.1.1.

• The Ford–Fulkerson algorithm is essentially a greedy algorithm. If there are multiple possible
augmenting paths, the decision of which path to use in line 2 is completely arbitrary.2 Thus,
like any terminating greedy algorithm, the Ford–Fulkerson algorithm will find a locally opti-
mal solution; it remains to show that the local optimum is also a global optimum. This is done
in §13.2.

13.1.1 Residual Networks and Augmenting Paths

The Ford–Fulkerson algorithm begins with a flow f (initially the zero flow) and successively improves
f by pushing more water along some path p from s to t. Thus, given the current flow f , we need
1 In order for a flow of water to be sustainable for long periods of time, there cannot exist an accumulation of excess

water anywhere in the pipe network. Likewise, the amount of water flowing into each node must at least be sufficient to
supply all the outgoing connections promised by that node. Thus, the amount of water entering each node must equal the
amount of water flowing out. In other words, the net flow into each vertex (other than the source and the sink) must be
zero.
2 There are countless different versions of the Ford–Fulkerson algorithm, which differ from each other in the heuristic

for choosing which augmenting path to use. Different situations (in which we have some prior information about the
nature of G) may call for different heuristics.

Lec 13 – pg. 2 of 11
a way to tell how much more water a given path p can carry. To start, note that a chain is only as
strong as its weakest link: if p = 〈v0 , . . . , vn 〉, then
µ ¶ µ ¶
amount of additional water amount of additional water that
= min .
that can flow through p 1≤ i ≤ n can flow directly from v i −1 to v i

All we have to know now is how much additional water can flow directly between a given pair of
vertices u, v. If (u, v) ∈ E, then clearly the flow from u to v can be increased by up to c(u, v) − f (u, v).
Next, if (v, u) ∈ E (and therefore (u, v) 6∈ E, since G is a flow network), then we can simulate an
increased flow from u to v by decreasing the throughput of the edge (v, u) by as much as f (v, u).
Finally, if neither (u, v) nor (v, u) is in E, then no water can flow directly from u to v. Thus, we define
the residual capacity between u and v (with respect to f ) to be

 c(u, v) − f (u, v) if (u, v) ∈ E


c f (u, v) = f (v, u) if (v, u) ∈ E (13.1)


0 otherwise.

When drawing flows in flow networks, it is customary to label an edge (u, v) with both the capacity
c(u, v) and the throughput f (u, v), as in Figure 13.2.
Next, we construct a directed graph G f , called the residual network of f , which has the same
vertices as G, and has an edge from u to v if and only if c f (u, v) is positive. (See Figure 13.2.) The
weight of such an edge (u, v) is c f (u, v). Keep in mind that c f (u, v) and c f (v, u) may both be positive
for some pairs of vertices u, v. Thus, the residual network of f is in general not a flow network.
Equipped with the notion of a residual network, we define an augmenting path to be a path
from s to t in G f . If p is such a path, then by virtue of our above discussion, we can perturb the flow
f at the edges of p so as to increase the flow value by c f (p), where

c f (p) = min c f (u, v). (13.2)

(u,v)∈ p

The way to do this is as follows. Given a path p, we might as well assume that p is a simple path.3
In particular, p will never contain a given edge more than once, and will never contain both an edge
and its reversal. We can then define a new flow f 0 in the residual network (even though the residual
network is not a flow network) by setting
(
c f (p) if (u, v) ∈ p
f 0 (u, v) =
0 otherwise.

Exercise 13.1. Show that f 0 is a flow in G f , and show that its magnitude is c f (p).

Finally, we can “augment” f by f 0 , obtaining a new flow f ↑ f 0 whose magnitude is ¯ f ¯ + ¯ f 0 ¯ =

¯ ¯ ¯ ¯

3 Recall that a simple path is a path which does not contain any cycles. If p is not simple, we can always pare p down to

a simple path by deleting some of its edges (see Exercise B.4-2 of CLRS, although the claim I just made is a bit stronger).
Doing so will never decrease the residual capacity of p (just look at (13.2)).

Lec 13 – pg. 3 of 11
 Flow/Capacity

12/12

11/16 15/20

4/9
s 1/4 7/7 t

8/13 4/4
11/14

Residual Network

12

5 5
11 4 15
5
s 3 1 7 t
4
8
5 4
3
11
Augmented Flow

12/12

11/16 19/20

0/9
s 1/4 7/7 t

12/13 4/4
11/14

New Residual Network

12

5 1
11 19

s 9
3 1 7 t

12
1 4
3
11

Figure 13.2. We begin with a flow network G and a flow f : the label of an edge (u, v) is “a/b,” where a = f (u, v) is the flow
through the edge and b = c(u, v) is the capacity of the edge. Next, we highlight an augmenting path p of capacity 4 in the
residual network G f . Next, we augment f by the augmenting path p. Finally, we obtain a new residual network in which
there happen to be no more augmenting paths. Thus, our new flow is a maximum flow.

Lec 13 – pg. 4 of 11
¯ f ¯ + c f (p). It is defined by4
¯ ¯


 f (u, v) + c f (p) if (u, v) ∈ p and (u, v) ∈ E


0
¡ ¢
f ↑ f (u, v) = f (u, v) − c f (p) if (v, u) ∈ p and (u, v) ∈ E


 f (u, v) otherwise.

Lemma 13.1 (CLRS Lemma 26.1). Let f be a flow in the flow network G = (V , E) and let f 0 be a flow
in the residual network G f . Let f ↑ f 0 be the augmentation of f by f 0 , as described in (13.3). Then

¯ f ↑ f 0¯ = ¯ f ¯ + ¯ f 0¯ .
¯ ¯ ¯ ¯ ¯ ¯

Proof sketch. First, we show that f ↑ f 0 obeys the capacity constraint for each edge in E and obeys
flow conservation for ¯each vertex in V \ { s, t}. Thus, f ↑ f 0 is truly a flow in G. Next, we obtain
the identity ¯ f ↑ f 0 ¯ = ¯ f ¯ + ¯ f 0 ¯ by simply expanding the left-hand side and rearranging terms in the
¯ ¯ ¯ ¯ ¯

summation.

13.1.2 Pseudocode Implementation of the Ford–Fulkerson Algorithm

Now that we have laid out the necessary conceptual machinery, let’s give more detailed pseudocode
for the Ford–Fulkerson algorithm.

Algorithm: F ORD –F ULKERSON(G)

1 B Initialize flow f to zero
2 for each edge (u, v) ∈ E do
3 (u, v). f ← 0
4 B The following line runs a graph search algorithm (such as BFS or DFS)∗ to find a
path from s to t in G f
5 while there exists a path p : s t in G f do
© ª
6 c f (p) ← min c f (u, v) : (u, v) ∈ p
7 for each edge (u, v) ∈ p do
8 B Because (u, v) ∈ G f , it must be the case that either (u, v) ∈ E or (v, u) ∈ E.
9 B And since G is a flow network, the “or” is exclusive: (u, v) ∈ E xor (v, u) ∈ E.
10 if (u, v) ∈ E then
11 (u, v). f ← (u, v). f + c f (p)
12 else
13 (v, u). f ← (v, u). f − c f (p)
∗ For more information about breath-first and depth-first searches, see Sections 22.2 and 22.3 of CLRS.

Here, we use the notation (u, v). f synonymously with f (u, v); though, the notation (u, v). f suggests
a convenient implementation decision in which we attach the value of f (u, v) as satellite data to the
4 In a more general version of augmentation, we don’t require p to be a simple path; we just require that f 0 be some

flow in the residual network G f . Then we define

(
0 f (u, v) + f 0 (u, v) − f 0 (v, u) if (u, v) ∈ E
f (u, v) = (13.3)
0 otherwise.

Lec 13 – pg. 5 of 11
edge (u, v) itself rather than storing all of f in one place. Also note that, because we often need to
consider both f (u, v) and f (v, u) at the same time, it is important that we equip each edge (u, v) ∈ E
with a pointer to its reversal (v, u). This way, we may pass from an edge (u, v) to its reversal (v, u)
without performing a costly search to find (v, u) in memory.
We defer the proof of correctness to §13.2. We do show, though, that the Ford–Fulkerson algo-
rithm halts if the edge capacities are integers.

Proposition 13.2. If the edge capacities of G are integers, then the Ford–Fulkerson algorithm termi-
nates in time O E · | f ∗ | , where | f ∗ | is the magnitude of any maximum flow for G.
¡ ¢

Proof. Each time we choose an augmenting path p, the right-hand side of (13.2) is a positive integer.
Therefore, each time we augment f , the value of | f | increases by at least 1. Since | f | cannot ever
exceed | f ∗ |, it follows that lines 5–13 are repeated at most | f ∗ | times. Each iteration of lines 5–13
takes O(E) time if we use a breadth-first or depth-first search in line 5, so the total running time of
F ORD –F ULKERSON is O E · | f ∗ | .
¡ ¢

Exercise 13.2. Show that, if the edge capacities of G are rational numbers, then the Ford–Fulkerson
algorithm eventually terminates. What sort of bound can you give on its running time?

Proposition 13.3. Let G be a flow network. If all edges in G have integer capacities, then there exists
a maximum flow in G in which the throughput of each edge is an integer. One such flow is given by
running the Ford–Fulkerson algorithm on G.

Proof. Run the Ford–Fulkerson algorithm on G. The residual capacity of each augmenting path p in
line 5 is an integer (technically, induction is required to prove this), so the throughput of each edge is
only ever incremented by an integer. The conclusion follows if we assume that the Ford–Fulkerson
algorithm is correct. The algorithm is in fact correct, by Corollary 13.8 below.

Flows in which the throughput of each edge is an integer occur frequently enough to deserve a
name. We’ll call them integer flows.
Perhaps surprisingly, Exercise 13.2 is not true when the edge capacities of G are allowed to be
arbitrary real numbers. This is not such bad news, however: it simply says that there exists a
sufficiently foolish way of choosing augmenting paths so that F ORD –F ULKERSON never terminates.
If we use a reasonably good heuristic (such as the shortest-path heuristic used in the Edmonds–Karp
algorithm of §13.1.3), termination is guaranteed, and the running time needn’t depend on | f ∗ |.

13.1.3 The Edmonds–Karp Algorithm

The Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson algorithm in which
the the augmenting path p is chosen to have minimal length among all possible augmenting paths
(where each edge is assigned length 1, regardless of its capacity). Thus the Edmonds–Karp algorithm
can be implemented by using a breadth-first search in line 5 of the pseudocode for F ORD –F ULKERSON.

Proposition 13.4 (CLRS Theorem 26.8). In the Edmonds–Karp algorithm, the total number of aug-
mentations is O(V E). Thus total running time is O V E 2 .
¡ ¢

Proof sketch.

• First one can show that the lengths of the paths p found by breadth-first search in line 5 of
F ORD –F ULKERSON are monotonically nondecreasing (this is Lemma 26.7 of CLRS).

Lec 13 – pg. 6 of 11
 • Next, one can show that each edge e ∈ E can only be the bottleneck for p at most O(V ) times. (By
“bottleneck,” we mean that e is the (or, an) edge of smallest capacity in p, so that c f (p) = c f (e).)

• Finally, because only O(E) pairs of vertices can ever be edges in G f and because each edge can
only be the bottleneck O(V ) times, it follows that the number of augmenting paths p used in
the Edmonds–Karp algorithm is at most O(V E).

• Again, since each iteration of lines 5–13 of F ORD –F ULKERSON (including the breadth-first
search) takes time O(E), the total running time for the Edmonds–Karp algorithm is O V E 2 .
¡ ¢

The shortest-path heuristic of the Edmonds–Karp algorithm is just one possibility. Another in-
teresting heuristic is relabel-to-front, which gives a running time of O V 3 . We won’t expect you
¡ ¢

to know the details of relabel-to-front for 6.046, but you might find it interesting to research other
heuristics on your own.

13.2 The Max Flow–Min Cut Equivalence

Definition. A cut (S, T = V \ S) of a flow network G is just like a cut (S, T) of the graph G in the
sense of §3.3, except that we require s ∈ S and t ∈ T. Thus, any path from s to t must cross the cut
(S, T). Given a flow f in G, the net flow f (S, T) across the cut (S, T) is defined as
X X X X
f (S, T) = f (u, v) − f (v, u). (13.4)
u ∈ S v∈ T u ∈ S v∈ T

One way to picture this is to think of the cut (S, T) as an oriented dam in which we count water
flowing from S to T as positive and water flowing from T to S as negative. The capacity of the cut
(S, T) is defined as X X
c(S, T) = c(u, v). (13.5)
u ∈ S v∈ T

The motivation for this definition is that c(S, T) should represent the maximum amount of water
that could ever possibly flow across the cut (S, T). This is explained further in Proposition 13.6.

Lemma 13.5 (CLRS Lemma 26.4). Given a flow f and a cut (S, T), we have

f (S, T) = | f | .

We omit the proof, which can be found in CLRS. Intuitively, this lemma is an easy consequence of
flow conservation. The water leaving s cannot build up at any of the vertices in S, so it must cross
over the cut (S, T) and eventually pour out into t.

Proposition 13.6. Given a flow f and a cut (S, T), we have

f (S, T) ≤ c(S, T).

Thus, applying Lemma 13.5, we find that for any flow f and any cut (S, T), we have

| f | ≤ c(S, T).

Lec 13 – pg. 7 of 11
 CSL851: Algorithmic Graph Theory Semester I 2013-2014

Lecture 1: July 24
Lecturer: Naveen Garg Scribes: Suyash Roongta

Note: LaTeX template courtesy of UC Berkeley EECS dept.

Disclaimer: These notes have not been subjected to the usual scrutiny reserved for formal publications.
They may be distributed outside this class only with the permission of the Instructor.

Matching in Bipartite Graphs

Definition 1.1 Given a graph G = (V,E), M ⊆ E is said to be a matching if M is an independent set of

edges, i.e., no two edges of M are incident on the same vertex.

A single edge set is a trivial matching. We are interested in an algorithm to find the largest matching in a
given bipartite graph. The algorithm that we are going to discuss is an iterative algorithm.

1.0.1 Augmenting path

Let M be the current matching. Suppose M is not maximum. Let M ’ be the maximum matching. Consider
the symmetric difference of M and M ’, i.e., the set of all edges present in exactly one of M and M ’.
Let v be any vertex. By the definition of matching, in the symmetric difference, there is at most one edge
from M incident on v, and at most one edge from M ’. This gives us

deg(v) ≤ 2

This means that we must have a disjoint union of paths and cycles. Let us denote the edges of the matching
M by the colour blue and those of the matching M 0 by the colour red. Observe that two edges of the same
colour cannot be incident on a vertex. Hence, the cycles and paths must have alternating red and blue edges.

Figure 1.1: Symmetric Difference of M and M 0

1-1
1-2 Lecture 1: July 24

Lemma 1.2 If M is not a maximum matching, there must exist an alternating path of odd length starting
with a red edge.

Proof: All the cycles are even in size, because of the alternating edges. Now, suppose all the paths also
had even length. Then the number of edges of M in the symmetric difference is equal to that of M 0 . This
implies
|M | = |M 0 |
since the edges of M and M 0 not in the symmetric difference are common to both. Therefore, if M is not
maximum, there must be an alternating path with more red edges than blue ones. This will be an odd length
alternating path starting with a red edge.

Figure 1.2: Odd length alternating path

We call such a path an augmenting path. Note that the vertices on either end of the augmenting path are
unmatched in our current matching M . This concept of augmenting paths gives the following general idea
of an iterative algorithm to compute the maximum matching in a bipartite graph.
If our current matching M is not maximum, there must exist a path of odd length that starts with an
unmatched vertex, takes alternately an edge not in the matching and an edge in the matching and ends up
at another unmatched vertex. If we flip the edges along this path, i.e., the edges along this path which were
in the matching go out of the matching, and those which weren’t are now included in the matching.

Figure 1.3: Augmenting procedure

Note: Flipping will not cause a vertex to have more than two incident edges in the matching, since, the
end vertices on the path were unmatched, and the other vertices were already matched, and thus had no
edge incident on them apart from the ones in the alternating path.
Following this procedure, we have increased the size of our matching by 1. This is called augmenting the
matching. We can do this iteratively till we get a maximum matching. The number of times we will have
repeat this procedure is at most n where n is the number of vertices in one partition of the bipartite graph.
In the next section, we formally describe the algorithm and argue about its correctness.
Lecture 1: July 24 1-3

1.0.2 Alternating tree algorithm

Given a bipartite graph G = (U, V, E), we start with an empty matching and iteratively augment the
matching using the following procedure
(Let us denote the vertices on the U side by the colour red and the vertices on the V side by the colour
blue.)

1. Start with an unmatched red vertex v.

2. Consider all the unmatched edges out of it. If one of these leads to an unmatched vertex w, add the
edge (v, w) to the matching. Otherwise go to step 3.

3. From the set of blue vertices obtained in the previous step, consider all the matched edges.

4. From the set of red vertices obtained in the previous step, consider all the unmatched edges. If one of
these leads to an unmatched vertex, we have found an augmenting path; flip along this path to increase
the size of the matching by 1. Otherwise, go back to step 3.

Figure 1.4: Building alternating tree

If we find an augmenting path, we improve our matching by flipping along the augmenting path, and we can
start afresh with another unmatched red vertex and repeat the procedure and keep doing that till we get a
maximum matching.

Figure 1.5: No augmenting path found

1-4 Lecture 1: July 24

Suppose, we are not able to find an augmenting path, i.e., at step 4, all the unmatched edges are back
edges. Does this imply that our matching is maximum? Let us consider the case when vertex v is the only
unmatched red vertex.
Let us denote the set of red vertices in the tree by A and the set of blue vertices by B. Then

|A| = |B| + 1

since apart from vertex v, each red vertex is matched to exactly one blue vertex (See FIg 1.5). Now, there
cannot be an edge from a vertex in A to a vertex in V \B. If there was such an edge, by the procedure
described above, it would have been included in the tree.

Figure 1.6: All edges starting from A end up in B

This means that all the vertices in A have to be matched to the vertices in B and since the size of B is one
less, one vertex of A will remain unmatched in any matching. And hence if v is the only unmatched vertex
in U , the current matching is maximum.
Now, suppose v wasn’t the only unmatched vertex in U . Then, we throw away all vertices in the alternating
tree rooted at v and start building an alternating tree from another unmatched vertex in U . We do this
until we exhaust all unmatched vertices. Whenever we find an augmenting path, we improve our matching
and start building alternating trees afresh.

Figure 1.7: Discarding is justified

Lecture 1: July 24 1-5

Suppose we end up with 3 unmatched vertices, for which no augmenting path is found. As before, let us
denote the set of vertices of U side in the trees by A and the set of vertices of V side by B. Then, as argued
above,
|A| = |B| + 3
At least 3 vertices will remain unmatched in any matching, and since we also have 3 unmatched vertices,
our matching is maximum.

1.0.3 Size of maximum matching

Definition 1.3 The neighbourhood of a set S, denoted by N (S) is defined as

N (S) = {v : u ∈ S; (u, v) ∈ E}

Figure 1.8: Neighbourhood of a set

Theorem 1.4 A bipartite graph G = (U, V, E) (|U | = |V | = n) has a perfect matching, i.e., a matching of
size n, iff
∀S ⊆ V, |N (S)| ≥ |S|
This theorem is called Hall’s Theorem. And a set S s.t. |N (S)| < |S| is called a Hall set.

Proof:

1. If G has a perfect matching, then there is no Hall set, i.e., ∀S ⊆ V, |N (S)| ≥ |S|
Suppose there exists a Hall set, i.e., ∃S s.t. |N (S)| < |S|, then by an argument similar to one given
above, all vertices of S cannot be matched, and hence there is no perfect matching.
2. If there is no Hall set, i.e., ∀S ⊆ V, |N (S)| ≥ |S|, then G has a perfect matching
Suppose G does not have a perfect matching. That means, that if we run our alternating tree algorithm
on G, we’ll land up with an unmatched vertex v for which we cannot find an augmenting path. Using
the alternating tree rooted at v, we can construct a Hall set (set of all U vertices in the tree).

Definition 1.5 The deficiency of a set S, denoted by def (S) is defined as

def (S) = |S| − |N (S)|
1-6 Lecture 1: July 24

Theorem 1.6 Let the size of the maximum matching of a bipartite graph G = (U, V, E) (|U | = |V | = n) be
denoted by s(G). Then
s(G) = n − max def (S)
S⊆V

(Note: The notation s(G) is used for convenience, is not standard.)

Proof:

1. s(G) ≤ n − maxS⊆V def (S)

Let the maximum deficiency value be k and let S 0 be a set with deficiency k. Then, at least k vertices
of S 0 will remain unmatched in any matching. Hence, s(G) ≤ n − k.

2. s(G) ≥ n − maxS⊆V def (S)

Suppose s(G) = n − k, then in our matching, there must be k unmatched vertices in U for which the
alternating tree rooted at these vertices do not contain an augmenting path. We can construct a set
A as above, whose deficiency would be k. The maximum deficiency value is then greater than or equal
to k, by definition.

k ≤ max def (S)

S⊆V

−k ≥ − max def (S)

S⊆V

n − k ≥ n − max def (S)

S⊆V

s(G) ≥ n − max def (S)

S⊆V

In fact there cannot be a set with deficiency greater than k, because then the size of the maximum
matching would have to be less than n-k, by the first point.

1.0.4 Time complexity analysis

The matching is augmented at most n times. The time taken to perform one augmentation (building the
alternating tree, finding the augmenting path by building backwards and flipping along it) is O(m) since
each edge is considered at most once. So, the total time complexity of the algorithm is O(mn).