UNIT – 6

Exploring graphs

Prepared by : Prof. Madhuri Vaghasia 1

 COMING UP!!
• An introduction using graphs
• Traversing Trees –Preconditioning
• Depth First Search -Undirected Graph
• Depth First Search -Directed Graph
• Topological sorting
• Breadth First Search
• Backtracking
• The general template
• The Knapsack Problem using backtracking
• The Eight queens problem
Prepared by : Prof. Madhuri Vaghasia 2
An introduction using graphs
• There are two standard ways to represent a graph G = (V, E): as
a collection of adjacency lists or as an adjacency matrix. Either
way is applicable to both directed and undirected graphs.

• The adjacency-list representation is usually preferred, because

it provides a compact way to represent sparse graphs-those for
which |E| is much less than |V|∧2.

• An adjacency-matrix representation may be preferred,

however, when the graph is dense-|E| is close to |V|∧2-or
when we need to be able to tell quickly if there is an edge.

Prepared by : Prof. Madhuri Vaghasia 3

An introduction using graphs and
games
• Two representations of an undirected graph. (a)
An undirected graph G having five vertices and
seven edges. (b) An adjacency-list representation
of G. (c) The adjacency matrix representation of
G.

Prepared by : Prof. Madhuri Vaghasia 4

An introduction using graphs and
games
• Two representations of a directed graph. (a) A
directed graph G having six vertices and eight
edges. (b) An adjacency-list representation of G.
(c) The adjacency-matrix representation of G.

Prepared by : Prof. Madhuri Vaghasia 5

Traversing Trees – Preconditioning
• We all know about Tree and Binary Tree

• We can traverse Binary Tree in following manners

– Preorder - Root  Left  Right
– Inorder – Left  Root  Right
– Postorder – Left  Right  Root

• Preorder and Postorder generalize in an obvious way to non binary trees.

• These three techniques explore the tree from left to right. Three
corresponding techniques explore the tree from right to left.

• Implementation of any of these techniques using recursion is

straightforward.
Prepared by : Prof. Madhuri Vaghasia 6
Traversing Trees – Preconditioning
• Preconditioning –

– If we have to solve several similar instances of the same

problem, it may be worthwhile to invest some time in
calculating auxiliary results that can thereafter be used to
speed up the solution of each instance. This is Preconditioning.

– Informally, let a be the time it takes to solve a typical instance

when no auxiliary information is available, let b the time it
takes to solve a typical instance when auxiliary information is
available, and let p be the time needed to calculate this extra
information.

Prepared by : Prof. Madhuri Vaghasia 7

Traversing Trees – Preconditioning
• Preconditioning –

– To solve n typical instances takes time na without preconditioning

and time p + nb if preconditioning is used.

– Provided b < a, it is advantageous to use preconditioning when n >

p/(a-b).

– From this point of view, the dynamic programming algorithm for

making change gives an example of preconditioning.

– Once the necessary values have been calculated, we can make

change quickly whenever this is required.
Prepared by : Prof. Madhuri Vaghasia 8
Traversing Trees – Preconditioning
• Preconditioning –

– Even when there are few instances to be solved, pre

computation of auxiliary information may be useful.

– Suppose we occasionally have to solve one instance

from some large set of possible instances.

– When a solution is needed it must be provided very

rapidly, for example to ensure sufficiently fast response
for a real time application.
Prepared by : Prof. Madhuri Vaghasia 9
Traversing Trees – Preconditioning
• Preconditioning –

– As a second example of this technique we use the

problem of determining ancestry in a rooted tree. Let T
be a rooted tree, not necessarily binary.

– We say that a node v of T is an ancestor of node w if v

lies on the path from w to the root of T.

– In particular, every node is its own ancestor and the root

is an ancestor of every node.
Prepared by : Prof. Madhuri Vaghasia 10
Traversing Trees – Preconditioning
• Preconditioning –

– The problem is thus, given a pair of nodes (v, w) from T,

to determine whether or not v is an ancestor of w.

– If T contains n nodes, any direct solution of this instance

takes a time in O(n).

– However it is possible to precondition T in a time of

O(n) so we can subsequently solve any particular
instance of the ancestry problem in constant time.
Prepared by : Prof. Madhuri Vaghasia 11
Traversing Trees – Preconditioning
• Preconditioning –

