7.6 Practice Problems
Let's dive into some practical problems that can help us understand these graph algorithms better.
Problem 1: DFS in Maze Solving
Let's start with an easy problem of solving a maze using DFS. In this problem, we are given a grid (2D array), and we have to find a path from the start position to the goal position. We can move up, down, left, and right, but not diagonally.
Here's a simple Python implementation using DFS:
def dfs(maze, start, goal): stack = [(start, [start])] visited = set() while stack: (vertex, path) = stack.pop() if vertex not in visited: if vertex == goal: return path visited.add(vertex) for neighbor in get_neighbors(maze, vertex): stack.append((neighbor, path + [neighbor])) def get_neighbors(maze, position): # Returns the valid neighbors of a position in the maze # We assume the maze to be a list of lists in Python i, j = position neighbors = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)] valid_neighbors = [] for x, y in neighbors: if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0: # 0 signifies a path, 1 is a wall valid_neighbors.append((x, y)) return valid_neighborsYou can test this with a simple maze (list of lists where 0 signifies a path and 1 is a wall).
Problem 2: Shortest Path in a Grid with BFS
A typical example of BFS is finding the shortest path in a grid (e.g., from the top-left corner to the bottom-right corner). This is because BFS is a level order traversal, and it visits all vertices at the same level before going deeper into the graph. Let's try to solve a problem using BFS. The problem statement is similar to the previous problem, but instead of DFS, we use BFS to find the shortest path.
We'll take a simple Python approach to demonstrate:
from collections import deque def bfs(grid, start, goal): queue = deque([([start], 0)]) # [(path, cost)] seen = {start: 0} while queue: path, cost = queue.popleft() current = path[-1] if current == goal: return path, cost for neighbor in get_neighbors(grid, current): if neighbor not in seen or cost + 1 < seen[neighbor]: seen[neighbor] = cost + 1 queue.append((path + [neighbor], cost + 1)) return None # No path found # get_neighbors is same as in the previous example You can test this with a simple grid to understand how BFS works.
Note: To solve the above problems using A* search, Dijkstra's Algorithm, or other graph algorithms, we just need to modify the way we explore the neighbors and possibly add a priority queue.
Have a try with these problems, and happy problem solving!