Disjoint Sets and Union and

Find Operations
Disjoint Sets - Introduction
• A tree is used to represent each set and the root to name a set
• Each node points upwards to its parent
• Two sets S1 and S2 are said to be disjoint if S1-S2 = Փ, i.e there is no
common elements in both S1 and S2
• A Collection of disjoint sets is called a disjoint set forest
• An array can be used to store parent of each element
Disjoint Sets - Introduction
• Example: When n=10, the element can be portioned into three disjoint
sets, S1 ={ 1,7,8,9 }, S2 = { 2,5,10 }and S3 = { 3,4,6}
Disjoint Sets - Operations
• Two important operations performed on disjoint sets
• Union: If Si and Sj are two disjoint sets, then their union SiU Sj=
all elements x such that x is in Si or Sj.Thus,,SiUS2 = {1,7,
8,9,2,5,10}Since we have assumed that all sets are disjoint, we can
assume that following the union of Si and Sj, the sets Si and Sj do
not exist independently; that is, they are replacedby SiU Sj in the
collection of sets.
• Find : Given the element i, find the set containing i. Thus, 4 is in
set S3,and 9 is in set S1.
Disjoint Sets – Operation Union
• IF S1 and S2 are two disjoint sets, their union S1 U S2 is a set of all
elements x such that x is in either S1 or S2
• As the sets should be disjoint S1 U S2 replace S1 and S2 which no
longer exist
• Union is achieved by simply making one of the trees as a subtree of
other i.e to set parent field of one of the roots of the trees to other root

or

Possible representation of S1 U S2
Disjoint Sets – Representation
• An array can be used to store parent of each element
• The ith element of this array represents the tree node that contains the
element i and it gives the parent of the element
• Root node has a parent -1
• An array P[1:n] can be taken for all n elements in the forest
• Element at the root node is taken as the name of the set
Disjoint Sets – Union and Find Algorithms
• Union(i, j):We passing two trees with roots
i and j. Adopting the convention that the first
tree becomes subtree of the second the
statement p[i] :=j;
• Find(i) : by following the indices, starting at i
until we reach a node with parent value -
1.For example, Find(6) start sat 6 and then
moves to 6'sparent,3. Since p[3] is negative,
we have reached the root
Disjoint Sets – Union and Find Algorithms
• In a worst case scenario SimpleUnion() and SimpleFind() perform
badly. Suppose we start with the single element sets {1}, {2}, {3} …
{n}, then execute the following sequence of union and find operations

• Union(1,2), Union(2,3), Union(3,4). …., Union(n-1,n)

• Find(1), Find(2), Find(3), …. Find(n)

• The total time needed to process the n finds is

Disjoint Sets – Weighted Union
• Simple Union leads to high time complexity in some cases
• Weighted union is a modified union algorithm with weighting rule
• Widely used to analyze the time complexity of an algorithm is average case
• Weighted union deals with making the smaller tree a subtree of the large
• If the no.of nodes in the tree with root i is less the no.of nodes in the tree
with root j, then make j the parent of i, otherwise make i the parent of j
• Count of nodes can be placed as a negative number in the P[i] value of the
root i.
Disjoint Sets – Weighted Union Algorithm
Disjoint Sets – CollapsingFind Algorithm
Collapsing Rule: 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].
UNIT IV:
Backtracking: General method, applications-n-queen problem, sum of subsets problem, graph
coloring, Hamiltonian cycles.
Branch and Bound: General method, applications - Travelling sales person problem,0/1
knapsack problem- LC Branch and Bound solution, FIFO Branch and Bound solution.

Backtracking (General method)

Many problems are difficult to solve algorithmically. Backtracking makes it possible to solve at
least some large instances of difficult combinatorial problems.
Suppose you have to make a series of decisions among various choices, where
 You don’t have enough information to know what to choose
 Each decision leads to a new set of choices.
 Some sequence of choices ( more than one choices) may be a solution to your problem.

Backtracking is a methodical (Logical) way of trying out various sequences of decisions, until
you find one that “works”
Example@1 (net example) : Maze (a tour puzzle)