– To precondition the tree, we traverse it first in

preorder and then in postorder, numbering the nodes
sequentially as we visit them.

– For a node v, let prenum[v] be the number assigned to

v when we traverse the tree in preorder, and let
postnum[v] be the number assigned during the
traversal in postorder.

Prepared by : Prof. Madhuri Vaghasia 12

Traversing Trees – Preconditioning
• Preconditioning –

– Let v and w be two nodes in the tree. In preorder we first number a node and
then number its subtress from left to right. Thus
• If prenum[v] <= prenum[w] then v is an ancestor of w OR v is to the left of w in the tree.

– In postorder we first number the subtrees of a node from left to right, and then
we number the node itself. Thus
• If postnum[v] >= postnum[w] then v is an ancestor of w OR v is to the right of w in the
tree.

– It follows that
• If prenum[v] <= prenum[w] and postnum[v] >= postnum[w] then v is an ancestor of w.

• Once the values of prenum and postnum have been calculated in a time in Θ(n), the
required condition can be checked in a time in Θ(1).
Prepared by : Prof. Madhuri Vaghasia 13
 Breadth-first searching
• A breadth-first search (BFS)
A explores nodes nearest the
root before exploring nodes
B C
further away
• For example, after searching
A, then B, then C, the search
D E F G
proceeds with D, E, F, G
• Node are explored in the
H I J K order A B C D E F G H I J K L
MNOPQ
L M N O P Q • J will be found before N

Prepared by : Prof. Madhuri Vaghasia 15

 Breadth-First Search
• Again will associate vertex “colors” to guide the
algorithm
– White vertices have not been discovered
• All vertices start out white
– Grey vertices are discovered but not fully explored
• They may be adjacent to white vertices
– Black vertices are discovered and fully explored
• They are adjacent only to black and gray vertices
• Explore vertices by scanning adjacency list of grey
vertices
Prepared by : Prof. Madhuri Vaghasia 16
Breadth-First Search: Example
r s t u

   

   
v w x y

Prepared by : Prof. Madhuri Vaghasia 17

Breadth First Search
r s t u

 0  

   
v w x y

Q: Ss

Prepared by : Prof. Madhuri Vaghasia 18

Breadth First Search
r s t u

1 0  

 1  
v w x y

Q: w r

Prepared by : Prof. Madhuri Vaghasia 19

Breadth First Search
r s t u

1 0 2 

 1 2 
v w x y

Q: r t x

Prepared by : Prof. Madhuri Vaghasia 20

Breadth First Search
r s t u

1 0 2 

2 1 2 
v w x y

Q: t x v

Prepared by : Prof. Madhuri Vaghasia 21

Breadth First Search
r s t u

1 0 2 3

2 1 2 
v w x y

Q: x v u

Prepared by : Prof. Madhuri Vaghasia 22

Breadth First Search
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: v u y

Prepared by : Prof. Madhuri Vaghasia 23

Breadth First Search
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: u y

Prepared by : Prof. Madhuri Vaghasia 24

Breadth First Search
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: y

Prepared by : Prof. Madhuri Vaghasia 25

Breadth First Search
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: Ø

Prepared by : Prof. Madhuri Vaghasia 26

Example using BFS

Prepared by : Prof. Madhuri Vaghasia 27

 Example

Prepared by : Prof. Madhuri Vaghasia 28

Prepared by : Prof. Madhuri Vaghasia 29
 Example

Prepared by : Prof. Madhuri Vaghasia 30

 1 2 3
4 5 6
Q 3 Q 5 6

1 2 3 1 2 3

• ANS: /null
4
/null
5
0/null
6
/null
4
/null
5
0/null
6
/null /null /null /null 1/3 1/3

Q 6 4 Q 4

1 2 3 1 2 3
/null /null 0/null /null /null 0/null
4 5 6 4 5 6
2/5 1/3 1/3 2/5 1/3 1/3

Q 2 Q 

1 2 3
/null 3/4 0/null 1 2 3
/null 3/4 0/null
4 5 6
2/5 1/3 1/3
4 5 6
2/5 1/3 1/3

Prepared by : Prof. Madhuri Vaghasia 31

 Breadth First Search
