3

10 4 6
UNIT II:
2
Disjoint set operations, union and find algorithms, AND/OR graphs, Connected Components and 1
Spanning trees, Bi-connected components.
Greedy method: General method, applications- Job sequencing with deadlines, Knapsack
9 problem,
Spanning trees, Minimum cost spanning trees, Single source shortest path problem.

Sets and Disjoint Set Union:

Disjoint Set Union: Considering a set S={1,2,3…10} (when n=10), then elements
can be partitioned into three disjoint sets s1={1,7,8,9},s2={2,5,10} and
s3={3,4,6}. Possible tree representations are:

5
1

/ \
7 8 9 2

In this representation each set is represented as a tree. Nodes are linked from the child
toparent rather than usual method of linking from parent to child.

The operations on these sets are:

1. Disjoint set union
2. Find(i)
3. Min Operation
4. Delete
5. Intersect
1. Disjoint Set union:
If Si and Sj are two disjoint sets, then their union Si U Sj = all the elements
X such that x is in Si or Sj. Thus S1 U S2 ={1,7,8,9,2,5,10}.
2. Find(i):
Given the element I, find the set containing i. Thus, 4 is in set S3, 9 is in S1.

UNION operation:
Union(i,j) requires two tree with roots i and j be joined. S1 U S2 isobtained by
making any one of the sets as sub tree of other.

1
5
9 5
7 8 1

2 1 7
8
 Simple Algorithm for Union:
Algorithm Union(i,j)
{
//replace the disjoint sets with roots i and j, I not equal to j by theirunion Integer
i,j;
P[j] :=i;
}

Example:
Implement following sequence of operations Union(1,3),Union(2,5),Union(1,2)
Solution:
Initially parent array contains zeros.

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

1. After performing union(1,3)operation Parent[3]:=1

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

2. After performing union(2,5)operation Parent[5]:=2

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

3. After performing union(1,2)operation Parent[2]:=1

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

3 2

5
Process the following sequence of union operations Union(1,2),Union(2,3) Union(n-1,n)
Degenerate Tree:

( n-1 )
\ /

The time taken for n-1 unions is O(n).

Find(i) operation: determines the root of the tree containing

element i. Simple Algorithm for Find:

Algorithm Find(i)

{
j:=i;
while(p[j]>0) do
j:=p[j]; return j;
}

Find Operation: Find(i) implies that it finds the root node of ith node, in other words it
returns the name of the set i.

Example: Consider the Union(1,3)

3
Find(1)=0
Find(3)=1, since its parent is 1. (i.e, root is 1)
Example:
Considering

3
2

5
Array Representation

P[i] 0 1 1 2
i 1 2 3 5

Find( 5 ) = 1
Find( 2 ) = 1
Find( 3 ) = 1
The root node represents all the nodes in the tree. Time Complexity of 、n’ find
operations is O(n 2 ) .
To improve the performance of union and find algorithms by avoiding the
creation of degenerate tree. To accomplish this, we use weighting rule for
Union(i,j).
Weighting Rule for Union(i,j)

Tree obtained with

 weighted Initially
1 2
n

