Python Program for Depth First Search or DFS for a Graph

Depth First Search in Python Working

Python Depth First Search Algorithm is used for traversing or searching tree or graph data structures.

1. Solving mazes with Depth-First
Search
Lab Assignment 2
Dr. Hitesh Mohapatra
Associate Professor
School of Computer Engineering
KIIT Deemed to be University

2. Graph

3. Step 1
Figure 3 — Green indicates the node we’re actively evaluating.

4. Step 2
Figure 3 — Blue indicates an already evaluated(visited) node.

5. Step 3

6. Step 4

7. Step 5

8. Step 6 and Step 7

9. Maze

10. Abstract the image

11. Example
The robot is positioned at the initial state (0,0) and aims
to reach the goal state (0,5).

12. # Maze dimensions and obstacles
maze_size = 6
obstacles = [(0,1),(1,1),(3,2),(3,3),(3,4),(3,5),(0,4),(4,1),(4,2),(4,3)]
start = (0,0)
goal = (0,5)

13. Step 2: Define a is_valid function
Theis_validfunction checks whether a given position of (x,y) is
valid such that it inspects that it's within the bounds of the maze
and not obstructed by any obstacles.
def is_valid(x,y):
return 0 <= x < maze_size and 0 <= y < maze_size and (x,y) not in
obstacles

14. Step 3: Define dfs function (Depth-first
search):
def dfs (current, visited, path):
x, y = current
if current == goal:
path.append(current)
return True
visited.add(current)
moves = [(x-1,y), (x+1, y), (x, y-1), (x, y+1)]
for move in moves:
if is_valid(*move) and move not in visited:
if dfs(move, visited, path):
path.append(current)
return True
return False

15. Step 4: Call DFS function to find the path
visited = set()
path = []
if dfs(start, visited, path):
path.reverse()
print("Path found:")
for position in path:
print(position)
else:
print("No path found!")

16. 1.https://github.com/hm18818/AI-with-
Python/blob/main/DFS%20for%20MAZE%20solve
2.https://github.com/hm18818/AI-with-
Python/blob/main/DFS%20for%20MAZE%20Solver
%20with%20Plot