• procedure bfsearch(G)
{
for each v ∈ N do mark[v]  not-visited
for each v ∈ N do
if mark[v] ≠ visited then bfs(v)
}
• Procedure bfs(v)
{
Q  empty-queue
mark[v]  visited
enqueue v into Q

while Q is not empty do

u  first(Q)
dequeue u from Q
for each node w adjacent to u do
if mark[w] ≠ visited
then mark[w]  visited
enqueue w into Q
} Prepared by : Prof. Madhuri Vaghasia 32
Depth First Search - Undirected Graph
• Let G = <N, A> be an undirected graph all of whose nodes
we wish to visit. Suppose it is somehow possible to mark a
node to show it has already been visited.

• To carry out a depth-first traversal of the graph, choose any

node v ∈ N as the starting point. Mark this node to show it
has been visited.

• Next, if there is a node adjacent to v that has not yet been

visited, choose this node as a new starting point and call
the depth-first search procedure recursively.
Prepared by : Prof. Madhuri Vaghasia 33
Depth First Search - Undirected Graph
• On return from the recursive call, if there is another
node adjacent to v that has not been visited, choose
this node as the next starting point, call the procedure
recursively once again, and finished.

• If there remain any nodes of G that have not been

visited, chose any one of them as a new starting point,
and call the procedure yet again.

• Continue thus until all the nodes of G are marked.

Prepared by : Prof. Madhuri Vaghasia 34
Depth First Search - Undirected Graph
• procedure dfsearch(G)
{
for each v ∈ N do mark[v]  not-visited
for each v ∈ N do
if mark[v] ≠ visited then dfs(v)
}

• procedure dfs(v)
{
{Node v has not previously been visited}

pnum  pnum + 1
prenum[v]  pnum

mark[v]  visited
for each node w adjacent to v do
if mark[w] ≠ visited then dfs(w)
}

Prepared by : Prof. Madhuri Vaghasia 35

 Depth-first searching
• A depth-first search (DFS)
A explores a path all the way to
a leaf before backtracking and
B C
exploring another path
• For example, after searching
A, then B, then D, the search
D E F G
backtracks and tries another
path from B
H I J K • Node are explored in the
order A B D E H L M N I O
L M N O P Q PCFGJKQ
• N will be found before J

Prepared by : Prof. Madhuri Vaghasia 36

 DFS-Procedure
• start from root
• travel to a leaf along a path
• backtrack one level
• travel down another branch
• if all branches of a node explored: backtrack
another level
• continue until all sub trees of root explored
• appropriate data structure: stack
Prepared by : Prof. Madhuri Vaghasia 37
Prepared by : Prof. Madhuri Vaghasia 38
 Example

Prepared by : Prof. Madhuri Vaghasia 39

Example on DFS
q r
s

v t
w u
x y

2/7 1/16 17/20

q r
s
• ANS: 3/6
v 8/15 t 18/19
w u
4/5 9/12 x y
13/14

10/11 z
Prepared by : Prof. Madhuri Vaghasia 40
 Example

Prepared by : Prof. Madhuri Vaghasia 41

Topological sorting

Prepared by : Prof. Madhuri Vaghasia 42

Topological sorting
– There are many problems involving a set of tasks in
which some of the tasks must be done before others.
– For example, consider the problem of taking a course
only after taking its prerequisites.
– Is there any systematic way of linearly arranging the
courses in the order that they should be taken?

Prepared by : Prof. Madhuri Vaghasia 43

Topological sorting
• The goal of a topological sort is given a list of items with
dependencies, (ie. item 5 must be completed before item 3, etc.)
to produce an ordering of the items that satisfies the given
constraints. In order for the problem to be solvable, there can not
be a cyclic set of constraints.

• We can model a situation like this using a directed acyclic graph.

Given a set of items and constraints, we create the corresponding
graph as follows:
– 1) Each item corresponds to a vertex in the graph.
– 2) For each constraint where item a must finish before item b, place a
directed edge in the graph starting from the vertex for item a to the
vertex for item b.
Prepared by : Prof. Madhuri Vaghasia 44
Topological sorting
• Topological sort is not unique.

• The following are all topological sort of the graph

below:
s1 = {a, b, c, d, e, f, g, h, i}

s2 = {a, c, b, f, e, d, h, g, i}

