UNIT-II

Disjoint Sets: Disjoint set operations, union and find algorithms, Priority Queue- Heaps, Heapsort.
Backtracking: General method, applications, n-queen’s problem, sum of subsets problem, graph
Coloring, Hamiltonian cycles.
DISJOINT SETS
 Two sets are called disjoint sets if they don’t have any element in common. In other words, the
intersection of A and B is the empty set, denoted as ∅.
Example 1
 Let A = {1, 2, 3} and B = {4, 5, 6}.
 The intersection of A and B (A ∩ B) is ∅, because there are no elements that are in both A
and B.
 Therefore, A and B are disjoint sets.
Example 2
 Let A = {1, 2, 3} and B = {2, 4, 5}.
 The intersection of A and B (A ∩ B) is {2}, because the element 2 is in both A and B.
 Therefore, A and B are not disjoint sets.
SET REPRESENTATIONS
Sets can be represented in 3 ways
1 : Tree Representation
2 : Data Representation
3 : Array Representation
Tree Representation
 The set will be represented as the tree structure where all children will store the address of parent /
root node.
 The root node will store null at the place of parent address.
 In the given set of elements any element can be selected as the root node, generally we select the first
node as the root node.
Example: S1 = { 1, 7, 8, 9 } S2 = { 2, 5, 10 } S3 = { 3, 4, 6 } , Then these sets can be represented
as

S1 S2 S3

1
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Data Representation
 We need to maintain the name of each set.
 So, we require one more data structure to store the set names.
 The data structure contains two fields.
 One is the set name and the other one is the pointer to root.
 The data representation for S1, S2 and S3.
Example: S1 = { 1, 7, 8, 9 } S2 = { 2, 5, 10 } S3 = { 3, 4, 6 }

Array Representation
 To represent the sets, we use an array of 1 to n elements where n is the maximum value among the
elements of all sets.
 The index values represent the nodes (elements of set) and the entries represent the parent node.
 For the root value the entry will be‘-1’.
Example: Array Representation of the sets S1, S2 and S3
S1 = { 1, 7, 8, 9 } S2 = { 2, 5, 10 } S3 = { 3, 4, 6 }

S1 S2 S3

i 1 2 3 4 5 6 7 8 9 10

p -1 5 -1 3 -1 3 1 1 1 5

2
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
DISJOINT SET OPERATIONS
Disjoint set supports two operations
1. Union
2. Find
Disjoint set Union
If Si and Sj are two disjoint sets, then their union Si U Sj = { all elements x such that x is in Si or Sj }
Example
S1 = { 1, 7, 8, 9 } S2 = { 2, 5, 10 }
S1 U S2 = { 1, 7, 8, 9 , 2, 5, 10 }
To perform disjoint set union between two sets Si and Sj can take any one root and make it sub-tree of the
other.
Example
S1 = { 1, 7, 8, 9 } S2 = { 2, 5, 10 } , Then S1 U S2 can be represented as any one of the following.

2 : Find ( i ) : Given the element i, find the set containing i.

Example: S1 = { 1, 7, 8, 9 } S2 = { 2, 5, 10 } S3 = { 3, 4, 6 }
Find ( 4 ) = 4 is in set S3
Find ( 9 ) = 9 is in set S1
Find ( 10 ) = 10 is in set S2

3
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
UNION AND FIND ALGORITHMS
1. Simple Union
2. Find
3. Weighted Union
4. Collapsing Find
1. Simple Union
To perform union the SimpleUnion(i,j) function takes the inputs as the set roots i and j . And make the
parent of i as j i.e, make the second root as the parent of first root.
Algorithm
SimpleUnion (i,j)
{
P[i]:=j;
}
Example : union ( 1, 3 )

( or )

Example : The union operation can be performed as follows.

union(10,20), union(20,30), union(30,40), union(40,50).

10 20 30 40 50 Initially

Union algorithm Time complexity : O ( n )

