The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Exercises with Graphs

Next ►
►

In this section, we will reinforce the concepts learned in the Graphs module through practical exercises. Each exercise is designed to help you understand and apply graph-related algorithms and data structures. Solutions are provided to help you verify your understanding and correct any mistakes.

Exercise 1: Graph Representation

Problem: Given the following undirected graph, represent it using an adjacency list and an adjacency matrix.

Graph:
    A -- B
    |    |
    C -- D

Solution:

Adjacency List Representation

graph_adj_list = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

Adjacency Matrix Representation

A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0

Exercise 2: Depth-First Search (DFS)

Problem: Implement the Depth-First Search (DFS) algorithm for the given graph and print the nodes in the order they are visited.

Graph:

    A
   / \
  B   C
 / \
D   E

Solution:

DFS Implementation

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A'},
    'D': {'B'},
    'E': {'B'}
}

dfs(graph, 'A')

Output:

A B D E C

Exercise 3: Breadth-First Search (BFS)

Problem: Implement the Breadth-First Search (BFS) algorithm for the given graph and print the nodes in the order they are visited.

Graph:

    A
   / \
  B   C
 / \
D   E

Solution:

BFS Implementation

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A'},
    'D': {'B'},
    'E': {'B'}
}

bfs(graph, 'A')

Output:

A B C D E

Exercise 4: Shortest Path Using Dijkstra's Algorithm

Problem: Given a weighted graph, implement Dijkstra's algorithm to find the shortest path from a starting node to all other nodes.

Graph:

    A --1-- B
    |      / \
    4     2   3
    |   /     \
    C --5-- D --6-- E

Solution:

Dijkstra's Algorithm Implementation

import heapq

def dijkstra(graph, start):
    queue = [(0, start)]
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    while queue:
        current_distance, current_node = heapq.heappop(queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))
    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'D': 2, 'E': 3},
    'C': {'A': 4, 'D': 5},
    'D': {'B': 2, 'C': 5, 'E': 6},
    'E': {'B': 3, 'D': 6}
}

distances = dijkstra(graph, 'A')
print(distances)

Output:

{'A': 0, 'B': 1, 'C': 4, 'D': 3, 'E': 4}

Exercise 5: Detecting Cycles in a Graph

Problem: Implement a function to detect if there is a cycle in an undirected graph.

Graph:

    A -- B
    |    |
    C -- D

Solution:

Cycle Detection Implementation

def has_cycle(graph):
    def visit(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if visit(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False

    visited = set()
    for node in graph:
        if node not in visited:
            if visit(node, None):
                return True
    return False

graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D'},
    'C': {'A', 'D'},
    'D': {'B', 'C'}
}

print(has_cycle(graph))

Output:

True

Conclusion

In this section, we covered various exercises to practice graph representations, traversal algorithms (DFS and BFS), shortest path algorithms (Dijkstra's), and cycle detection. These exercises are crucial for understanding the practical applications of graphs in computer science. Make sure to practice these problems thoroughly to solidify your understanding of graph data structures and algorithms.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved