Artificial Intelligence
BFS and DFS
PRN : 1262240234
Done by : samratsinh bhandari
Aim : To understand concept of BFS & DFS and its application
1 BFS definition :
• Breadth-First Search (BFS) is an graph traversal algorithm which is used for used for traversing or
searching through a graph or tree. It explores nodes level by level, meaning it visits all the neighbors of
a node before moving on to the next level of neighbors.
• Also, it uses the Queue data structure to maintaining track record of visited nodes and work on the
principle of FIFO ( First In First Out ) which is generally used for finding shortest path. Application :
shortest Path Lets see it for graph as shown below Fig 1:
Figure 1: Graph
1
from collections import deque
def bfs ( graph , start , goal ) :
visited = set ()
queue = deque ([[ start ]])
if start == goal :
return [ start ]
while queue :
path = queue . popleft ()
node = path [ -1]
if node not in visited :
neighbors = graph [ node ]
for neighbor in neighbors :
new_path = list ( path )
new_path . append ( neighbor )
queue . append ( new_path )
if neighbor == goal :
return new_path
visited . add ( node )
return []
graph = {
’A ’: [ ’B ’ , ’C ’] ,
’B ’: [ ’A ’ , ’D ’ , ’E ’] ,
’C ’: [ ’A ’ , ’F ’] ,
’D ’: [ ’B ’] ,
’E ’: [ ’B ’ , ’F ’] ,
’F ’: [ ’C ’ , ’E ’]
}
start_node = ’A ’
goal_node = ’F ’
shortest_path = bfs ( graph , start_node , goal_node )
print ( f " Shortest path from { start_node } to { goal_node }: { shortest_path } " )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
• Output :
Shortest path from A to F : [ ’A ’ , ’C ’ , ’F ’]
Conclusion : This concept can be also applied to more complex algorithm such as Djkiltra Algorithm
but its slower as it takes more computancy.
2
2 DFS definition :
• Depth-First Search (DFS) is an algorithm used for traversing or searching through a graph or tree by
exploring as far as possible down one branch before backtracking to explore other branches.
• Also, it uses the Stacking data structure to maintaining track record of visited nodes and work on the
principle of LIFO ( Last In First Out ) It keeps exploring particular path untill unless it reaches leaf node
and back track when its completed.
Application : N-Queen Problem
def is_safe ( board , row , col , N ) :
for i in range ( col ) :
if board [ row ][ i ] == ’Q ’:
return False
for i , j in zip( range ( row , -1 , -1) , range ( col , -1 , -1) ) :
if board [ i ][ j ] == ’Q ’:
return False
for i , j in zip( range ( row , N ) , range ( col , -1 , -1) ) :
if board [ i ][ j ] == ’Q ’:
return False
return True
def print_board ( board , N ) :
for row in board :
print ( " " . join ( row ) )
print ()
# Recursive function to solve the N- Queens problem
def solve_n_queens ( board , col , N ) :
# Base case : If all queens are placed , return True
if col >= N :
print_board ( board , N )
return True
res = False # Track if there ’s a solution in this path
# Try placing the queen in all rows one by one
for i in range ( N ) :
if is_safe ( board , i , col , N ) :
board [ i ][ col ] = ’Q ’
res = solve_n_queens ( board , col + 1 , N ) or res
board [ i ][ col ] = ’. ’
return res
def n_queens ( N ) :
# Create an N x N chessboard initialized with ’. ’
board = [[ ’. ’ for _ in range ( N ) ] for _ in range ( N ) ]
if not solve_n_queens ( board , 0 , N ) :
print ( " No solution exists " )
N = int( input ( " Enter the value of N : " ) ) == 5 # Input the size of the board n_queens ( N )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
3
• Output:
1Q....
2. . . Q .
3 .Q...
4 ....Q
5 ..Q..
6
7 Q....
8 ..Q..
9 ....Q
10 .Q...
11 ...Q.
12
13 ..Q..
14 Q . . . .
15 ...Q.
16 .Q...
17 ....Q
18
19 ...Q.
20 Q . . . .
21 ..Q..
22 ....Q
23 .Q...
24
25 .Q...
26 . . . Q .
27 Q....
28 ..Q..
29 ....Q
30
31 ....Q
32 . . Q . .
33 Q....
34 ...Q.
35 .Q...
36
37 .Q...
38 . . . . Q
39 ..Q..
40 Q....
41 ...Q.
42
43 ....Q
44 . Q . . .
45 ...Q.
46 Q....
47 ..Q..
48
49 ...Q.
50 .Q...
51 ....Q
52 ..Q..
4
53 Q....
54
55 ..Q..
56 . . . . Q
57 .Q...
58 ...Q.
59 Q....
Conclusion : This concept is very much useful in finding such problems i.e. Hamiltonian Path/Cycle,
Traveling Salesman Problem.
5