We can improve the performance of our union algorithm by avoiding the creation of degenerate trees.
We can use Weighted Union rule.
4
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
2. Find Algorithm : FIND(i), means it finds the root node of ith node, in other words, it returns the name of set i.
Algorithm
SimpleFind(i)
{
while ( p[i] >= 0 ) do
i = p[i];
return i;
}
Example : Consider a tree

Solution : If we want to Find(i) = 8,

Array Representation of tree
i 1 2 3 4 5 6 7 8

p -8 1 1 3 1 5 5 7
i=8
while ( p[i]>=0) – true
i=p[8], i.e 7
while ( p[i]>=0) – true
i=p[7], i.e 5
while ( p[i]>=0) – true
i=p[5], i.e 1
while ( p[i]>=0) – false
return i, i.e i = 1
So 1 is the root node of node 8
Find algorithm Time complexity : O ( N2 )

5
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
3. Weighted Union Algorithm
Definition : if the number of nodes in the tree with root i is less than the number in the tree with root j,
then make j the parent of i ; otherwise make i the parent of j.
Algorithm :
Weighted_Union( i, j )
{
p[i]  - count[i]; //Initially
p[j]  - count[j];
temp  p[i] + p[j];
if(p[i] > p[j]) then // i has few nodes than j
{
p[i] = j; // j becomes parent of i
p[j] = temp;
}
else
{
p[j] = i; // i becomes parent of j
p[i] = temp;
}
}
Example : Weighting rule to perform the sequence of set unions given below

1 2 3 4 -------------------------- n

Solution : Array Representation

i 1 2 3 4 n
----------------------------------
p -1 -1 -1 -1 -1

Step1 : Initially

1 2 3 4 ------------------------- n

6
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step2 : Union(1,2)
i 1 2 3 4 N
----------------------------------
p -2 1 -1 -1 -1
[ -2 ]
1 3 4 ------------------------ n

2
Step3 : Union(1,3)
i 1 2 3 4 n
----------------------------------
p -3 1 1 -1 -1
[ -3 ]
1 4 ------------------------ n

2 3

Step4 : Union(1,4)
i 1 2 3 4 n
----------------------------------
p -4 1 1 1 -1
[-4]
1 ------------- n

2 3 4

Step4 : Union(1,n)
1

2 3 4 ----------------- n

The above trees obtained using the weighting rule

7
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Example
Consider the behavior of Weighted union on the following sequences of unions.
Union ( 1,2 ), Union ( 3,4 ), Union ( 5,6 ), Union ( 7,8 ), Union ( 1,3 ), Union ( 5,7 ), Union ( 1,5 ),

Solution: The sequence of unions starting from the initial configuration p[i] = -count[i]=-1

[ -1 ] [ -1 ] [ -1 ] [ -1 ] [ -1 ] [ -1 ] [ -1 ] [ -1 ]

union(1,2) union(3,4) union(5,6) union(7,8)

[ -2 ] [ -2 ] [ -2 ] [ -2 ]

union ( 5,7 )
union ( 1,3 )

[ -4 ] [ -4 ]

8
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
union ( 1,5 )

[ -4 ] [ -4 ] [ -8 ]

Explanation in Weighted Union Algorithm

Union(1,5)
i 1 2 3 4 5 6 7 8
p -4 1 1 3 -4 5 5 7
i=1 and J=5
p[ i ]=-count[i]
p[1]=-count[1]
p[ 1 ] = -4
p[ j ]=-count[j]
p[5]=-count[5]
p[ 5 ] = -4
temp = p[ i ] + p [ j ]
temp = -4 – 4 = -8
if ( p[ i ] > p[ j ] ) then
-4 > -4 – false
p[ j ] = i, p[ 5 ] = 1 // for 5th node 1 is the root node
p[ i ] = temp
p[ 1 ] = -8
9
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
4. Collapsing Find Algorithm
 The Collapsing Find Algorithm is an optimization technique used in the Union-Find data structure.
 It improves the efficiency of the Find operation by applying path compression, which helps flatten
the structure of the tree over time, leading to nearly constant time operations.
Key Concept
 The Find operation determines the root (or representative) of a set.
 Without optimization, the worst-case time complexity is O(n).
 Path compression is applied so that each node directly points to the root of the set, reducing the