s3 = {a, b, d, c, e, g, f, h, i}

s4 = {a, c, f, b, e, h, d, g, i}
etc.

Prepared by : Prof. Madhuri Vaghasia 45

By: Jay B. Teraiya(HOD IT Depart. - FOE)
Topological sorting

Prepared by : Prof. Madhuri Vaghasia 46

Topological sorting
• Example : A topological sort is given by: B, A, D, C,
E.
• ->There could be several topological sorts for a
given DAG.

Prepared by : Prof. Madhuri Vaghasia 47

Topological sorting

Prepared by : Prof. Madhuri Vaghasia 48

By: Jay B. Teraiya(HOD IT Depart. - FOE)
 Articulation point
• An articulation point of a graph is a vertex v
such that if v and its incident edges are
removed, a connected component of the
graph is broken into two or more pieces
• A connected component with no articulation
points is said to be biconnected

Prepared by : Prof. Madhuri Vaghasia 49

 DFS Edge Classification
• While building DFS tree, edges can be clasified into four categories.
1. If v is visited for the first time as we traverse the edge (u; v), then
the edge is a tree edge.
2. Else, v has already been visited:
– If v is an ancestor of u, then edge (u; v) is a back edge.
– Else, if v is a descendant of u, then edge (u; v) is a forward edge.
– Else, if v is neither an ancestor or descendant of u, then edge (u;
v) is a cross edge.

Prepared by : Prof. Madhuri Vaghasia 50

 Algorithm to Find out Articulation
points in a given graph
Step 1. Perform DFS on given graph and give prenum to
each node
Step 2. Find highest of each node(in sequence of post order
travesed) which is Minimum of
1. Dfs order no(prenum)
2. Back edge prenum
3. Child’s back edge prenum
Step 3.
1. Root is AP if it has more then 1 child.
2. Any other node v is AP if it has a child x such that
highest[x]>=prenum[v]
3. No leaf node can be AP.
Prepared by : Prof. Madhuri Vaghasia 51
If the graph has no AP then it is said to be bi-connected

Prepared by : Prof. Madhuri Vaghasia 52

Prepared by : Prof. Madhuri Vaghasia 53
Example 3

Prepared by : Prof. Madhuri Vaghasia 54

 Example 4

Prepared by : Prof. Madhuri Vaghasia 55

 Example 5

Prepared by : Prof. Madhuri Vaghasia 56

Example 6

Prepared by : Prof. Madhuri Vaghasia 57

Prepared by : Prof. Madhuri Vaghasia 58
Example 7

Prepared by : Prof. Madhuri Vaghasia 59

 Backtracking
• Backtracking is kind of solving a problem by
trial and error. However, it is a well organized
trial and error. We make sure that we never
try the same thing twice.
• We also make sure that if the problem is finite
we will eventually try all possibilities
(assuming there is enough computing power
to try all possibilities).

Prepared by : Prof. Madhuri Vaghasia 60

 Need for Backtracking
• 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 (possibly more than
one) may be a solution to your problem
• Backtracking is a methodical way of trying
out various sequences of decisions, until
you find one that “works”
Prepared by : Prof. Madhuri Vaghasia 61
 Backtracking (animation)
dead end

?
dead end
dead end

?
start ? ?
dead end

dead end

success!

Prepared by : Prof. Madhuri Vaghasia 62

The general template
• Procedure backtrack(v[1…k])
{
{ v is a k – promising vector}
if v is a solution then write v
{else} for each (k+1) – promising vector w
such that w[1…k] = v[1…k]
do backtrack(w[1…k+1])
}

Prepared by : Prof. Madhuri Vaghasia 64

Backtracking Algorithm – Example
• Find path through maze
– Start at beginning of maze
– If at exit, return true
– Else for each step from current location
• Recursively find path
• Return with first successful step
• Return false if all steps fail
• Other puzzles like 8-queen puzzle,
Crosswords, Verbal Arithmetic, Sudoku,
Peg solitaire,etc.

Prepared by : Prof. Madhuri Vaghasia 65

 Sudoku

Prepared by : Prof. Madhuri Vaghasia 66

 Sudoku

Prepared by : Prof. Madhuri Vaghasia 67

 Sudoku