1,2) 3 n
Union(
1

2
n
1 4
2
3

:
:
:

Union(1,n)

2 n
3 ·
Collapsing Rule for Find(i)
Spanning Trees:
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum
possible number of edges. Hence, a spanning tree does not have cycles and it cannot be
disconnected..

By this definition, we can draw a conclusion that every connected and undirected Graph G has
at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot
be spanned to all its vertices.

We found three spanning trees off one complete graph. A complete undirected graph can
have maximum nn-2number of spanning trees, where n is the number of nodes. In the above
addressed example, n is 3, hence 33-2 = 3spanning trees are possible.

GeneralPropertiesofSpanningTree
We now understand that one graph can have more than one spanning tree. Following are a
few properties of the spanning tree connected to graph G −
• A connected graph G can have more than one spanning tree.

• All possible spanning trees of graph G, have the same number of edges and vertices.

• The spanning tree does not have any cycle(loops).

• Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning
tree is minimally connected.

• Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is
maximally acyclic.
MathematicalPropertiesofSpanningTree
• Spanning tree has n-1 edges, where n is the number of nodes (vertices).

• From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.

• A complete graph can have maximum nn-2number of spanningtrees.

Thus, we can conclude that spanning trees are a subset of connected Graph G and
disconnected graphs do not have spanning tree.
ApplicationofSpanningTree
Spanning tree is basically used to find a minimum path to connect all nodes in a graph.
Common application of spanning trees are −
• Civil Network Planning

• Computer Network Routing Protocol

• Cluster Analysis

AND/OR GRAPH:

And/or graph is a specialization of hypergraph which connects nodes by sets of arcs rather
than by a single arcs. A hypergraph is defined as follows:
A hypergraph consists of: N, a set of nodes,

H, a set of hyperarcs defined by ordered pairs, in which the first implement of the pair is a node
of N and the second implement is the subset of N.

An ordinary graph is a special case of hypergraph in which all the sets of decendent nodes have
a cardinality of 1.

Hyperarcs also known as K-connectors, where K is the cardinality of the set of decendent nodes.
If K = 1, the descendent may be thought of as an OR nodes. If K > 1, the elements of the set
of decendents may be thought of as AND nodes. In this case the connector is drawn with
individual edges from the parent node to each of the decendent nodes; these individual edges are
then joined with a curved link. And/or graph for the expression P and Q -> R is follows:
The K-connector is represented as a fan of arrows with a single tie is shown above. The
and/or graphs consists of nodes labelled by global databases. Nodes labelled by compound
databases have sets of successor nodes. These successor nodes are called AND nodes, in
order to process the compound database to termination, all the compound databases must be
processed to termination. For example consider, consider a boy who collects stamps (M). He has
for the purpose ofexchange a winning conker (C), a bat (B) and a small toy animal (A). In his
class there are friends who are also keen collectors of different items and will make the following
exchanges.

1. 1 winning conker (C) for a comic (D) and a bag of sweets(S).

2. 1 winning conker (C) for a bat (B) and a stamp (M).

3. 1 bat (B) for two stamps (M, M).

4. 1 small toy animal (A) for two bats (B, B) and astamp (M).

The problem is how to carry out the exchanges so that all his exchangable items are converted
into stamps (M). This task can be expressed more briefly as:
1. Initial state = (C, B, A)

2. Transformation rules:
a. If C then (D, S)

b. If C then (B, M)

c. If B then (M, M)

d. IfA then (B, B, M)

3. The goal state is to left with only stamps (M,............. , M)

The figure shows that, a lot of extra work is done by redoing many of the transformations.This
repetition can be avoided by decomposing the problem into subproblems. There are two
major ways to order the components:

1. The components can either be arranged in some fixed order at the time they
are generated (or).

2. They can be dynamically reordered duringprocessing.

The more flexible system is to reorder dynamically as the processing unfolds. It can
be represented by and/or graph. The solution to the exchange problem will be:

Swap conker for a bat and a stamp, then exchange this bat for two stamps. Swap
hisown bat for two more stamps, and finally swap the small toy animal for two bats and a
stamp. The two bats can be exchanged for two stamps.
The previous exchange problem, when implemented as an and/or graph looks as follows:
Example 1:

Draw an AND/OR graph for the following prepositions:

1. A
2. B
3. C
4. A ^ B -> D
5. A ^ C -> E
6. B ^ D ->
F 7. F -> G
8. A ^ E -> H
 Connected components
In graph theory,a connected component (or just component) of an undirected
graphis a subgraph in which any two vertices are connected to each other by paths, and
which is connected to no additional vertices in the super graph. For example, the graph
shown in the illustration has three connected components. A vertex with no incident edges is
itself a connected component. A graph that is itself connected has exactly one connected

:>
component, consisting of the whole graph.

Biconnecte

o d
Component
s

A graph with three connected components.

Biconnected Components:
Let G = (V, E) be a connected undirected graph. Consider the following definitions:

Articulation Point (or Cut Vertex): An articulation point in a connected graph is

a vertex (together with the removal of any incident edges) that, if deleted, would break
the graph into two or more pieces..

Bridge: Is an edge whose removal results in a disconnected graph.

Biconnected: A graph is biconnected if it contains no articulation points. In a

biconnected graph, two distinct paths connect each pair of vertices. A graph that is
not biconnected divides into biconnected components. This is illustrated in the
following figure:
Articulation Points and Bridges

Articulation Point
Bridge
 DESIGN AND ANALYSIS OF ALGORITHM AY:2023-24

Biconnected graphs and articulation points are of great interest in thedesign of

network algorithms,
because these are the “critical" points, whose failure will result in
thenetwork becoming disconnected.
2 1
Let us consider the typical case of vertex v, where v is not a leaf and v is not the root.
Let w1, w2, . . . . . . . wk be the children of v. For each child there is a subtree of the DFS
tree rooted at this child. If for some child, there is no back edge 9going to a proper
ancestor of v, then if we remove v, this subtree becomes disconnected from the rest of
the graph, and hence vis an articulation point.

L (u) = min {DFN (u), min {L (w) l w is a child of u}, min {DFN
(w) | (u, w) is a back edge}}.

L (u) is the lowest depth first number that can be reached from ‘u’ using a path
of descendents followed by at most one back edge. It follows that, If ‘u’ is not the root
then ‘u’ is an articulation point iff ‘u’ has a child ‘w’ such that:

L (w) ≥ DFN (u)

Algorithm for finding the Articulation points:

Pseudocode to compute DFN and L.

Algorithm Art (u, v)

// u is a start vertex for depth first search. V is its parent if any in the depth first
// spanning tree. It is assumed that the global array dfn is initialized to zero and that
// the global variable num is initialized to 1. n is the number of vertices in G.
{
dfn [u]: = num; L [u]: = num;
num: = num + 1; for each vertex wadjacent from u do
{
if (dfn [w] = 0) then
{

1
5
9 5
7 8 1

2 1 7
8
 Simple Algorithm for Union:
Algorithm Union(i,j)
{
//replace the disjoint sets with roots i and j, I not equal to j by theirunion Integer
i,j;
P[j] :=i;
}

Example:
Implement following sequence of operations Union(1,3),Union(2,5),Union(1,2)
Solution:
Initially parent array contains zeros.

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

1. After performing union(1,3)operation Parent[3]:=1

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

2. After performing union(2,5)operation Parent[5]:=2

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

3. After performing union(1,2)operation Parent[2]:=1

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

3 2

5
Process the following sequence of union operations Union(1,2),Union(2,3) Union(n-1,n)
Degenerate Tree:

( n-1 )
\ /

The time taken for n-1 unions is O(n).

Find(i) operation: determines the root of the tree containing

element i. Simple Algorithm for Find:

Algorithm Find(i)

{
j:=i;
while(p[j]>0) do
j:=p[j]; return j;
}

Find Operation: Find(i) implies that it finds the root node of ith node, in other words it
returns the name of the set i.

Example: Consider the Union(1,3)

3
Find(1)=0
Find(3)=1, since its parent is 1. (i.e, root is 1)
Example:
Considering

3
2

5
Array Representation

P[i] 0 1 1 2
i 1 2 3 5

Find( 5 ) = 1
Find( 2 ) = 1
Find( 3 ) = 1
The root node represents all the nodes in the tree. Time Complexity of 、n’ find
operations is O(n 2 ) .
To improve the performance of union and find algorithms by avoiding the
creation of degenerate tree. To accomplish this, we use weighting rule for
Union(i,j).
Weighting Rule for Union(i,j)

Tree obtained with

 weighted Initially
1 2
n

Union(1,2)
3 n
1

2
Union(1,3)

n
1 4
2
3

:
:
:

Union(1,n)

2 n
3 ·
Collapsing Rule for Find(i)
Spanning Trees:
A spanning tree is a subset of Graph G, which has all the vertices covered with minimum
possible number of edges. Hence, a spanning tree does not have cycles and it cannot be
disconnected..

By this definition, we can draw a conclusion that every connected and undirected Graph G has
at least one spanning tree. A disconnected graph does not have any spanning tree, as it cannot
be spanned to all its vertices.

We found three spanning trees off one complete graph. A complete undirected graph can
have maximum nn-2number of spanning trees, where n is the number of nodes. In the above
addressed example, n is 3, hence 33-2 = 3spanning trees are possible.

GeneralPropertiesofSpanningTree
We now understand that one graph can have more than one spanning tree. Following are a
few properties of the spanning tree connected to graph G −
• A connected graph G can have more than one spanning tree.

• All possible spanning trees of graph G, have the same number of edges and vertices.

• The spanning tree does not have any cycle(loops).

• Removing one edge from the spanning tree will make the graph disconnected, i.e. the spanning
tree is minimally connected.

• Adding one edge to the spanning tree will create a circuit or loop, i.e. the spanning tree is
maximally acyclic.
MathematicalPropertiesofSpanningTree
• Spanning tree has n-1 edges, where n is the number of nodes (vertices).

• From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.

• A complete graph can have maximum nn-2number of spanningtrees.

Thus, we can conclude that spanning trees are a subset of connected Graph G and
disconnected graphs do not have spanning tree.
ApplicationofSpanningTree
Spanning tree is basically used to find a minimum path to connect all nodes in a graph.
Common application of spanning trees are −
• Civil Network Planning

• Computer Network Routing Protocol

• Cluster Analysis

AND/OR GRAPH:

And/or graph is a specialization of hypergraph which connects nodes by sets of arcs rather
than by a single arcs. A hypergraph is defined as follows:
A hypergraph consists of: N, a set of nodes,

H, a set of hyperarcs defined by ordered pairs, in which the first implement of the pair is a node
of N and the second implement is the subset of N.

An ordinary graph is a special case of hypergraph in which all the sets of decendent nodes have
a cardinality of 1.

Hyperarcs also known as K-connectors, where K is the cardinality of the set of decendent nodes.
If K = 1, the descendent may be thought of as an OR nodes. If K > 1, the elements of the set
of decendents may be thought of as AND nodes. In this case the connector is drawn with
individual edges from the parent node to each of the decendent nodes; these individual edges are
then joined with a curved link. And/or graph for the expression P and Q -> R is follows:
The K-connector is represented as a fan of arrows with a single tie is shown above. The
and/or graphs consists of nodes labelled by global databases. Nodes labelled by compound
databases have sets of successor nodes. These successor nodes are called AND nodes, in
order to process the compound database to termination, all the compound databases must be
processed to termination. For example consider, consider a boy who collects stamps (M). He has
for the purpose ofexchange a winning conker (C), a bat (B) and a small toy animal (A). In his
class there are friends who are also keen collectors of different items and will make the following
exchanges.

1. 1 winning conker (C) for a comic (D) and a bag of sweets(S).

2. 1 winning conker (C) for a bat (B) and a stamp (M).

3. 1 bat (B) for two stamps (M, M).

4. 1 small toy animal (A) for two bats (B, B) and astamp (M).

The problem is how to carry out the exchanges so that all his exchangable items are converted
into stamps (M). This task can be expressed more briefly as:
1. Initial state = (C, B, A)

2. Transformation rules:
a. If C then (D, S)

b. If C then (B, M)

c. If B then (M, M)

d. IfA then (B, B, M)

3. The goal state is to left with only stamps (M,............. , M)

The figure shows that, a lot of extra work is done by redoing many of the transformations.This
repetition can be avoided by decomposing the problem into subproblems. There are two
major ways to order the components:

1. The components can either be arranged in some fixed order at the time they
are generated (or).

2. They can be dynamically reordered duringprocessing.

The more flexible system is to reorder dynamically as the processing unfolds. It can
be represented by and/or graph. The solution to the exchange problem will be:

Swap conker for a bat and a stamp, then exchange this bat for two stamps. Swap
hisown bat for two more stamps, and finally swap the small toy animal for two bats and a
stamp. The two bats can be exchanged for two stamps.
The previous exchange problem, when implemented as an and/or graph looks as follows:
Example 1:

Draw an AND/OR graph for the following prepositions:

1. A
2. B
3. C
4. A ^ B -> D
5. A ^ C -> E
6. B ^ D ->
F 7. F -> G
8. A ^ E -> H
Connected components
In graph theory,a connected component (or just component) of an undirected
graphis a subgraph in which any two vertices are connected to each other by paths, and
which is connected to no additional vertices in the super graph. For example, the graph
shown in the illustration has three connected components. A vertex with no incident edges is
itself a connected component. A graph that is itself connected has exactly one connected
component, consisting of the whole graph.

A graph with three connected components.

Biconnected Components:
Let G = (V, E) be a connected undirected graph. Consider the following definitions:

Articulation Point (or Cut Vertex): An articulation point in a connected graph is

a vertex (together with the removal of any incident edges) that, if deleted, would break
the graph into two or more pieces..

Bridge: Is an edge whose removal results in a disconnected graph.

Biconnected: A graph is biconnected if it contains no articulation points. In a

biconnected graph, two distinct paths connect each pair of vertices. A graph that is
not biconnected divides into biconnected components. This is illustrated in the
following figure:
DESIGN AND ANALYSIS OF ALGORITHM AY:2023-24

Articulation Points and Bridges

Biconnected graphs and articulation points are of great interest in thedesign

of network algorithms,
because these are the “critical" points, whose failure will result in thenetwork
becoming disconnected.

Let us consider the typical case of vertex v, where v is not a leaf and v is not the root.
Let w1, w2, . . . . . . . wk be the children of v. For each child there is a subtree of the DFS
tree rooted at this child. If for some child, there is no back edge going to a proper ancestor
of v, then if we remove v, this subtree becomes disconnected from the rest of the graph,
and hence vis an articulation point.

L (u) = min {DFN (u), min {L (w) l w is a child of u}, min {DFN
(w) | (u, w) is a back edge}}.

L (u) is the lowest depth first number that can be reached from ‘u’ using a path
of descendents followed by at most one back edge. It follows that, If ‘u’ is not the root
then ‘u’ is an articulation point iff ‘u’ has a child ‘w’ such that:

L (w) ≥ DFN (u)

Algorithm for finding the Articulation points:

Pseudocode to compute DFN and L.

Algorithm Art (u, v)

// u is a start vertex for depth first search. V is its parent if any in the depth first
// spanning tree. It is assumed that the global array dfn is initialized to zero and that
// the global variable num is initialized to 1. n is the number of vertices in G.
{
dfn [u]: = num; L [u]: = num;
num: = num + 1; for each vertex wadjacent from u do
{
if (dfn [w] = 0) then
{
Backtracking: General method, Applications- n-queue problem, Sum of subsets problem,
Graph coloring, Hamiltonian cycles.

BACKTRACKING

General Method:

Backtracking is used to solve problem in which a sequence of objects is chosen from

a specified set so that the sequence satisfies some criterion. The desired solution
is expressed as an n-tuple (x1, , xn) where each xi Є S, S being a finite set.

The solution is based on finding one or more vectors that maximize, minimize, or satisfy
a criterion function P (x1, , xn). Form a solution and check at every step
if this has any chance of success. If the solution at any point seems not promising,
ignore it. All solutions requires a set of constraints divided into two categories: explicit
and implicit constraints.

Definition 1: Explicit constraints are rules that restrict each xi to take on values only
from a given set. Explicit constraints depend on the particular instance Iof
problem being solved. All tuples that satisfy the explicit constraints
define a possible solution space for I.

Definition 2: 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’s must relate to each other.

• For 8-queens problem:

Explicit constraints using 8-tuple formation, for this problem are S= {1, 2, 3, 4,
5, 6, 7, 8}.

The implicit constraints for this problem are that no two queens can be the
same (i.e., all queens must be on different columns) and no two queens can be
on the same diagonal.

Backtracking is a modified depth first search of a tree. Backtracking algorithms

determine problem solutions by systematically searching the solution space for the
given problem instance. This search is facilitated by using a tree organization for
the solution space.

Backtracking is the procedure whereby, after determining that a node can lead to
nothing but dead end, we go back (backtrack) to the nodes parent and proceed with the
search on the next child.

A backtracking algorithm need not actually create a tree. Rather, it only needs to
keep track of the values in the current branch being investigated. This is the way
we implement backtracking algorithm. We say that the state space tree exists
implicitly in the algorithm because it is not actuallyconstructed.

State space is the set of paths from root node to other nodes. State space tree is
the tree organization of the solution space. The state space trees are called static trees.
This terminology follows from the observation that the tree organizations are
independent of the problem instance being solved. For some problems it is
advantageous to use different tree organizations for different problem instance.
In this case the tree organization is determined dynamically as the solution space
is being searched. Tree organizations that are problem instance dependent are called
dynamic trees.
 Terminology:

Problem state is each node in the depth first search tree.

Solution states are the probIem states 、S’ for which the path from the root
node to 、S’ defines a tupIe in the soIution space.

Answer states are those solution states for which the path from root
node to s defines a tuple that is a member of theset of solutions.

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. In other
words, an E-node is a node currently being expanded.

Dead node is a generated node that is not to be expanded or explored any further.
All children of a dead node have already been expanded.

Branch and Bound refers to all state space search methods in which all
children of an E-node are generated before any other live node can become
theE-node.

Depth first node generation with bounding functions is called backtracking.

State generation methods in which the E-node remains the E-node until it is
dead, lead to branch and bound methods.

N-Queens Problem:

Let us consider, N = 8. Then 8-Queens Problem is to place eight queens on an

8 x 8 chessboard so that no two “attack”, that is, no two of them are on
the same row, column, or diagonal.
All solutions to the 8-queens problem can be represented as 8-tuples (x 1 , . . .
. , x 8 ), where x i is the column of the i th row where the i th queen is placed.
The explicit constraints using this formulation are S i = {1, 2, 3, 4, 5, 6, 7, 8}, 1 < i <
8. Therefore the solution space consists of 8 8 8-tuples.

The implicit constraints for this problem are that no two x i ’s can be the same
(i.e., aII queens must be on different columns) and no two queens can be
on the same diagonal.
This realization reduces the size of the solution space from 8 8 tuples to 8! Tuples.

The promising function must check whether two queens are in the same
column or diagonal:
Suppose two queens are placed at positions (i, j) and (k, l) Then:

• Column Conflicts: Two queens conflict if their x i values are identical.

• Diag 45 conflict: Two queens i and j are on the same 45 0 diagonal if:

i - j = k - l.

This implies, j - l = i - k
• Diag 135 conflict:
i + j = k + l. This implies, j - l = k - i
Therefore, two queens lie on the same diagonal if and only if:
Ij - l I = Ii – k I

Where, j be the column of object in row i forth the i th queen and l be the
column of object in row 、k’ for the k queen.

To check the diagonal clashes, let us take the following tile configurati on:

*
In this example, we
* have:
*
i 1 2 3 4 5 6 7 8
*
* xi 2 5 1 8 4 7 3 6
*

* Letrdus considerthfor the

case whether the queens on 3 row and 8 row
* are conflicting or not. In this
case (i, j) = (3, 1) and (k, l) = (8, 6). Therefore:
Ij - l I = Ii – k I → I 1 - 6 I = I3 – 8 I
→5 = 5

In the above example we have, Ij - l I = Ii – k I, so the two queens are

attacking. This is not a solution.

Example:

Suppose we start with the feasible sequence 7, 5, 3, 1.

*
*
*
*

Step 1:
Add to the sequence the next number in the sequence 1, 2, . . . , 8
not yet used.
Step 2:
If this new sequence is feasible and has length 8 then STOP with a
solution. If the new sequence is feasible and has length less then 8,
repeat Step 1.

Step 3:
If the sequence is not feasible, then backtrack through the sequence
until we find the most recent place at which we can exchange a value.
Go back to Step 1.
 Remarks
1 2 3 4 5 6 7 8

7 5 3 1
lj - ll = l 1 - 2 l = 1
7 5 3 1* 2* li - k l = l4 - 5 l = 1
7 5 3 1 4
lj - ll = l7 - 2 l = 5
7* 5 3 1 4 2* li - k l= l1 -6l= 5
lj - ll = l3 - 6 l = 3
7 5 3* 1 4 6* li - k l = l3 - 6 l = 3
7 5 3 1 4 8
lj - ll = l4 - 2 l = 2
7 5 3 1 4* 8 2* li - k l = l5 - 7 l = 2
lj - ll = l4 - 6 l = 2
7 5 3 1 4* 8 6* li - k l = l5 - 7 l = 2
7 5 3 1 4 8 Backtrack
7 5 3 1 4 Backtrack
7 5 3 1 6
lj - ll = l 1 - 2 l = 1
7* 5 3 1 6 2* li - k l = l7 - 6 l = 1
7 5 3 1 6 4
7 5 3 1 6 4 2
lj - ll = l3 - 8 l = 5
7 5 3* 1 6 4 2 8* li - k l = l3 - 8 l = 5
7 5 3 1 6 4 2 Backtrack
7 5 3 1 6 4 Backtrack
7 5 3 1 6 8
7 5 3 1 6 8 2
7 5 3 1 6 8 2 4 SOLUTION

* indicates conflicting queens.

On a chessboard, the solution will look like:

*
*
*
*
*
*
*
*
 1 1 1
1 1 1
. . 2 2
. . . 2 2
. . .
3
. . 4
4 - Queens Problem:

Let us see how backtracking works on the 4-queens problem. We start with the root
node as the only live node. This becomes the E-node. We generate one child. Let us
assume that the children are generated in ascending order. Let us assume that
the children are generated in ascending order. Thus node number 2 of figure is
generated and the path is now (1). This corresponds to placing queen 1 on column
1. Node 2 becomes the E-node. Node 3 is generated and immediately killed. The
next node generated is node 8 and the path becomes (1, 3). Node 8 becomes
the E-node. However, it gets killed as all its children represent board configurations
that cannot lead to an answer node. We backtrack to node 2 and generate another
child, node 13. The path is now (1, 4). The board configurations as backtracking
proceeds is as follows:

1
2

. 3

(a) (b) (c) (d)

1
2
3

. . . .
(e) (f) (g) (h)

The above figure shows graphically the steps that the backtracking algorithm
goes through as it tries to find a solution. The dots indicate placements of a queen,
which were tried and rejected because another queen was attacking.

In Figure (b) the second queen is placed on columns 1 and 2 and finally settles on
column 3. In figure (c) the algorithm tries all four columns and is unable to place the
next queen on a square. Backtracking now takes place. In figure (d) the second
queen is moved to the next possible column, column 4 and the third queen is
placed on column 2. The boards in Figure (e), (f), (g), and (h) show the remaining
steps that the algorithm goes through until a solution is found.
Complexity Analysis:
= nn +1 − 1
1 + n + n +n +□+ n
2 3 n n− 1
 5

For the instance in which

6 7n = 8,
8 the state space tree contains:

x3 =4 x3 =4
= 19, 173,
13
961 nodes
14 S

Sum of Subsets:
Given positive numbers wi, 1 ≤ i ≤ n, and m, this probIem requires finding aII
subsets of wi whose sums are 、m,.
All solutions are k- tupIes, 1 ≤ k ≤ n .

Explicit constraints:
• x i Є {j I j is an integer and 1 ≤ j ≤n}.

Implicit constraints:

• No two x i can be the same.

• The sum of the corresponding w i ,s be m.
• x i < x i+1 , 1 ≤ i < k (totaI order in indices) to avoid generating
muItipIe instances of the same subset (for example, (1, 2, 4)
and (1, 4, 2) represent the same subset).

A better formulation of the problem is where the solution subset is

represented by an n-tuple (x 1 , , x n ) such that x i Є {0,1}.

The above solutions are then represented by (1, 1, 0, 1) and (0,

0, 1, 1). For both the above formulations, the solution space is 2 n
distincttuples.
For example, n = 4 , w = ( 1 1 , 1 3 , 2 4 , 7 ) and m = 3 1 , the desired subsets are( 1 1 ,
13, 7) and (24, 7).
The following figure shows a possible tree organization for two possible
formulations of the solution space for the case n = 4.
1
x1
=1 x 1 = 2 /
x1 =3
x1
=4
2 3 4
x2 =2 x 2 =4 x 2
x2 =4
x2 =3 =3 x2
10 =4
x 3 =3 9 11
x 3 S
1
15
2x 4 =4
=4
16

A p o s s ib le s o lut io n s p ac e org a n is at io n f or t h e
su m of t he s u b set s pro ble m.

The tree corresponds to the variable tuple size formulation. The edges are
labeled such that an edge from a level i node to a level i+1 node represents a
value for x i . At each node, the solution space is partitioned into sub - solution
spaces. All paths from the root node to any node in the tree define the
solution space, since any such path corresponds to a subset satisfying the
explicit constraints.
The possible paths are (1), (1, 2), (1, 2, 3), (1, 2, 3, 4), (1, 2, 4), (1, 3, 4), (2), (2, 3),
and so on. Thus, the left mot sub-tree defines all subsets containing w1, the next
sub-tree defines all subsets containing w2 but not w1, and so on.
Graph Coloring (for planar graphs):

Let G be a graph and m be a given positive integer. We want to discover whether

the nodes of G can be colored in such a way that no two adjacent nodes have the
same color, yet only m colors are used. This is termed the m-colorabiltiy decision
problem. The m-colorability optimization problem asks for the smallest integer m for
which the graph G can be colored.

Given any map, if the regions are to be colored in such a way that no two
adjacent regions have the same color, only four colors are needed.

For many years it was known that five colors were sufficient to color any map, but no
map that required more than four colors had ever been found. After several
hundred years, this problem was solved by a group of mathematicians with the
help of a computer. They showed that in fact fourcolors are sufficient for planar
graphs.

The function m-coloring will begin by first assigning the graph to its adjacency matrix,
setting the array x [] to zero. The colors are represented by the integers 1, 2, . . . , m
and the solutions are given by the n-tuple (x1, x2, . . ., xn), where xi is the color of
node i.

A recursive backtracking algorithm for graph coloring is carried out by invoking

the statement mcoloring(1);

Algorithm mcoloring (k)

// This algorithm was formed using the recursive backtracking schema. The graph is
// represented by its Boolean adjacency matrix G [1: n, 1: n]. All assignments of
// 1, 2,.......... , m to the vertices of the graph such that adjacent vertices areassigned
// distinct integers are printed. k is the index of the next vertex to color.
{
repeat
{ // Generate all legal assignments for x[k].
NextValue (k); // Assign to x [k] a legal color.
If (x [k] = 0) then return; // No new color possible
If (k = n) then // at most m colors have been
// used to color the n vertices.
write (x [1: n]);
else mcoloring (k+1);
} until (false);
}

Algorithm NextValue (k)

// x [1] ,.........x [k-1] have been assigned integer values in the range [1, m] such that
// adjacent vertices have distinct integers. A value for x [k] is determined in the range
// [0, m].x[k] is assigned the next highest numbered color while maintaining distinctness
// from the adjacent vertices of vertex k. If no such color exists, then x [k] is 0.
{
repeat
{

x [k]: = (x [k] +1) mod (m+1) // Next highest color.

If (x [k] = 0) then return; // All colors have been used
for j := 1 to ndo
{ // check if this color is distinct from adjacent colors
if ((G [k, j] ≠ 0) and (x [k] = x [j]))
// If (k, j) is and edge and if adj. vertices have the same color.
then break;
 x1
1 3
2

O x2
2 3 3 1 2

O O O
} 1 / 3 1 2
if (j = n+1) then return;
2 3 1
2
// New color
5
/\ 3
found
O
3 /
1
x3

} until (false); // Otherwise try to find another color. x4

} 3 1 \ 2

Example:

Color the graph given below with minimum number of colors by

backtracking using state space tree

1 1
2

2
4 3
Gra p h

O/ O
\ 2 2 3 3 1 3 1 3 1 3 1 1 2 2
2

A 4- n o d e gra p h a n d a l l p o s s ib le 3-c o lorin gs

Hamiltonian Cycles:

Let G = (V, E) be a connected graph with n vertices. A Hamiltonian cycle

(suggested by William Hamilton) is a round-trip path along n edges of G
that visits every vertex once and returns to its starting position. In other
vertices of G are visited in the order v1, v2, . . . . . , vn+1, then the edges
(vi, vi+1) are in E, 1 < i < n, and the vi are distinct expect for v1 and vn+1,
which are equal. The graph G1 contains the Hamiltonian cycle 1, 2, 8, 7, 6,
5, 4, 3, 1. The graph G2 contains no Hamiltonian cycle.

1 2 3 4 1 2 3

8 7 6 5 4

Graph G1 Graph G2

Two graphs to illustrate Hamiltonian cycle

The backtracking solution vector (x1, . . . . . xn) is defined so that xi

represents the ith visited vertex of the proposed cycle. If k = 1, then x1 can
be any of the n vertices. To avoid printing the same cycle n times, we
require that x1 = 1. If 1 < k < n, then xk can be any vertex v that is
distinct from x1, x2, . . . , xk-1 and v is connected by an edge to kx-1 . The