Given a maze, find a path from start to finish.

 In maze, at each intersection, you have to decide between 3 or fewer choices:
 Go straight
 Go left
 Go right
 You don’t have enough information to choose correctly
 Each choice leads to another set of choices.
 One or more sequences of choices may or may not lead to a solution.
 Many types of maze problem can be solved with backtracking.

Example@ 2 (text book):

Sorting the array of integers in a[1:n] is a problem whose solution is expressible by an n-tuple
xi is the index in ‘a’ of the ith smallest element.
The criterion function ‘P’ is the inequality a[xi]≤ a[xi+1] for 1≤ i ≤ n
Si is finite and includes the integers 1 through n.
misize of set Si
m=m1m2m3---mn n tuples that possible candidates for satisfying the function P.
With brute force approach would be to form all these n-tuples, evaluate (judge) each one with P
and save those which yield the optimum.
By using backtrack algorithm; yield the same answer with far fewer than ‘m’ trails.
Many of the problems we solve using backtracking requires that all the solutions satisfy a
complex set of constraints.
For any problem these constraints can be divided into two categories:

DESIGN AND ANALYSIS OF ALGORITHMS Page 86

  Explicit constraints.
 Implicit constraints.

Explicit constraints: Explicit constraints are rules that restrict each xi to take on values only
from a given set.
Example: xi ≥ 0 or si={all non negative real numbers}
Xi=0 or 1 or Si={0, 1}
li ≤ xi ≤ ui or si={a: li ≤ a ≤ ui }
The explicit constraint depends on the particular instance I of the problem being solved. All
tuples that satisfy the explicit constraints define a possible solution space for I.
Implicit Constraints:
The 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 Xi must
relate to each other.
Applications of Backtracking:
 N Queens Problem
 Sum of subsets problem
 Graph coloring
 Hamiltonian cycles.

N-Queens Problem:
It is a classic combinatorial problem. The eight queen’s puzzle is the problem of placing eight
queens puzzle is the problem of placing eight queens on an 8×8 chessboard so that no two
queens attack each other. That is so that no two of them are on the same row, column, or
diagonal.
The 8-queens puzzle is an example of the more general n-queens problem of placing n queens on
an n×n chessboard.

Here queens can also be numbered 1 through 8

Each queen must be on a different row
Assume queen ‘i’ is to be placed on row ‘i’
All solutions to the 8-queens problem can therefore be represented a s s-tuples(x1, x2, x3—x8)
xi the column on which queen ‘i’ is placed
si{1, 2, 3, 4, 5, 6, 7, 8}, 1 ≤ i ≤8
Therefore the solution space consists of 88 s-tuples.
The implicit constraints for this problem are that no two xi’s can be the same column and no two
queens can be on the same diagonal.
By these two constraints the size of solution pace reduces from 88 tuples to 8! Tuples.
Form example si(4,6,8,2,7,1,3,5)

DESIGN AND ANALYSIS OF ALGORITHMS Page 87

In the same way for n-queens are to be placed on an n×n chessboard, the solution space consists
of all n! Permutations of n-tuples (1,2,----n).

Some solution to the 8-Queens problem

Algorithm for new queen be placed All solutions to the n·queens problem
Algorithm Place(k,i) Algorithm NQueens(k, n)
//Return true if a queen can be placed in kth // its prints all possible placements of n-
row & ith column queens on an n×n chessboard.
//Other wise return false {
{ for i:=1 to n do{
for j:=1 to k-1 do if Place(k,i) then
if(x[j]=i or Abs(x[j]-i)=Abs(j-k))) {
then return false X[k]:=I;
return true if(k==n) then write (x[1:n]);
} else NQueens(k+1, n);
}
}}

DESIGN AND ANALYSIS OF ALGORITHMS Page 88

Sum of Subsets Problem:
Given positive numbers wi 1 ≤ i ≤ n, & m, here sum of subsets problem is finding all subsets of
wi whose sums are m.
Definition: Given n distinct +ve numbers (usually called weights), desire (want) to find all
combinations of these numbers whose sums are m. this is called sum of subsets problem.
To formulate this problem by using either fixed sized tuples or variable sized tuples.
Backtracking solution uses the fixed size tuple strategy.

