Menu iconMenu iconIntroduction to Algorithms
Introduction to Algorithms

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_neighbors

You 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_neighbors

You 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_neighbors

You 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_neighbors

You 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!