UNIT-2

DISJOINT SETS
Set:

A set is a collection of distinct elements. The Set can be represented, for examples, as
S1={1,2,5,10}.

Disjoint Sets:

The disjoints sets are those do not have any common element. For example S1={1,7,8,9} and
S2={2,5,10}, then we can say that S1 and S2 are two disjoint sets.

1. 1. A tree is used to represent each set and the root to name a set.
2. Each node points upwards to its parent
3. Two sets A and B are said to be disjoint if A— B = f. i.e., there is no common element in
both A and B
4. A collection of disjoint sets is called a disjoint set forest
5. An array can be used to store parent of each element

DISJOINT SET OPERATIONS

The disjoint set operations are

1. Union
2. Find

Union:

If Si and Sj are two disjoint sets, then their union Si U Sj consists of all the elements x such that
x is in Si or Sj.

Example:

S1 = {1, 7, 8, 9} S2 = {2, 5, 10}

S1 U S2 = {1, 2, 5, 7, 8, 9, 10}

Find:

Given the element I, find the set containing i.

Example:
S1 = {1, 7, 8, 9}

Then,

S2 = {2, 5, 10} s3 = {3, 4, 6}

Find(4)= S3 Find(5)=S2 Find(7)=S1

Set 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

Disjoint Union:

To perform disjoint set union between two sets Si and Sj can take any one root and make it sub-
tree of the other. Consider the above example sets S1 and S2 then the union of S1 and S2 can be
represented as any one of the following.

Disjoint Find:

To perform find operation, along with the tree structure 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.
UNION AND FIND ALGORITHM
In presenting Union and Find algorithms, we ignore the set names and identify sets just by the
roots of trees representing them. 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:

For the following sets the array representation is as shown below.

Algorithm for Union operation:

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;

Algorithm for find operation:

The SimpleFind(i) algorithm takes the element i and finds the root node of i. It starts at I until it
reaches a node with parent value -1.

Algorithms SimpleFind(i)

while( P[i]≥0) do i:=P[i];

return i;

Weighting rule for Union:

If the number of nodes in the tree with root I is less than the number in the tree with the root j,
then make „j‟ the parent of i; otherwise make „i' the parent of j.

Algorithm WeightedUnion(i,j)

//Union sets with roots i and j , i≠j using the weighted rule

// P[i]=-count[i] and p[j]=-count[j]

temp:= P[i]+P[j];

if (P[i]>P[j]) then

// i has fewer nodes

P[i]:=j;

P[j]:=temp;

else

// j has fewer nodes

P[j]:=i;

P[i]:=temp;
}

}
Collapsing rule for find:

If j is a node on the path from i to its root and p[i]≠root[i], then set P[j] to root[i]. Consider the
tree created by WeightedUnion() on the sequence of 1≤i≤8. Union(1,2), Union(3,4), Union(5,6)
and Union(7,8).

Algorithm CollapsingFind(i)

// Find the root of the tree containing element i

// use the collapsing rule to collapse all nodes from i to root.

r:=i;

while(P[r]>0) do r:=P[r]; //Find root

while(i≠r)

//reset the parent node from element i to the root

s:=P[i];

P[i]:=r;

i:=s;

BACKTRACKING

General Method
Backtracking is a technique based on algorithm to solve problem. It uses recursive calling to find
the solution by building a solution step by step increasing values with time. It removes the
solutions that doesn't give rise to the solution of the problem based on the constraints given to
solve the problem.

Backtracking algorithm is applied to some specific types of problems,

Decision problem used to find a feasible solution of the problem.

Optimization problem used to find the best solution that can be applied.

Enumeration problem used to find the set of all feasible solutions of the problem.

In backtracking problem, the algorithm tries to find a sequence path to the solution which has
some small checkpoints from where the problem can backtrack if no feasible solution is found
for the problem.

All solutions require a set of constraints divided into two categories: explicitand implicit
constraints.

 Explicit constraints are rules that restrict each xi to take on values only from a given set.
Explicit constraints depend on the particular instance I of problem being solved. All
tuples that satisfy the explicit constraints define a possible solution space for I.
 Implicit constraints are rules that determine which of the tuples in the solution space of I
satisfy the criterion function. Thus, implicit constraints describe the way in which the x i’s
must relate to each other.

Applications Of Backtracking
1. N-queens problem
2. Sum of subsets problem
3. Graph coloring