For example:
If n=4 (w1, w2, w3, w4)=(11,13,24,7) and m=31.
Then desired subsets are (11, 13, 7) & (24, 7).
The two solutions are described by the vectors (1, 2, 4) and (3, 4).

In general all solution are k-tuples (x1, x2, x3---xk) 1 ≤ k ≤ n, different solutions may have
different sized tuples.

 Explicit constraints requires xi ∈ {j / j is an integer 1 ≤ j ≤ n }

 Implicit constraints requires:
No two be the same & that the sum of the corresponding wi’s be m
i.e., (1, 2, 4) & (1, 4, 2) represents the same. Another constraint is xi<xi+1 1 ≤ i ≤ k

Wi weight of item i

DESIGN AND ANALYSIS OF ALGORITHMS Page 89
M Capacity of bag (subset)
Xi the element of the solution vector is either one or zero.
Xi value depending on whether the weight wi is included or not.
If Xi=1 then wi is chosen.
If Xi=0 then wi is not chosen.

The above equation specify that x1, x2, x3, --- xk cannot lead to an answer node if this condition
is not satisfied.

The equation cannot lead to solution.

Recursive backtracking algorithm for sum of subsets problem

Algorithm SumOfSub(s, k, r)
{

X[k]=1
If(S+w[k]=m) then write(x[1: ]); // subset found.
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]);
}
}

Graph Coloring:

DESIGN AND ANALYSIS OF ALGORITHMS Page 90

Let G be a undirected graph and ‘m’ be a given +ve integer. The graph coloring problem is
assigning colors to the vertices of an undirected graph with the restriction that no two adjacent
vertices are assigned the same color yet only ‘m’ colors are used.
The optimization version calls for coloring a graph using the minimum number of coloring.
The decision version, known as K-coloring asks whether a graph is colourable using at most k-
colors.
Note that, if ‘d’ is the degree of the given graph then it can be colored with ‘d+1’ colors.
The m- colorability optimization problem asks for the smallest integer ‘m’ for which the graph G
can be colored. This integer is referred as “Chromatic number” of the graph.
Example

 Above graph can be colored with 3 colors 1, 2, & 3.

 The color of each node is indicated next to it.
 3-colors are needed to color this graph and hence this graph’ Chromatic Number
is 3.
 A graph is said to be planar iff it can be drawn in a plane (flat) in such a way that no two
edges cross each other.
 M-Colorability decision problem is the 4-color problem for planar graphs.
 Given any map, can the regions be colored in such a way that no two adjacent regions
have the same color yet only 4-colors are needed?
 To solve this problem, graphs are very useful, because a map can easily be transformed
into a graph.
 Each region of the map becomes a node, and if two regions are adjacent, then the
corresponding nodes are joined by an edge.

o Example:

o
The above map requires 4 colors.
 Many years, it was known that 5-colors were required to color this map.
DESIGN AND ANALYSIS OF ALGORITHMS Page 91
  After several hundred years, this problem was solved by a group of mathematicians with
the help of a computer. They show that 4-colors are sufficient.
Suppose we represent a graph by its adjacency matrix G[1:n, 1:n]

Ex:

Here G[i, j]=1 if (i, j) is an edge of G, and G[i, j]=0 otherwise.

Colors are represented by the integers 1, 2,---m and the solutions are given by the n-tuple (x1,
x2,---xn)
xi Color of node i.

State Space Tree for

n=3 nodes
m=3colors

1st node coloured in 3-ways

2nd node coloured in 3-ways
3rd node coloured in 3-ways
So we can colour in the graph in 27 possibilities of colouring.

DESIGN AND ANALYSIS OF ALGORITHMS Page 92

 Finding all m-coloring of a graph Getting next color
