Module 1: Graphs I

Understanding Graphs

A graph is a data structure consisting of vertices (nodes) and edges that connect these vertices. Graphs are highly versatile and can represent many real-world relationships and networks.

Types of Graphs:

• Directed Graph: Edges have a specific direction (one-way connections)
• Undirected Graph: Edges have no direction (two-way connections)
• Weighted Graph: Edges have associated weights/values
• Cyclic Graph: Contains at least one cycle (a path that starts and ends at the same vertex)
• Acyclic Graph: Contains no cycles
• Connected Graph: There is a path between any two vertices

Real-world Applications:

• Social networks (friends as vertices, connections as edges)
• Road maps (intersections as vertices, roads as edges)
• Computer networks (devices as vertices, connections as edges)
• Recommendation systems (users/items as vertices, preferences as edges)

Adjacency Lists Explained

An adjacency list is one of the most common ways to represent a graph. It uses an array or object where each vertex is associated with a list of its adjacent vertices (neighbors).

Implementation in Python:

class Graph:
    def __init__(self):
        self.adjacency_list = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.adjacency_list:
            self.adjacency_list[vertex] = []
    
    def add_edge(self, vertex1, vertex2):
        # For undirected graph
        self.adjacency_list[vertex1].append(vertex2)
        self.adjacency_list[vertex2].append(vertex1)
    
    def remove_edge(self, vertex1, vertex2):
        self.adjacency_list[vertex1] = [v for v in self.adjacency_list[vertex1] if v != vertex2]
        self.adjacency_list[vertex2] = [v for v in self.adjacency_list[vertex2] if v != vertex1]
    
    def remove_vertex(self, vertex):
        while self.adjacency_list[vertex]:
            adjacent_vertex = self.adjacency_list[vertex].pop()
            self.remove_edge(vertex, adjacent_vertex)
        del self.adjacency_list[vertex]

Time Complexity:

• Add Vertex: O(1)
• Add Edge: O(1)
• Remove Edge: O(E) where E is the number of edges
• Remove Vertex: O(V + E) where V is the number of vertices and E is the number of edges
• Space Complexity: O(V + E)

Adjacency Matrices Explained

An adjacency matrix is a 2D array where rows and columns represent vertices. The value at matrix[i][j] indicates if there is an edge from vertex i to vertex j.

Implementation in Python:

class GraphMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # Initialize matrix with zeros
        self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
    
    # Add edge for undirected graph
    def add_edge(self, v1, v2):
        # Set values to 1 to indicate an edge
        self.matrix[v1][v2] = 1
        self.matrix[v2][v1] = 1  # Remove this line for directed graph
    
    # Add edge with weight
    def add_weighted_edge(self, v1, v2, weight):
        self.matrix[v1][v2] = weight
        self.matrix[v2][v1] = weight  # Remove this line for directed graph
    
    # Remove edge
    def remove_edge(self, v1, v2):
        self.matrix[v1][v2] = 0
        self.matrix[v2][v1] = 0  # Remove this line for directed graph
    
    # Check if there is an edge between vertices
    def has_edge(self, v1, v2):
        return self.matrix[v1][v2] != 0
    
    # Get all adjacent vertices of a vertex
    def get_adjacent_vertices(self, v):
        adjacent = []
        for i in range(self.num_vertices):
            if self.matrix[v][i] != 0:
                adjacent.append(i)
        return adjacent

Comparison with Adjacency Lists:

• Adjacency Matrix:
  • Space Complexity: O(V²)
  • Checking if two vertices are connected: O(1)
  • Better for dense graphs
• Adjacency List:
  • Space Complexity: O(V + E)
  • Checking if two vertices are connected: O(V) worst case
  • Better for sparse graphs

Depth-First Traversal (DFT) Explained

Depth-First Traversal is an algorithm used to explore nodes and edges of a graph. It starts at a source node and explores as far as possible along each branch before backtracking.

Recursive Implementation:

class Graph:
    # ... previous methods ...
    
    def depth_first_traversal(self, start):
        result = 
        visited = {}
        
        # Helper function to perform recursive DFT
        def dfs(vertex):
            if not vertex:
                return None
            
            # Mark as visited and add to result
            visited[vertex] = True
            result.append(vertex)
            
            # Visit all neighbors
            for neighbor in self.adjacency_list[vertex]:
                if neighbor not in visited:
                    dfs(neighbor)
        
        # Start traversal
        dfs(start)
        return result
    
    # Iterative implementation using stack
    def depth_first_iterative(self, start):
        stack = [start]
        result = 
        visited = {start: True}
        
        while stack:
            current_vertex = stack.pop()
            result.append(current_vertex)
            
            for neighbor in self.adjacency_list[current_vertex]:
                if neighbor not in visited:
                    visited[neighbor] = True
                    stack.append(neighbor)
        
        return result

Applications of DFT:

• Detecting cycles in a graph
• Topological sorting
• Finding connected components
• Solving mazes and puzzles
• Path finding algorithms