UNIT - 3

GRAPHS
In the graph shown in Figure b above have two ingredients: (1) vertices, and (2) edges.

We usually denote the vertex and edge sets of a graph by V and E, respectively, and
sometimes write G = (V, E) to mean the graph G with vertices V and edges E.

Types of Graph
1. There are two flavors of graphs:
◦ Directed graph:
▪ In a directed graph, each edge (v, w) is an ordered pair, with the edge traveling from the
first vertex v (called the tail) to the second w (the head).
◦ Undirected Graph:
▪ In undirected graph each edge corresponds to an unordered pair {v, w} of vertices, which are called the
endpoints of the edge.
▪ In an undirected graph, there is no difference between an edge (v, w) and an edge (w,v).

Other types of Graph:

1. Infinite graph: A graph with infinite vertex set is called an Infinite graph
2. Finite graph: A graph with a finite vertex set is called a finite graph.
3. Simple graph: A graph in which each edge connects two different vertices and where no two edges connect the
same pair of vertices.
4. Multigraphs: Graphs that may have multiple edges connecting the same vertices are called multigraphs.
.
 Terminologies in Graph:

1. Path: Sequence of vertices connected by edges. A simple path is one with no repeated vertices
(e.g. s w t, s v t w).
2. Cycle: Path whose first and last vertices are the same. (e.g. s v w s)
3. The length of a path or a cycle is its number of edges.
4. A self-loop is an edge that connects a vertex to itself (see Figure below).

5. Two edges that connect the same pair of vertices are parallel edges.
6. The degree of a vertex is the number of edges incident to it.
7. A subgraph is a subset of a graph’s edges (and associated vertices) that constitutes a graph.
8. A graph is connected if there is a path from every vertex to every other vertex in the graph.
9. An acyclic graph is a graph with no cycles. A tree is an acyclic connected graph. A disjoint set of trees is called
a forest.
NOTE: A graph G with V vertices is a tree if and only if it satisfies any of the following five conditions:
1. G has V-1 edges and no cycles.
2. G has V-1 edges and is connected.
3. G is connected, but removing any edge disconnects it.
4. G is acyclic, but adding any edge creates a cycle.
5. Exactly one simple path connects each pair of vertices in G.
 Size of a Graph

1. What we actuatlly mean by size of Graph?

◦ Two parameters control a graph’s size--the number of vertices and the number of edges.

Representations of graphs:
We can choose between two standard ways to represent a graph G = (V, E):Adjacency list, and
1. Adjacency matrix.
Either way applies to both directed and undirected graphs. Adjacency-list representation provides a compact way
to represent sparse graphs
—those for which |E| is much less than |V|2.
• We may prefer an adjacency-matrix representation, 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 connecting two given vertices.
 Representations of Undirected Graphs

Representations of directed Graphs

Searching a Graph:
In this section we will study two algorithms, namely:
1. Breadth first search (BFS), and
2. Depth first search (DFS)
• Breadth first search
Breadth-first search is one of the simplest algorithms for
searching a graph.

BFS(G, «)
1 for each vertex u s G.V —{s j
2 H. color —
— WH ITE
3 u. d = in
4 u. F NIL
S s. color —— GRAY
6 s.d —
—0

9
10
11
12 for xhv [Link][]
13 if v. COfor == WHITB
14 v. c o l o r GRAY
15 v.d u. d + 1
lh
17 ENQURUR( , U)
18 u. color BLACK
• Depth First Search
Ouline of DFS:

1. Depth-first search explores edges out of the most recently discovered vertex v that still
has unexplored edges leaving it.

2. Once all of v’s edges have been explored, the search “backtracks” to explore edges
leaving the vertex from which v was discovered.

3. This process continues until we have discovered all the vertices that are reachable from
the original source vertex.

4. If any undiscovered vertices remain, then depth-first search selects one of them as a new
source, and it repeats the search from that source.
DFT(G)

Å IÎ Ł[Link]ÒŁ *= WHITE
7 DFT VISIT(G, )

DFT-VISIT(G, o)
1 fix time x l // white vertex u has justbeert Óscoyered
1 u.d —
- time

4 for eachy ë G.&j|x] // exploreedge (i‹,r)

å lÎ .color ---- WHITE
6 r.r = x
7 DFT—VISIT(G, r)
II blackena; itis finished
Example of DFS:
“Backtracking Approach”
Backtracking (Real Scenario Example)
• Have you ever seen Blind people walking on road?

❑ If Blind people find any obstacles in

their way, they just move backward and
then they will proceed in other
direction.
❑ How a blind person could move
backward when he/she finds obstacle?
❑ Simple answer…. By intelligence !!
❑ Similarly, if an algorithm Backtracks
with intelligence, it is called a
“Backtracking Algorithm”.
 Backtracking Approach: Introduction