Algorithm mColoring(k){ Algorithm NextValue(k){
// g(1:n, 1:n) boolean adjacency matrix. //x[1],x[2],---x[k-1] have been assigned
// kindex (node) of the next vertex to integer values in the range [1, m]
color. repeat {
repeat{ x[k]=(x[k]+1)mod (m+1); //next highest
nextvalue(k); // assign to x[k] a legal color. color
if(x[k]=0) then return; // no new color if(x[k]=0) then return; // all colors have
possible been used.
if(k=n) then write(x[1: n]; for j=1 to n do
else mcoloring(k+1); {
} if ((g[k,j]≠0) and (x[k]=x[j]))
until(false) then break;
} }
if(j=n+1) then return; //new color found
} until(false)
}

Previous paper example:

Adjacency matrix is

DESIGN AND ANALYSIS OF ALGORITHMS Page 93

Hamiltonian Cycles:
 Def: Let G=(V, E) be a connected graph with n vertices. A Hamiltonian cycle is a round
trip path along n-edges of G that visits every vertex once & returns to its starting
position.
 It is also called the Hamiltonian circuit.
 Hamiltonian circuit is a graph cycle (i.e., closed loop) through a graph that visits each
node exactly once.
 A graph possessing a Hamiltonian cycle is said to be Hamiltonian graph.
Example:

 In graph G, Hamiltonian cycle begins at some vertiex v1 ∈ G and the vertices

of G are visited in the order v1,v2,---vn+1, then the edges (vi, vi+1) are in E, 1 ≤ i ≤
n.

g1
The above graph contains Hamiltonian cycle: 1,2,8,7,6,5,4,3,1

The above graph contains no Hamiltonian cycles.

 There is no known easy way to determine whether a given graph contains a

Hamiltonian cycle.
 By using backtracking method, it can be possible
 Backtracking algorithm, that finds all the Hamiltonian cycles in a graph.
 The graph may be directed or undirected. Only distinct cycles are output.
 From graph g1 backtracking solution vector= {1, 2, 8, 7, 6, 5, 4, 3, 1}
 The backtracking solution vector (x1, x2, --- xn)
xi ith visited vertex of proposed cycle.

DESIGN AND ANALYSIS OF ALGORITHMS Page 94

  By using backtracking we need to determine how to compute the set of possible
vertices for xk if x1,x2,x3---xk-1 have already been chosen.
If k=1 then x1 can be any of the n-vertices.
By using “NextValue” algorithm the recursive backtracking scheme to find all Hamiltoman
cycles.
This algorithm is started by 1st initializing the adjacency matrix G[1:n, 1:n] then setting x[2:n]
to zero & x[1] to 1, and then executing Hamiltonian (2)
Generating Next Vertex Finding all Hamiltonian Cycles
Algorithm NextValue(k) Algorithm Hamiltonian(k)
{ {
// x[1: k-1] is path of k-1 distinct vertices. Repeat{
// if x[k]=0, then no vertex has yet been NextValue(k); //assign a legal next value to
assigned to x[k] x[k]
Repeat{ If(x[k]=0) then return;
X[k]=(x[k]+1) mod (n+1); //Next vertex If(k=n) then write(x[1:n]);
If(x[k]=0) then return; Else Hamiltonian(k+1);
If(G[x[k-1], x[k]]≠0) then } until(false)
{ }
For j:=1 to k-1 do if(x[j]=x[k]) then break;
//Check for distinctness
If(j=k) then //if true , then vertex is distinct
If((k<n) or (k=n) and G[x[n], x[1]]≠0))
Then return ;
}
}
Until (false);
}

Branch & Bound

Branch & Bound (B & B) is general algorithm (or Systematic method) for finding optimal
solution of various optimization problems, especially in discrete and combinatorial
optimization.
 The B&B strategy is very similar to backtracking in that a state space tree is used to solve
a problem.
 The differences are that the B&B method
 Does not limit us to any particular way of traversing the tree.
 It is used only for optimization problem
 It is applicable to a wide variety of discrete combinatorial problem.
 B&B is rather general optimization technique that applies where the greedy method &
dynamic programming fail.
 It is much slower, indeed (truly), it often (rapidly) leads to exponential time complexities
in the worst case.
 The term B&B refers to all state space search methods in which all children of the “E-
node” are generated before any other “live node” can become the “E-node”
 Live node is a node that has been generated but whose children have not yet been
generated.
 E-nodeis a live node whose children are currently being explored.

DESIGN AND ANALYSIS OF ALGORITHMS Page 95