Uninformed Search
DR. SHWETA SHARMA
Contents
1. Breadth-First Search (BFS)
2. Depth-First Search (DFS)
DR. SHWETA SHARMA, PEC CHANDIGARH 2
Breadth-First Search (BFS)
DR. SHWETA SHARMA, PEC CHANDIGARH 3
1. Breadth-First Search (BFS)
An algorithm used for traversing graphs or trees. Traversing
means visiting each node of the graph
Expand all the nodes of one level first
An iterative algorithm to search all the vertices of a graph or
a tree
Breadth-First Search in a tree and graph is almost the same.
The only difference is that the graph may contain cycles, so
we may traverse to the same node again
DR. SHWETA SHARMA, PEC CHANDIGARH 4
Breadth-First Search (BFS)
Example: Rubik’s Cube
Rubik’s Cube is seen as searching for a path to convert it from a full mess of colors to a
single color
Comparing the Rubik’s Cube to the graph:
the possible state of the cube is
corresponding to the nodes of the graph and
the possible actions of the cube is
corresponding to the edges of the graph
DR. SHWETA SHARMA, PEC CHANDIGARH 5
Breadth-First Search (BFS)
BFS starts from a node, then it checks all the nodes at distance one
from the beginning node, then it checks all the nodes at distance
two, and so on
So as to recollect the nodes to be visited, BFS uses a QUEUE
DR. SHWETA SHARMA, PEC CHANDIGARH 6
Breadth-First Search (BFS)
DR. SHWETA SHARMA, PEC CHANDIGARH 7
Breadth-First Search (BFS)
DR. SHWETA SHARMA, PEC CHANDIGARH 8
Breadth-First Search (BFS)
As breadth-first search is the process of traversing each node of the
graph, a standard BFS algorithm traverses each vertex of the graph
into two parts: 1) Visited 2) Not Visited
So, the purpose of the algorithm is to visit all the vertex while
avoiding cycles
DR. SHWETA SHARMA, PEC CHANDIGARH 9
Steps in BFS
1. Start by putting any one of the graph’s vertices at the back of the queue
2. Now take the front item of the queue and add it to the visited list
3. Create a list of that vertex's adjacent nodes. Add those which are not
within the visited list to the rear of the queue
4. Keep continuing steps two and three till the queue is empty
DR. SHWETA SHARMA, PEC CHANDIGARH 10
BFS pseudo code
create a queue Q
mark v as visited and put v into Q
while Q is non-empty
remove the head u of Q
mark and enqueue all (unvisited) neighbors of u
DR. SHWETA SHARMA, PEC CHANDIGARH 12
Example 1
Undirected graph with 5 vertices
DR. SHWETA SHARMA, PEC CHANDIGARH 13
Example 1 (Cont..)
Source is chosen randomly (say, P)
Begin from the vertex P, the BFS
algorithm starts by putting it
within the Visited list and puts all
its adjacent vertices (Q, R, and S)
in the queue
DR. SHWETA SHARMA, PEC CHANDIGARH 14
Example 1 (Cont..)
Next, we have a tendency to visit
the part at the front of the queue
i.e. Q and visit its adjacent nodes
Since P has already been visited,
we have a tendency to visit R
instead
Note: R is in the front of the
QUEUE (FIFO)
DR. SHWETA SHARMA, PEC CHANDIGARH 15
Example 1 (Cont..)
Vertex R has an unvisited adjacent
vertex in T
Thus we have a tendency to add
that to the rear of the queue and
visit S, which is at the front of the
queue
DR. SHWETA SHARMA, PEC CHANDIGARH 16
Example 1 (Cont..)
Only T remains within the queue
since the only adjacent node of S
i.e. P is already visited.
We have a tendency to visit it.
DR. SHWETA SHARMA, PEC CHANDIGARH 17
Example 1 (Cont..)
Since the queue is empty, we've
completed the Traversal of the
graph
DR. SHWETA SHARMA, PEC CHANDIGARH 18
Implementation of BFS (Python)
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = [] # List for visited nodes.
queue = [] #Initialize a queue
def bfs(visited, graph, node): #function for BFS
visited.append(node)
queue.append(node)
DR. SHWETA SHARMA, PEC CHANDIGARH 19
Implementation of BFS (Python)
while queue: # Creating loop to visit each node
m = queue.pop(0)
print (m, end = " ")
for neighbour in graph[m]:
if neighbour not in visited:
visited.append(neighbour)
queue.append(neighbour)
print("Following is the Breadth-First Search")
bfs(visited, graph, '5') # function calling
DR. SHWETA SHARMA, PEC CHANDIGARH 20
Question 1 on BFS Traversal
01234
DR. SHWETA SHARMA, PEC CHANDIGARH 21
Question 2 on BFS Traversal
A, B, C, D, E, F
DR. SHWETA SHARMA, PEC CHANDIGARH 22
Question 3 on BFS Traversal
2, 3, 0, 1
or
2, 0, 3, 1
DR. SHWETA SHARMA, PEC CHANDIGARH 23
Depth-First Search (DFS)
DR. SHWETA SHARMA, PEC CHANDIGARH 25
BFS vs. DFS
DR. SHWETA SHARMA, PEC CHANDIGARH 26
Depth-First Search (DFS)
Depth-first traversal or Depth-first Search is an
algorithm to look at all the vertices of a graph
or tree data structure
Expand one of the nodes at the deepest level
DR. SHWETA SHARMA, PEC CHANDIGARH 27
Depth-First Search (DFS)
Example: Maze
We tend to take a route, keep going until we discover a
dead end. When touching the dead end, we again
come back and keep coming back till we see a path we
didn't attempt before
Take that new route. Once more keep going until we
discover a dead end. Take a come back again… This is
exactly how Depth-First Search works
DR. SHWETA SHARMA, PEC CHANDIGARH 28
Depth-First Search (DFS)
The Depth-First Search is a recursive algorithm that uses the concept of
backtracking
It involves thorough searches of all the nodes by going ahead if potential,
else by backtracking
Here, the word backtrack means once you are moving forward and there
are not any more nodes along the present path, you progress backward on
an equivalent path to seek out nodes to traverse
All the nodes are progressing to be visited on the current path until all the
unvisited nodes are traversed after which subsequent paths are going to
be selected
DR. SHWETA SHARMA, PEC CHANDIGARH 29
DFS
The recursive method of the Depth-First Search algorithm is
implemented using STACK. A standard Depth-First Search
implementation puts every vertex of the graph into one in all 2
categories: 1) Visited 2) Not Visited
The only purpose of this algorithm is to visit all the vertex of the
graph avoiding cycles
DR. SHWETA SHARMA, PEC CHANDIGARH 30
Steps in DFS
1. We will start by putting any one of the graph's vertex on top of the stack
2. After that take the top item of the stack and add it to the visited list of
the vertex
3. Next, create a list of that adjacent node of the vertex. Add the ones
which aren't in the visited list of vertexes to the top of the stack
4. Lastly, keep repeating steps 2 and 3 until the stack is empty
DR. SHWETA SHARMA, PEC CHANDIGARH 31
DFS pseudo code
DFS(G, u)
u.visited = true
for each v ∈ G.Adj[u]
if v.visited == false
DFS(G,v)
init() {
For each u ∈ G
u.visited = false
For each u ∈ G
DFS(G, u)
DR. SHWETA SHARMA, PEC CHANDIGARH 32
Example 1
Undirected graph with 5 vertices
DR. SHWETA SHARMA, PEC CHANDIGARH 33
Example 1 (Cont..)
Source is chosen randomly (say, P)
Begin from the vertex P, the DFS rule
starts by putting it within the Visited list
and putting all its adjacent vertices
within the stack
DR. SHWETA SHARMA, PEC CHANDIGARH 34
Example 1 (Cont..)
Next, we tend to visit the part at the
highest of the stack i.e. Q, and head to
its adjacent nodes. Since P has already
been visited, we tend to visit R instead
DR. SHWETA SHARMA, PEC CHANDIGARH 35
Example 1 (Cont..)
Vertex R has the unvisited adjacent
vertex in T, therefore we will be adding
that to the highest of the stack and visit
it
DR. SHWETA SHARMA, PEC CHANDIGARH 36
Example 1 (Cont..)
DR. SHWETA SHARMA, PEC CHANDIGARH 37
Example 1 (Cont..)
At last, we will visit the last component
S, it does not have any unvisited
adjacent nodes, thus we've completed
the Depth First Traversal of the graph
DR. SHWETA SHARMA, PEC CHANDIGARH 38
Implementation of DFS (Python)
graph = {
'5' : ['3','7'],
'3' : ['2', '4'],
'7' : ['8'],
'2' : [],
'4' : ['8'],
'8' : []
}
visited = set() # Set to keep track of visited nodes of graph.
def dfs(visited, graph, node): #function for dfs
if node not in visited:
print (node)
visited.add(node)
for neighbour in graph[node]:
dfs(visited, graph, neighbour)
print("Following is the Depth-First Search")
dfs(visited, graph, '5')
DR. SHWETA SHARMA, PEC CHANDIGARH 39
Question 1 on DFS Traversal
01243
DR. SHWETA SHARMA, PEC CHANDIGARH 40
Question 2 on DFS Traversal
12453
DR. SHWETA SHARMA, PEC CHANDIGARH 41
Question 3 on DFS Traversal
01352476
or
02475136
or
02475361
Starting node: 0
DR. SHWETA SHARMA, PEC CHANDIGARH 42
Thank you!
DR. SHWETA SHARMA, PEC CHANDIGARH 43