• Suppose we have to make a series of decisions, among various choices
where we don’t have enough information to know what to choose and each
decision leads to a new set of choices.

• Some sequence of choices (possibly more

than one) may be a solution to our problem.

• Backtracking is a methodical way of trying

out various sequences of decisions until we
find one that “works”.

• Backtracking Algorithm determines soln by

systematically searching the solution space
for given problem. It is a “Depth First
Search” with some bounding function.
Problems solved by Backtracking
Approach or Algorithms
• Example: N-Queens Problem, Knight’s Tour Problem

Other Problems: Hamiltonian Circuit Problem, Subset-sum Problem, Travelling

Salesman Problem (TSP), Graph Coloring Problem etc.
N-Queens Problem
 N-Queens Problem
• N-Queens problem is to place N-Queens in such a way on a N x N chessboard
that no two queens attack each other by being in a same row, column or
diagonal. The puzzle was originally proposed in 1848 by the chess player
Max Bezzel.

• It can be seen that for N=1, the

problem has a trivial solution. And
no solution exits for N=2 and N=3.

• So, first we will consider 4-Queens

problem and then generalize it to N-
Queens problem.
4 x 4 chessboard
State-Space Tree for 4-Queens Problem
Brute Force Search

Size of search space is N !

Then, how to search effectively??
State-Space Tree for 4-Queens Problem
With Bounding Function
(explore by ensuring no diagonal attack)
Demonstration of Backtracking Approach for solving
4-Queens Problem
4-Queens Problem: Two possible Solutions…

Soln X = 2 4 1 3 X= 3 1 4 2

Column no.
[Link]
I
5-Queens Problem: Many possible Solutions…
8-Queens
Problem
Solutions:
8-Queens Problem: More solutions…

Solution 13:
900 clockwise rotation
of Solution 3

Solution 15:
1800 clockwise/anti-clockwise
rotation of Solution 3
Solution 14:
900 anti-clockwise
rotation of Solution 3

[Link]
p
 N-Queens Problem: Developing a Backtracking
Algorithm

1. Start from the first row.

2. if all queens are placed return “true”
3. Check all columns in the current row
Do following for every tried column
a) if the queen can be placed safely in this column then mark this position
[row,column] as part of the solution and recursively check if placing
queen here leads to a solution.
b) if placing the queen in [row,column] leads to a solution then return “true”
c) if placing queen doesn’t leads to a solution then unmark this position
[row,column],(means Backtrack) and go to step a) to check other columns.
4. If all columns have been checked and nothing worked,
return “false” to trigger backtracking.
N-Queens Problem: Backtracking Algorithm
Approach (Horowitz and Sahni Book)
You observed from the 8-queens problem that we can let (X1, ... , Xn) represent a solution where Xi is the
column of the ith row where the ith queen is placed. The XiS will all be distinct since no two queens can be
placed in the same column. Now, how do we test if two queens are on the same diagonal?

❑ Thus, the solution for 8-queens problem

is (4, 6, 8, 2, 7, 1, 3, 5).
❑ If two queens are placed at position (i, j) and (k, l).
Then, they are on same diagonal only
if i-j = k-l
or i+j= k+l
The first equation implies that j - l = i - k.
The second equation implies that j - l = k - i
❑ Therefore, two queens lie on the same diagonal if and
only if | j – l |=| i – k |
N-Queens Problem: Backtracking Algorithm
(Horowitz and Sahni Book)
procedure NQUEENS(n)

// prints combination of all solutions

for i=1 to n do
{
if (place(k,i)) then
{
x[k] = i
if(k==n) then //if all the queens are placed
print(x[1:n])
else
Nqueens(k+1,n)
}
}
Algorithm: Can a new queen be placed?
procedure PLACE(k)
// return true if a queen can be placed in the kth row and X(k)th column.
// Otherwise it returns false.
// X is a global array whose first k values have been set.
// ABS(r) returns the absolute value of r
global X(1:k); integer i, k
for i 1 to k do
if X(i) = X(k) // two in the same column
or ABS(X(i)- X(k)) = ABS(i-k) // two in the same diagonal
then return (false)
endif
repeat
return(true)
end PLACE

PLACE (k) procedure Computing time = O(k)

Knight’s Tour Problem
 Knight’s Tour Problem
• Given N x N chessboard with the knight placed on the one block of an empty
board. Moving according to the rules of chess knight must visit all squares
exactly one.

⮚ Similar to the N-Queens problem, we start

