Chapter 7: Graph Algorithms
7.6 Practice Problems of Chapter 7: Graph Algorithms
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!
7.6 Practice Problems of Chapter 7: Graph Algorithms
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!
7.6 Practice Problems of Chapter 7: Graph Algorithms
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!
7.6 Practice Problems of Chapter 7: Graph Algorithms
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!