tree depth.
 This optimization ensures that subsequent operations are much faster.
Algorithm
Collapse_find( i )
{
// Problem Description : This algorithm Collapse all nodes from i to root node.
r = i;
while ( p[r] > 0 ) do
r := p[r]; //Find the root.
while ( i # r) do //Collapse nodes from i to root r
{
s =p[i];
p[i] =r;
i =s;
}
return r;
}

10
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Example : Consider a tree

Solution : If we want to Find(i) = 8,

Array Representation of tree
i 1 2 3 4 5 6 7 8

p -8 1 1 3 1 5 5 7

Step1 : i = 8, r = 8
while ( p[r]>0) – true
r=p[8], i.e 7
while ( p[r]>0) – true
r=p[7], i.e 5
while ( p[r]>0) – true
r=p[5], i.e 1
while ( p[r]>0) – false
Step2 : Collapse nodes from i to root r.

while ( i # r )
8 # 1 – true
s=p[i],
s=p[8]
s=7
p[i]=r
11
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
 p[8]=1 // means for 8th node 1 is the root node
i=7

again while ( i # r )
7 # 1 – true
s=p[i],
s=p[7]
s=5
p[i]=r
p[7]=1 // means for 7th node 1 is the root node
i=5

again while ( i # r )
5 # 1 – true
s=p[i],
s=p[5]
s=1
p[i]=r
p[5]=1 // means for 5th node 1 is the root node
i=1
again while ( i # r )
1 # 1 – false
return r, i.e r=1

Array Representation of collapsing nodes from i to root j

i 1 2 3 4 5 6 7 8

p -8 1 1 3 1 5 1 1

After collapsing nodes from i to root j , the given tree is

12
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
PRIORITY QUEUE
 A priority queue is a type of queue that arranges elements based on their priority values.
 Each element has a priority associated. When we add an item, it is inserted in a position based on its
priority.
 Elements with higher priority are typically retrieved or removed before elements with lower priority.

Difference between Priority Queue and Normal Queue

In a queue, the first-in-first-out rule is implemented whereas, in a priority queue, the values are
removed on the basis of priority. The element with the highest priority is removed first.

13
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
IMPLEMENTATION OF PRIORITY QUEUE
 Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary
search tree.
 Among these data structures, heap data structure provides an efficient implementation of priority
queues.
HEAP DATA STRUCTURE
A Heap is a special Tree-based data structure in which the tree is a complete binary tree.
Heap can be classified into two types
1. Max Heap
2. Min Heap
Max Heap
 In max heap, every node contains greater or equal value element than its child nodes are called Max
Heap.
 Thus, root node contains the largest value element.
Example : Consider the following example of max heap-

This is max heap because-

 Every node contains greater or equal value element than its child nodes.
 It is an almost complete binary tree with its last level strictly filled from left to right.

14
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Min Heap
 In min heap, every node contains lesser value element than its child nodes are called Min Heap.
 Thus, root node contains the smallest value element.
Example : Consider the following example of min heap

This is min heap because-

 Every node contains lesser value element than its child nodes.
 It is an almost complete binary tree with its last level strictly filled from left to right.
Max Heap Algorithm

Step 1: Convert the given array of elements into complete binary tree.

Step 2: Insert the newNode as last leaf from left to right.

Step 3: Compare newNode value with its Parent node.

Step 4: If newNode value is greater than its parent, then swap both of them.

Step 5: Repeat step 3 and step 4 until newNode value is less than its parent node (or) newNode

reaches to root.

15
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Example
Construct Heap tree for the following sequence of elements then sort the elements into ascending
order using heap sort technique.
50,25,30,75,100,45,80
Insert 50
 First element 50 is root.

Insert 25
 25 is inserted at left of 50.
 The tree is satisfying heap condition.

50

25

Insert 30
 30 is inserted at right of 50.
 The tree is satisfying heap condition. So it is a Heap tree.

50

25 30

Insert 75
 75 is inserted at left of 25.
 The tree is not satisfying heap condition because 75 is greater than 25 as well as 50.
 So exchange it with its root 25 and again 50.
 After exchange it is a heap tree.

50 50 75

25 30 75 30 50 30

75 25 25

16
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Insert 100
 100 is inserted at right of 50.
 The tree is not satisfying heap condition because 100 is greater than 50 as well as 75.
 So exchange it with its root 50 and again 75.
 After exchange it is a heap tree.

75 75 100

50 30 100 30 75 30

25 100 25 50 25 50

Insert 45
 45 is inserted at left of 30.
 The tree is not satisfying heap condition because 45 is greater than 30.
 So exchange 45 with its root 30.
 After exchange it is a heap tree.

100 100

75 30 75 45

25 50 25 50
45 30

Insert 80
 80 is inserted at right of 45.
 The tree is not satisfying heap condition because 80 is greater than 45.
 So exchange 80 with its root 45.
 After exchange it is a heap tree.

100 100

75 45 75 80

25 50 25 50
30 80 30 45

17
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
HEAP SORT
Heap sort algorithm requires two phases
1. Constructing a Heap.
2. Sorting Heap.
Heap Sort Algorithm
Step 1: Swap the Root node with the last node of the heap. Now, last node is in its proper place.
Step 2: Delete last element, put the deleted element into the sorted list and consider the remaining
elements as the new list.
Step 3: Heap after deleted element from max heap, the new list may not be in heap form. Therefore,
construct a heap of new list.
Step 4: Repeat steps 1, 2 and 3 until all elements are placed at their proper place i. e, until all elements
are sorted.
Example

18
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
 19
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
 20
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
 21
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
 22
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
BACKTRACKING
 Backtracking is one of the techniques that can be used to problem solving algorithm, like Divide and
Conquer method, Greedy Method, Dynamic Programming, Branch and Bound.
 Backtracking method uses Brute Force search that means brute force search says that for the given
problem, we try to make all the possible solutions and pick out the best solution from all the desired
solutions.
 Backtracking is used for recursion that means if the current solution is not suitable then backtracks
and tries other solution.
 Backtracking is used when we have multiple solutions, and we require all those solutions.
 Backtracking name itself suggests that we are going back and coming forward; if it satisfies the
condition, then return success, else we go back again.
How does Backtracking work?
Backtracking is a systematic method of trying out various sequences of decisions until you find out that
works.
Example

We start with a start node. First, we move to node A. Since it is not a feasible solution so we move to the
next node, i.e., B. B is also not a feasible solution, and it is a dead-end so we backtrack from node B to
node A.

23
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Suppose another path exists from node A to node C. So, we move from node A to node C. It is also a dead-
end, so again backtrack from node C to node A. We move from node A to the starting node.

Now we will check any other path exists from the starting node. So, we move from start node to the node
D. Since it is not a feasible solution so we move from node D to node E. The node E is also not a feasible
solution. It is a dead end so we backtrack from node E to node D.

Suppose another path exists from node D to node F. So, we move from node D to node F. Since it is not a
feasible solution and it's a dead-end, we check for another path from node F.

24
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Suppose there is another path exists from the node F to node G so move from node F to node G. The node
G is a success node.

Difference between the Backtracking and Recursion

 Recursion is a technique that calls the same function again and again until you reach the base case.
 Backtracking is an algorithm that finds all the possible solutions and selects the desired solution from
the given set of solutions.

25
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
APPLICATIONS OF BACKTRACKING
1. N – Queen Problems
2. Sum of Subset Problem
3. Graph Coloring Problems
4. Hamiltonian Graph Problem.
N QUEENS PROBLEMS (4 – QUEENS & 8 – QUEENS PROBLEM)
 This is generalization problem.
 If we take n=8 then the problem is called as 8 queens’ problem.
 If we take n=4 then the problem is called 4 queens’ problem.
 Consider n * n chessboard.
 Let there are N queens. These n – queens are to be placed on the n * n chessboard so that no two
queens are on the same column, same row or same diagonal.
Algorithm
NQueens(k , n )
{
for i = 1 to n do
{
if( place (k, i )) then
{
x[k] = i;
if( k = n) then
write(X[1 : n]);
else
NQueens(k + 1, n);
}
}
}
Algorithm
place ( k, i)
{
for j =1 to k – 1 do
{
if(X[k] = i) then
return false;
else
return true;
}
}

26
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
4 – QUEENS PROBLEM
 The 4 Queens Problem consists in placing four queens on a 4 x 4 chessboard so that no two queens
attack each other.
 That is, no two queens are allowed to be placed on the same row, the same column or the same
diagonal.
 We are going to look for the solution for n=4 on a 4 x 4 chessboard.

4 Queens Problem using Backtracking Algorithm

 Place each queen one by one in different rows, starting from the topmost row.
 While placing a queen in a row, check for clashes with already placed queens.
 For any column, if there is no clash then mark this row and column as part of the solution by placing
the queen.
 In case, if no safe cell found due to clashes, then backtrack (i. e, undo the placement of recent queen)
and return false.
Illustration of 4 Queens Solution:
Step 0: Initialize a 4×4 board.

27
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step 1:
 Put our first Queen (Q1) in the (0,0) cell .
 ‘x‘ represents the cells which is not safe i.e. they are under attack by the Queen (Q1).
 After this move to the next row [ 0 -> 1 ].

Step 2:
 Put our next Queen (Q2) in the (1,2) cell .
 After this move to the next row [ 1 -> 2 ].

Step 3:
 At row 2 there is no cell which are safe to place Queen (Q3) .
 So, backtrack and remove queen Q2 queen from cell ( 1, 2 ) .

28
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step 4:
 There is still a safe cell in the row 1 i.e. cell ( 1, 3 ).
 Put Queen ( Q2 ) at cell ( 1, 3).

Step 5:
 Put queen ( Q3 ) at cell ( 2, 1 ).

Step 6:
 There is no any cell to place Queen ( Q4 ) at row 3.
 Backtrack and remove Queen ( Q3 ) from row 2.
 Again there is no other safe cell in row 2, So backtrack again and remove queen ( Q2 ) from row 1.
 Queen ( Q1 ) will be removed from cell (0,0) and move to next safe cell i.e. (0 , 1).
Step 7:
 Place Queen Q1 at cell (0 , 1), and move to next row.

29
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step 8:
 Place Queen Q2 at cell (1 , 3), and move to next row.

Step 9:
 Place Queen Q3 at cell (2 , 0), and move to next row.

Step 10:
 Place Queen Q4 at cell (3 , 2), and move to next row.
 This is one possible configuration of solution

Hence the solution to 4 – queen’s problem is x1 = 2 , x2 = 4, x3 = 1, x4 = 3. i.e, first queen is placed in 2nd
column, second queen is placed in 4th column and third queen is placed in first column and fourth queen
is placed in third column.
30
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
The State Space Tree for the 4 – Queens’s problem

X1 = 1 1 X1 = 2

2 3
X2 = 2 X2 = 4
X2 = 4 X2 = 1
3

4 5 6 7 8 9
x3 = 2
4 2 X3 = 3
X2 = 3 X3 = 1

10 11
12 13 14

X4 = 3 X4 = 3

15
16

8 - QUEENS PROBLEM
 The 8 queens’ problem is the problem of placing eight queens on an 8×8 chessboard such that none of
them attack one another (no two are in the same row, column, or diagonal).
 More generally, the n queens problem places n queens on an n×n chessboard.
 we can solve 8 queens’ problem by using similar procedure adapted for 4 queens’ problem.
 The algorithm of 8 queens’ problem can be obtained by placing n=8, in N queens’ algorithm.
 The solution of 8 queens’ problem can be obtained similar to the solution of 4 queens.
Problem: X1=3, X2=6, X3=2, X4=7, X5=1, X6=4, X7=8, X8=5
The solution can be shown as

31
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
2. SUM OF SUBSETS
Given a set[] of non-negative integers and a value sum, the task is to print the subset of the given set
whose sum is equal to the given sum.
Example 1 :
Input: set[] = {1,2,1}, sum = 3
Output: [1,2],[2,1]
Explanation: There are subsets [1,2],[2,1] with sum 3.
Example 2
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: []
Explanation: There is no subset that add up to 30.
 In this case the element xi of the solution vector is either zero or one depending on whether the
weight wi is included or not.
 The children of any node are easily generated. For a node at level I the left child corresponds to xi = 1
and the right child corresponds to xi = 0.
Algorithm
SumofSub( s, k, r )
{
x[k] = 1;
if ( s + w[k] = m) then
write ( x[1 : k]) ;
else if ( s + w[k] + w[k + 1] ≤ m ) then
SumofSub(s + w[k], k + 1, r – w[k]);
if ( ( s + r – w[k] ≥ m) and ( s + w[k+1] ≤ m) then
{
x[k] = 0;
SumofSub( s, k+1, r – w[k]);
}
}

32
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Example1: Let n=3, w = {2, 4, 6} and m = 6, Find all possible subsets of w that sum to m.
Solution : n=3
M=6
w1 = 2, w2=4, w3=6
Initially three variables
S=0
k=1
r = ( 2 + 4 + 6 ) = 12
To calculate Left child and Right child
xi = 1 ( Left Child ) = s + w[k],k+1,r-w[k]
xi = 0 ( Right Child ) = s ,k+1,r-w[k]
State space tree generated by Sum of Subsets Problem

There are Two answer states in the state space tree diagram. The answer states are denoted by
A,B. There are 2 solutions
A = { 1, 1, 0 } = { 2 + 4 + 0 } = 6
B = { 0, 0, 6 } = { 0 + 0 + 6 } = 6

33
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Example 2 : Let n=6, w ={ 5,10,12,13,15,18 } and m = 30, Find all possible subsets of w that sum to
m.
Solution : n = 6, M=30
w1 = 5, w2=10, w3=12, w4=13, w5=15, w6=18
Initially three variables
S=0
k=1
r = ( 5+10+12+13+15+18 ) = 73
To calculate Left child and Right child
xi = 1 ( Left Child ) = s + w[k],k+1,r-w[k]
xi = 0 ( Right Child ) = s ,k+1,r-w[k]
State space tree generated by Sum of Subsets Problem

There are Three answer states in the state space tree diagram. The answer states are denoted by
A,B,C. There are 3 solutions
A = { 1, 1, 0, 0, 1, 0 } = { 5 + 10 + 0 + 0 + 15 + 0 } = 30
B = { 1, 0, 1, 1, 0, 0 } = { 5 + 0 + 12 + 13 + 0 + 0 } = 30
C= { 0, 0, 1, 0, 0, 1 } = { 0 + 0 + 12 + 0 + 0 + 18 } = 30

34
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
GRAPH COLOURING PROBLEM
 Graph coloring refers to the problem of coloring vertices of a graph in such a way that no two
adjacent vertices have the same color.
 This is also called the vertex coloring problem. If coloring is done using at most m colors, it is
called m-coloring.
Example

Chromatic Number
 The minimum number of colors needed to color a graph is called its chromatic number.
 For example, the following can be colored a minimum of 2 colors.

35
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Algorithm for Graph Coloring Problem
1. Start with an uncolored graph.
2. Choose a vertex to color.
3. Try assigning colors to the chosen vertex one by one.
4. If a color is valid (no adjacent vertices have the same color), move on to the next vertex.
5. If no valid color can be assigned to the current vertex, backtrack to the previous vertex and try a
different color.
6. Continue this process until all vertices are colored or all possibilities have been explored.
Example : A 4-node graph and all possible 3-colorings

Solution : State Space tree for graph coloring problem ( n=4, m=3 )

x1=1 x1=3
x1=2

x2=2 x2=1 x2=1

x2=3 x2=3 x2=2

x3=1 x3=2 x3=2

x3=3 x3=1 x3=2 x3=3 x3=1 x3=2 x3=3 x3=1 x3=3

x4=2 x4=3 x4=2 x4=3 x4=1 x4=3 x4=1 x4=3 x4=1 1 x4=2 x4=2 x4=2
2 x4=3 1 x4=3 1

Here the Solutions are

( 1, 2, 1, 3 ) ( 2, 1, 2, 3 ) ( 3, 1, 2, 1 )
( 1, 2, 3, 2 ) ( 2, 1, 3, 1 ) ( 3, 1, 3, 2 )
( 1, 3, 1, 2 ) ( 2, 3, 1, 3 ) ( 3, 2, 1, 2 )
( 1, 3, 2, 3 ) ( 2, 3, 2, 1 ) ( 3, 2, 3, 1 )

36
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Graph Coloring Applications-
Some important applications of graph coloring are as follows-
 Map Coloring
 Scheduling the tasks
 Preparing Time Table
 Assignment
 Conflict Resolution
 Sudoku
Time Complexity: O(mV)
Space Complexity: O(V)
HAMILTONIAN GRAPH
A Hamiltonian graph is the directed or undirected graph containing a Hamiltonian cycle.
The Hamiltonian cycle is the cycle that traverses all the vertices of the given graph G exactly once and
then ends at the starting vertex.
 Given a graph G = (V, E) we have to find the Hamiltonian Circuit using Backtracking approach.
 We start our search from any arbitrary vertex say 'a.' This vertex 'a' becomes the root of our
implicit tree.
 The first element of our partial solution is the first intermediate vertex of the Hamiltonian Cycle
that is to be constructed.
 The next adjacent vertex is selected by alphabetical order. If at any stage any arbitrary vertex
makes a cycle with any vertex other than vertex 'a' then we say that dead end is reached.
 In this case, we backtrack one step, and again the search begins by selecting another vertex and
backtrack the element from the partial solution must be removed.
 The search using backtracking is successful if a Hamiltonian Cycle is obtained

37
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Example : The following graph illustrates the presence of the Hamiltonian cycle in a graph G.

Step 1: Firstly, we start our search with vertex 'a.' this vertex 'a' becomes the root of our implicit tree.

Step 2: Next, The vertex adjacent to 'a' is b, c and d. it comes first in lexicographical order (b, c, d).

Step 3: Next, The vertex adjacent to 'b' is a, c and e. but ‘ a’ is already visited.

38
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step 4 : Next, The vertex adjacent to 'c' is a, b, d and e. but ‘ a’ and ‘b’ are already visited.

Step 5: Next, The vertex adjacent to 'd' is a, c, e and f. but ‘ a’ and ‘c’ are already visited.

Step 6 : Next, The vertex adjacent to 'e' is b, c and f. but ‘ b’ and ‘c’ are already visited.

39
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step 7 : Next, The vertex adjacent to 'f' is d and e, but ‘d’ and ‘e’ are already visited. Thus, we get the dead
end, and we backtrack one step

Step 8 : we backtrack one step , the vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already
been checked, and b, c, d have already visited. So, again we backtrack one step. Now, the vertex adjacent
to d are e, f from which e has already been checked, and adjacent of 'f' are d and e. The vertex 'd' has
already visited. If 'e' vertex, revisited them we get a dead end. So again we backtrack one step.
40
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step 9 : we backtrack one step , Next, The vertex adjacent to 'e' is b,c,d and f, but ‘b’ and ‘c’ are already
visited.

Step 9 : Next, The vertex adjacent to 'd' is a,c,e and f, but ‘a’,’c’ and ‘e’ are already visited.

41
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step10 : Next, The vertex adjacent to 'f' is d,e but ‘d’,and ’e’ are already visited. Thus, we get the dead end

42
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM
Step11 : Next, The vertex adjacent to 'f' is d,e but ’e’ are already visited.

Step12 : Next, The vertex adjacent to 'd' is d,e but ’e’ are already visited.

The Solution is : a – b – c – e – f – d – a

43
P. SANDHYA RANI_ADA(R22) NOTES – III YEAR II SEM