Practical 9: Graph Data Structure and Traversal Algorithms

Objective

In this lab, you will implement a graph data structure and basic graph traversal algorithms in Python. This exercise will help you understand graph representations and practice implementing depth-first search (DFS) and breadth-first search (BFS) algorithms.

Submission Date: November 4st

Prerequisites

• Basic knowledge of Python syntax
• Understanding of data structures (particularly dictionaries)
• Familiarity with object-oriented programming in Python

Lab Steps

Step 1: Implement the Graph Class

First, let's create a Graph class using an adjacency list representation:

class Graph:
    def __init__(self):
        self.graph = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, vertex1, vertex2):
        self.add_vertex(vertex1)
        self.add_vertex(vertex2)
        self.graph[vertex1].append(vertex2)
        self.graph[vertex2].append(vertex1)  # For undirected graph
    
    def print_graph(self):
        for vertex in self.graph:
            print(f"{vertex}: {' '.join(map(str, self.graph[vertex]))}")

# Test the Graph class
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)
g.print_graph()

Step 2: Implement Depth-First Search (DFS)

Now, let's implement the DFS algorithm:

class Graph:
    # ... (previous methods remain the same)

    def dfs(self, start_vertex):
        visited = set()
        self._dfs_recursive(start_vertex, visited)
    
    def _dfs_recursive(self, vertex, visited):
        visited.add(vertex)
        print(vertex, end=' ')
        
        for neighbor in self.graph[vertex]:
            if neighbor not in visited:
                self._dfs_recursive(neighbor, visited)

# Test DFS
print("\nDFS starting from vertex 0:")
g.dfs(0)

Step 3: Implement Breadth-First Search (BFS)

Next, let's implement the BFS algorithm:

from collections import deque

class Graph:
    # ... (previous methods remain the same)

    def bfs(self, start_vertex):
        visited = set()
        queue = deque([start_vertex])
        visited.add(start_vertex)

        while queue:
            vertex = queue.popleft()
            print(vertex, end=' ')

            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)

# Test BFS
print("\nBFS starting from vertex 0:")
g.bfs(0)

Step 4: Implement a Method to Find All Paths

Let's add a method to find all paths between two vertices:

class Graph:
    # ... (previous methods remain the same)

    def find_all_paths(self, start_vertex, end_vertex, path=[]):
        path = path + [start_vertex]
        if start_vertex == end_vertex:
            return [path]
        if start_vertex not in self.graph:
            return []
        paths = []
        for neighbor in self.graph[start_vertex]:
            if neighbor not in path:
                new_paths = self.find_all_paths(neighbor, end_vertex, path)
                for new_path in new_paths:
                    paths.append(new_path)
        return paths

# Test finding all paths
print("\nAll paths from vertex 0 to vertex 3:")
all_paths = g.find_all_paths(0, 3)
for path in all_paths:
    print(' -> '.join(map(str, path)))

Step 5: Implement a Method to Check if the Graph is Connected

Finally, let's add a method to check if the graph is connected:

class Graph:
    # ... (previous methods remain the same)

    def is_connected(self):
        if not self.graph:
            return True
        start_vertex = next(iter(self.graph))
        visited = set()
        self._dfs_recursive(start_vertex, visited)
        return len(visited) == len(self.graph)

# Test if the graph is connected
print("\nIs the graph connected?", g.is_connected())

# Add a disconnected vertex and test again
g.add_vertex(4)
print("After adding a disconnected vertex:")
print("Is the graph connected?", g.is_connected())

Exercises for Students

1. Implement a method to find the shortest path between two vertices using BFS.
2. Add a method to detect cycles in the graph.
3. Implement Dijkstra's algorithm to find the shortest path in a weighted graph.
4. Create a method to determine if the graph is bipartite.

Conclusion

In this lab, you've implemented a graph data structure and basic graph traversal algorithms in Python. You've practiced creating a Graph class, implementing DFS and BFS, finding all paths between two vertices, and checking if a graph is connected.

These fundamental graph algorithms form the basis for solving many complex problems in computer science. As you work on the additional exercises, you'll gain a deeper understanding of graph theory and its applications.

Remember to test your code with different graph structures to ensure it works correctly in various scenarios.