Prepared by : Prof. Madhuri Vaghasia 68

0/1 Knapsack Problem using Backtracking

• Knapsack can carry a weight not exceeding

W(total knapsack capacity)
• Main Aim: To fill the knapsack in a way the
maximize the profit of the included objects,
while respecting the capacity constraint.
• We may take an object or to leave it behind,
but we may not take a fraction of an object

Prepared by : Prof. Madhuri Vaghasia 73

 An Example:

Weight 2 3 4 5

Profit 3 5 6 10
Capacity 8

Prepared by : Prof. Madhuri Vaghasia 75

 ;0

2;3 3;5 4;6 5;10

4,4;
2,2;6 2,3;8 2,4;9 2,5;13 3,3;10 3,4;11 3,5;15
12

2,2,2;9 2,2,3;11 2,2,4;12

2,3,3;13

2,2,2,2;1
2

Weight 2 3 4 5

Profit 3 5 6 10
Capacity 8
Prepared by : Prof. Madhuri Vaghasia 76
 Algorithm
function backtrack(i , r)
{ Calculates the value of the best load that can be constructed
using items of types I to n and whose total weight does not
exceed r }
b=0
{ Try each allowed kind of item in turn }
for k = i to n do
{
if (w[k]<=r) then
b = max(b , v[k]+ backpack (k, r-w[k]))
}
return b;
Prepared by : Prof. Madhuri Vaghasia 78
 N-queen Problem
• Given is a chess board. A chess board has 8x8
fields. Is it possible to place 8 queens on this
board, so that no two queens can attack each
other?
• A queen can attack horizontally, vertically, and
on both diagonals, so it is pretty hard to place
several queens on one board so that they
don’t attack each other.

Prepared by : Prof. Madhuri Vaghasia 81

 Example: The n-Queen problem
• Place n queens on an n by n chess board so that no
two of them are on the same row, column, or
diagonal

Solution Not a Solution 82

Solving a 3-queen Problem

Prepared by : Prof. Madhuri Vaghasia 83

 Solving 4-queen problem

Prepared by : Prof. Madhuri Vaghasia 84

State Space Tree of the Four-queens Problem

Prepared by : Prof. Madhuri Vaghasia 85

Solution to 5-queen Problem

Prepared by : Prof. Madhuri Vaghasia 86

Some solution to 8 queen problem

Prepared by : Prof. Madhuri Vaghasia 87

Algorithm Place(k,i)
/* returns true if a queen can be placed in kth row and ith column.
Otherwise it returns false. X[ ] is a gloabal array whose first (k-1)
values have been set. Abs( r) returns the absolute value of r. */
{
for j:=1 to k-1 do
if((x[j]=i) /* two in the same column */
or (Abs(x[j]-i)=Abs(j-k))) /* or in the same daigonal */
then return false;
return true;
}

Prepared by : Prof. Madhuri Vaghasia 88

Algorithm Queens(k,8)
/* using backtracking ,this procedure pritns all possible placement of n queens on
8×8 chessboard so that they are nonattacking */
{
for i:=1 to 8 do
{
if(Place(k,i) then
{
x[k]:=i;
if(k=8) then write(x[1..8]);
else Queens(k+1,8);
}
}
}
Prepared by : Prof. Madhuri Vaghasia 89
 GTU QUESTIONS..
• Explain in brief Breadth First Search and Depth
First Search Traversal techniques of a Graph.
[7]
• Find all possible solution for the 4*4
chessboard, 4 queen’s problem using
backtracking. [7]
• Define: Acyclic Directed Graph, Articulation
Point, Dense Graph, Sparse Graph.
[4]

Prepared by : Prof. Madhuri Vaghasia 90

 PG

• For a graph G = (V, E) with V no of Vertices and E

no of Edges. Where V=12 and E=23. What kind of
storage would be used to store Information of
Adjacent Nodes? What would be storage
requirement/complexity for maintaining
information for adjacent List and adjacent Matrix?
• Explain different types of Edges in DFS with
suitable example.
• Find an optimal solution to the knapsack instance
n=4, M=8, (P1,P2,P3,P4)= (3,5,6,10) and
(W1,W2,W3,W4)=(2,3,4,5) using backtracking.
Prepared by : Prof. Madhuri Vaghasia 91