by moving the knight and if the knight
reaches to a cell from where there is no
further cell available to move and we have
not reached to the solution yet (not all cells
are covered), then we backtrack and change
our decision and choose a different path.
• For a person who is not familiar with chess, the knight moves two squares
horizontally and one square vertically, or two squares vertically and one
square horizontally as shown in the picture given below.

Thus if a knight is at (3, 3), it can move to the

(1, 2), (1, 4), (2,1), (2,5), (4, 1), (4, 5), (5, 2) and
(5, 4) cells.
Knight’s Tour
demonstration
on 6 x 6 board

3 Possible Solutions
Knight’s Closed Tour vs. Open Tour
• Finding a knight tour is actually
an application of Hamiltonian
Path or cycle.

• A knight tour is considered

closed if the final position is one
move away from the starting
position, and the knight could
immediately start the tour
again.

• A tour that is not closed is

considered open.
Closed Open
Tour Tour
Knight’s Tour demonstration on 8 x 8
board

Example of closed tour

8 x 8 Board
Knight’s Tour Problem: Backtracking Algorithm…

Valid Move:
A move is valid if it is inside the chessboard (i.e., i and j are between 1 to N)
and if the cell is not already occupied (i.e., sol[i][j] == -1).
We will make the value of all unoccupied cells equal to -1.
x_move = [2, 1, -1, -2, -2, -1, 1,
2]
y_move = [1, 2, 2, 1, -1, -2, -2, -
1]

IS-VALID(i, j, sol)
{
if (i >=1 and i <=N and j >=1 and j <=N and sol[i][j]= = -1)
return TRUE
else
return FALSE
}
 Knight’s Tour Problem:
// initialization of soln Matrix
Backtracking Algorithm

// initial position of knight // Try all next moves from the current coordinate i, j

// Checking valid move?

Space Complexity: O(N2)

// Backtrack
 Branch-and-bound: 16-puzzle problem
• The 16-puzzle (or 15-puzzle) is a sliding puzzle with 15 numbered
tiles and one empty space on a 4×4 board.

• The goal is to arrange the tiles in order (1 to 15) using the empty
space.
 How it works for 16-Puzzle
state of the puzzle is treated as a node.
[Link]

[Link] branches are the moves you can make by sliding a tile
into the empty space.
[Link] each node, compute:
•g(n) = number of moves made so far
•h(n) = estimated moves to reach the goal (e.g., Manhattan distance)
•f(n) = g(n) + h(n) (total estimated cost)

[Link] explore the node with the smallest f(n).

[Link] the goal state is reached, the path gives the
minimum number of moves.
First and goal position
Cont…
Cont…
• Solving this 16 Puzzle problem using expanding the node lead to huge
problem, so need to follow a heuristic approach to solve.
• Total of 16! Nodes will be generated, and from that picking the goal
node path is very difficult and also this occupies large space.
• So, using the branch and bound technique , solving these type of
problems are much easier.
• In this branch and bound technique, promising node( who’s solution
is better than the optimal solution) will be done branching and rest
will be bound.
Cont…
• Step 1
• For Node 2, there are 4 wrong positions
1 2 4 Compare with Goal Node 1 2 3 4
5 6 3 8 5 6 7 8
9 10 7 11 9 10 11 12
13 14 15 12 13 14 15

• The red color indicate a wrong position when compared with goal
node.
 ෣ of Node 2 is “4”
• So, the score 𝑔(𝑥)
෣ is 4
• For Node 3, 𝑔(𝑥)
෣ is 2
• For Node 4, 𝑔(𝑥)
෣ is 4
• For Node 5, 𝑔(𝑥)
• Step 2
෣ I.e 2.
• Among 2,3,4,5, Node 4 have smallest 𝑔(𝑥)
• So, only Node 4 should be branched

• Step 3
෣ =1
• Node 10 = 𝑔(𝑥)
෣ =3
• Node 11 = 𝑔(𝑥)
෣ =3
• Node 12 = 𝑔(𝑥)
• Step 4
෣ value, So Node 10
• Among Node 10,11,12. Node 10 have the low 𝑔(𝑥)
is done branching, rest are bounded.
• Step 5
• Node 10 : 1 2 3 4
5 6 7 8
9 10 11
13 14 15 12

• From this Node 10, we can do only two operation up and down.
• IF left operation is done it leads to the parent node, i.e “Node 2”
• And right operation cannot be done, as the blank space is already in
the right most.
• So, Now Node 10, leads to two other node those are Node 22 and 23.
• Finally we reached our goal node i.e. Node 23.
• So, branching is done for Node 4 and Node 10, rest all are bounded.
• Time Complexity: Worst case: pruning might do little, so you expand
on the order of all possible nodes up to depth d → O(b^d). With b≤4
that’s at worst O(4^d).