N-Queen’s Problem
In N-Queen problem, we are given an NxN chessboard and we have to place n queens on the
board in such a way that no two queens attack each other. A queen will attack another queen if it
is placed in horizontal, vertical or diagonal points in its way.

For solving n queens problem, we will try placing queen into different positions of one row. And
checks if it clashes with other queens. In current positioning of queens if there are any two
queens attacking each other. If they are attacking, we will backtrack to previous location of the
queen and change its positions. And check clash of queen again.

Here, We will do an example problem of 4-Queen problem.

For 4-queens problem we need to have a 4*4 chessboard.

Few key points:

1. Board[r][c] will be used to check safe positions on the board and place the queen.
 2. On encountering safe position increment the column value by 1.
3. On encountering unsafe position change the row to next row.

Step 0: C=0, R=0, formula to be used is b[r][c]

Check b[0][0] = safe, place 1st queen 0 1 2 3

Now increment column value by 1 0 Q - - -

Step 1.0: C=1, R=0 - -

1
b[0][1] = not safe, as position in firsrt row is unsafe change - Q
2
row value. Increment row value by 1
3 -
Step1.1:c=1,r=1
b[1][1] = unsafe, increment row by 1 again as its unsafe.

Step 1.2: c=1, r=2

b[2][1] = safe, place 2nd queen

Increment the value of column by 1

Step 2.0: c=2, r=0

b[0][2] = unsafe, increment row by 1

Step 2.1: c=2,r=1

b[1][2] = unsafe, increment row by 1

Step 2.2: c=2, r=2

b[2][2] = unsafe, increment row by 1

Step 2.3: c=2, r=3

b[3][2] = unsafe, we reached the last row of column 2 but no safe position we found to place the
third queen. Now we have to backtrack and remove the last positioned queen i.e., at position b[2]
[1] and place that queen by increasing the row value by 1.

We have backtracked to new row(2+1)=3 col = 1

Step 1.3: c=1, r=3

B[3][1]=safe, increment column value by 1

Step 2.0: c=2, r=0

B[0][2]= unsafe, increment row by 1

Step 2.1: c=2, r=1

B[1][2]= safe, increment column value by 1 0 1 2 3

Step 3.0: c=3, r=0 Q - - -

0
B[0][3]=unsafe, increment row by 1
Q
Step 3.1: c=3, r=1 1

B[1][3] = unsafe, increment row by 1 2

Q
Step 3.2: c=3, r=2 3

B[2][3] = unsafe, increment row by 1

Step 3.3: c=3, r=3

B[3][3] = unsafe

We have reached the end of rows and columns but didn’t find safe place to position fourth queen.
Again backtrack and remive the last placed queen i.e., b[1][2]

Now set col=2 and row=2

Step 2.2: c=2, r=2

B[2][2]= unsafe, increment row by 1

Step 2.3: c=2, r=3

B[3][2]= unsafe.

Again backtrack as we cannot place the third queen in its position. Remove both the queens i.e.,
b[3][1] and b[0][0]. And increment the row value by 1 i.e., b[1][0]

Step 0.1: c=0, r=1

B[0][1] = safe, increment the column value by 1

Step 1.0: c=1, r=0

B[0][1] = unsafe, increment row value by 1

Step 1.1: c=1, r=1

B[1][1] = unsafe, increment row value by 1

Step 1.2: c=1, r=2

B[2][1] = unsafe, increment row value by 1 - - Q -

Step 1.3: c=1, r=3 Q - - -

B[3][1] = safe, place the queen and increment column
- - - Q
value by 1

Step 2.0: c=2, r=0 - Q - -

B[0][2] = safe, place the third queen and increment the value of column by 1

Step 3.0: c=3, r=0

B[0][3] = unsafe, increment the value of row by 1

Step 3.1: c=3, r=1

B[1][3] = unsafe, increment the value of row by 1

Step 3.2: c=3, r=2

B[2][3] = safe, place the fourth queen.

Finally, all the four queens are placed in safe positions

Matrix representation

0 0 1 0

1 0 0 0

0 0 0 1

0 1 0 0

Program for N-Queens Problem:

# include <stdio.h>

# include <conio.h>

# include <stdlib.h>

int x[10] = {5, 5, 5, 5, 5, 5, 5, 5, 5, 5};

place (int k)
{

int i;

for (i=1; i < k; i++)

if ((x [i] == x [k]) || (abs (x [i] – x [k]) == abs (i - k)))

return (0);

return (1);

nqueen (int n)

int m, k, i = 0;

x [1] = 0;

k = 1;

while (k > 0)

x [k] = x [k] + 1;

while ((x [k] <= n) && (!place (k)))

x [k] = x [k] +1;

if(x [k] <= n)

if (k == n)

else
}

else

k--;

i++;

printf (“\ncombination; %d\n”,i);

for (m=1;m<=n; m++)

printf(“row = %3d\t column=%3d\n”, m, x[m]);

getch();

k++;

x [k]=0;

return (0);

main ()

int n;

clrscr ();

printf (“enter value for N: “);

scanf (“%d”, &n);

nqueen (n);

Sum of Subsets
Subset sum problem is to find subset of elements that are selected from a given set whose sum
adds up to a given number K. The backtracking approach generates all permutations in the worst
case but in general, performs better than the recursive approach towards subset sum problem.

In Backtracking algorithm as we go down along depth of tree we add elements so far, and if the
added sum is satisfying explicit constraints, we will continue to generate child nodes further.
Whenever the constraints are not met, we stop further generation of sub-trees of that node, and
backtrack to previous node to explore the nodes not yet explored.We need to explore the nodes
along the breadth and depth of the tree. Generating nodes along breadth is controlled by loop and
nodes along the depth are generated using recursion.

1. Start with an empty set

2. Add the next element from the list to the set
3. If the subset is having sum M, then stop with that subset as solution.
4. If the subset is not feasible or if we have reached the end of the set, then backtrack
through the subset until we find the most suitable value.
5. If the subset is feasible (sum of seubset < M) then go to step 2.
6. If we have visited all the elements without finding a suitable subset and if no
backtracking is possible then stop without solution.

For example, n = 4, w = (11, 13, 24, 7) and m = 31, the desired subsets are

S1 = (11, 13, 7)

S2 = (24, 7)

State space tree will look like this

In the above tree which ever weight are included that edge will be written as 1 or will be written
as 0. I.e., xi = 0/1.

Problem: 1 2 3 4 5 6
W [1:6] = {5, 10, 12, 13, 15, 18} n = 6 and m = 30

As there are 6 weights there will be 7 level of state space tree and its height will be 6.

Total weight is 73

0, 73
x1=1

x2=1 5, 68

x3=1 15, 58 x3 = 0

27, 46 15, 46

x4=1(BT) x4=0 (BT) x4=1(BT) x4=0

40, 33 27, 33 28, 33 15, 33

backtrack x5=1(BT) x5=0(BT) x5 = 1(BT) x5=0(BT) x5=1

28, 18 30, 18 Sol1

42, 18 27, 18 43, 18
x6=1 (BT) x6=0 (BT) x6 = 1(BT) x6 = 0(BT)

45, 0 27, 0 46, 0 26, 0

Similarly find more solutions by backtracking to level 2

One subset that’s found is X1= {1, 1, 0, 0, 1, 0}

Graph Coloring

Graph coloring is the procedure of assignment of colors to each vertex of a graph G such that no
adjacent vertices get same color. The objective is to minimize the number of colors while
coloring a graph. The smallest number of colors required to color a graph G is called its
chromatic number of that graph. Graph coloring problem is a NP Complete problem.
The steps required to color a graph G with n number of vertices are as follows −

1. Arrange the vertices of the graph in some order.

2. Choose the first vertex and color it with the first color.
3. Choose the next vertex and color it with the lowest numbered color that has not been
colored on any vertices adjacent to it. If all the adjacent vertices are colored with this
color, assign a new color to it. Repeat this step until all the vertices are colored.

In the above figure, at first vertex a is colored red. As the adjacent vertices of vertex a are again
adjacent, vertex b and vertex d are colored with different color, green and blue respectively.
Then vertex c is colored as red as no adjacent vertex of c is colored red. Hence, we could color
the graph by 3 colors. Hence, the chromatic number of the graph is 3.

Applications of Graph Coloring

1. Register Allocation
2. Map Coloring
3. Bipartite Graph Checking
4. Mobile Radio Frequency Assignment
5. Making time table, etc.

Example:

Color the graph given below with minimum number of colors by backtracking using state space
tree.
Lets assume 1= red, 2= green and 3= blue