Artificial Intelligence

BFS and DFS

PRN : 1262240022

Done by : Rahul Shah

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
 1 from collections import deque
2

3 def bfs ( graph , start , goal ) :

4 visited = set ()
5 queue = deque ([[ start ]])
6

7 if start == goal :
8 return [ start ]
9

10 while queue :
11 path = queue . popleft ()
12

13 node = path [ -1]

14 if node not in visited :
15 neighbors = graph [ node ]
16 for neighbor in neighbors :
17 new_path = list ( path )
18 new_path . append ( neighbor )
19 queue . append ( new_path )
20

21 if neighbor == goal :
22 return new_path
23 visited . add ( node )
24 return []
25 graph = {
26 ’A ’: [ ’B ’ , ’C ’] ,
27 ’B ’: [ ’A ’ , ’D ’ , ’E ’] ,
28 ’C ’: [ ’A ’ , ’F ’] ,
29 ’D ’: [ ’B ’] ,
30 ’E ’: [ ’B ’ , ’F ’] ,
31 ’F ’: [ ’C ’ , ’E ’]
32 }
33 start_node = ’A ’
34 goal_node = ’F ’
35

36 shortest_path = bfs ( graph , start_node , goal_node )

37 print ( f " Shortest path from { start_node } to { goal_node }: { shortest_path } " )

• Output :
1 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
1 def is_safe ( board , row , col , N ) :
2 for i in range ( col ) :
3 if board [ row ][ i ] == ’Q ’:
4 return False
5 for i , j in zip ( range ( row , -1 , -1) , range ( col , -1 , -1) ) :
6 if board [ i ][ j ] == ’Q ’:
7 return False
8 for i , j in zip ( range ( row , N ) , range ( col , -1 , -1) ) :
9 if board [ i ][ j ] == ’Q ’:
10 return False
11 return True
12

13 def print_board ( board , N ) :

14 for row in board :
15 print ( " " . join ( row ) )
16 print ()
17

18 # Recursive function to solve the N - Queens problem

19 def solve_n_queens ( board , col , N ) :
20 # Base case : If all queens are placed , return True
21 if col >= N :
22 print_board ( board , N )
23 return True
24

25 res = False # Track if there ’s a solution in this path

26

27 # Try placing the queen in all rows one by one

28 for i in range ( N ) :
29 if is_safe ( board , i , col , N ) :
30 board [ i ][ col ] = ’Q ’
31 res = solve_n_queens ( board , col + 1 , N ) or res
32 board [ i ][ col ] = ’. ’
33

34 return res
35

36 def n_queens ( N ) :
37 # Create an N x N chessboard initialized with ’. ’
38 board = [[ ’. ’ for _ in range ( N ) ] for _ in range ( N ) ]
39

40 if not solve_n_queens ( board , 0 , N ) :

41 print ( " No solution exists " )
42 N = int ( input ( " Enter the value of N : " ) ) == 5 # Input the size of the board
43 n_queens ( N )

3
 • Output :
1 Q . . . .
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.