Algorithm Graph Representations Adjacency List And Matrix Complete Guide

Graph Representation: Adjacency List

Concept:

• An adjacency list is a collection of unordered lists or arrays used to represent a finite graph.
• Each list describes the set of neighbors of a node in the graph.
• This representation is space-efficient for sparse graphs (graphs with relatively few edges).

Example Problem:

• Consider a simple undirected graph with 4 vertices and 5 edges as shown below:

  A -- B
  | \  |
  |  \ |
  C -- D
  

Steps to Represent the Graph Using an Adjacency List:

1. Initialize the Adjacency List:

   • Create a dictionary (or hashmap) where each key is a vertex, and the value is a list of neighboring vertices.

   from collections import defaultdict
   
   # Initialize an empty adjacency list
   adjacency_list = defaultdict(list)
   

2. Add Edges to the Adjacency List:

   • For each edge, add both vertices to each other's neighbor lists.

   # Add edges (A, B), (A, C), (A, D), (B, D), (C, D)
   edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'D'), ('C', 'D')]
   
   for src, dest in edges:
       adjacency_list[src].append(dest)
       adjacency_list[dest].append(src)
   
   # Print the resulting adjacency list
   print(adjacency_list)
   

   Output:

   defaultdict(<class 'list'>, {
       'A': ['B', 'C', 'D'],
       'B': ['A', 'D'],
       'C': ['A', 'D'],
       'D': ['A', 'B', 'C']
   })
   

3. Using the Adjacency List:

   • You can iterate over each vertex's neighbors to perform operations like depth-first search (DFS) or breadth-first search (BFS).

   # Function to perform DFS starting from a given vertex
   def dfs(graph, start_vertex):
       visited = set()
       stack = [start_vertex]
   
       while stack:
           vertex = stack.pop()
           if vertex not in visited:
               print(vertex, end=' ')
               visited.add(vertex)
   
               for neighbor in reversed(graph[vertex]):
                   if neighbor not in visited:
                       stack.append(neighbor)
   
   print("\nDepth-First Search starting from vertex A:")
   dfs(adjacency_list, 'A')
   

   Output:

   Depth-First Search starting from vertex A:
   A D B C 
   

Summary of the Adjacency List Example:

• Initialization: We start by creating a defaultdict to store each vertex and its neighboring vertices.
• Adding Edges: For each edge, we append the destination vertex to the source vertex's list and vice versa to account for undirected edges.
• Traversal: We use the adjacency list to perform DFS, iterating through each vertex's neighbors efficiently.

Graph Representation: Adjacency Matrix

Concept:

• An adjacency matrix is a two-dimensional array representing the number of edges between each pair of vertices in the graph.
• If there is an edge between vertex i and vertex j, then the cell at position (i, j) will be marked with 1; otherwise, it will be marked with 0.
• For weighted graphs, the cell (i, j) would contain the weight of the edge instead of 1.
• This representation is efficient for dense graphs (graphs with many edges).

Example Problem:

• Consider the same simple undirected graph as before:

  A -- B
  | \  |
  |  \ |
  C -- D
  

Steps to Represent the Graph Using an Adjacency Matrix:

1. Define Vertices and Initialize the Matrix:

   • Determine the number of vertices in the graph.
   • Create a square matrix of size n x n (where n is the number of vertices) and initialize all elements to 0.

   # Define the vertices
   vertices = ['A', 'B', 'C', 'D']
   
   # Number of vertices
   n = len(vertices)
   
   # Initialize an n x n matrix filled with zeros
   adjacency_matrix = [[0] * n for _ in range(n)]
   
   # Create a mapping from vertices to indices
   vertex_index_map = {vertices[i]: i for i in range(n)}
   

2. Add Edges to the Adjacency Matrix:

   • For each edge, mark the corresponding cells in the matrix with 1.

   # Add edges (A, B), (A, C), (A, D), (B, D), (C, D)
   edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'D'), ('C', 'D')]
   
   for src, dest in edges:
       # Get the indices of the source and destination vertices
       src_idx = vertex_index_map[src]
       dest_idx = vertex_index_map[dest]
   
       # Mark the edge in the matrix
       adjacency_matrix[src_idx][dest_idx] = 1
       adjacency_matrix[dest_idx][src_idx] = 1  # For undirected graph
   
   # Print the resulting adjacency matrix
   print("Vertices:", vertices)
   print("Adjacency Matrix:")
   for row in adjacency_matrix:
       print(row)
   

   Output:

   Vertices: ['A', 'B', 'C', 'D']
   Adjacency Matrix:
   [0, 1, 1, 1]
   [1, 0, 0, 1]
   [1, 0, 0, 1]
   [1, 1, 1, 0]
   

3. Using the Adjacency Matrix:

   • You can access the neighbors of a vertex by iterating over its row in the matrix and checking for non-zero values.

   # Function to perform BFS starting from a given vertex
   from collections import deque
   
   def bfs(graph, start_vertex, vertices, vertex_index_map):
       visited = set()
       queue = deque([start_vertex])
   
       while queue:
           vertex = queue.popleft()
           if vertex not in visited:
               print(vertex, end=' ')
               visited.add(vertex)
   
               # Get the index of the current vertex
               vertex_idx = vertex_index_map[vertex]
   
               # Iterate over neighbors in the adjacency matrix
               for i in range(len(graph[vertex_idx])):
                   if graph[vertex_idx][i] == 1 and vertices[i] not in visited:
                       queue.append(vertices[i])
   
   print("\nBreadth-First Search starting from vertex A:")
   bfs(adjacency_matrix, 'A', vertices, vertex_index_map)
   

   Output:

   Breadth-First Search starting from vertex A:
   A B C D 
   

Summary of the Adjacency Matrix Example:

• Initialization: We define the vertices and create a square matrix filled with zeros.
• Mapping: We create a dictionary to map each vertex to an index for easy matrix manipulation.
• Adding Edges: For each edge, we update the corresponding cells in the matrix to mark the presence of an edge.
• Traversal: We use the adjacency matrix to perform BFS, checking the neighbors of a vertex by inspecting its row in the matrix.

Key Differences Between Adjacency List and Adjacency Matrix:

| Aspect | Adjacency List | Adjacency Matrix | |--------------------|-----------------------------------------------|-----------------------------------------| | Space Complexity | O(V + E) | O(V^2) | | Time to Check Edge | O(E/V) - in the worst case | O(1) | | Time to Iterate Over Neighbors | O(degree of the vertex) | O(V) | | Use Cases | Sparse graphs | Dense graphs | | Ease of Modification | Adding/removing edges is efficient | Adding/removing edges is less efficient |

Notes:

• Adding/Removing Vertices: Adjacency lists handle adding/removing vertices more efficiently than matrices, especially for sparse graphs.
• Weighted Graphs: In an adjacency matrix, you can store weights directly in place of 1s. In an adjacency list, you can store tuples containing the neighboring vertex and the edge weight.

Complete Example Code:

Here's the complete code for both the adjacency list and adjacency matrix representations:

from collections import defaultdict, deque

# Adjacency List Representation
def adjacency_list_example():
    # Initialize an empty adjacency list
    adjacency_list = defaultdict(list)
    
    # Define edges
    edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'D'), ('C', 'D')]
    
    # Add edges to the adjacency list
    for src, dest in edges:
        adjacency_list[src].append(dest)
        adjacency_list[dest].append(src)  # For undirected graph
    
    # Print the resulting adjacency list
    print("Adjacency List:")
    for vertex, neighbors in adjacency_list.items():
        print(f"{vertex}: {neighbors}")
        
    # Function to perform DFS starting from a given vertex
    def dfs(graph, start_vertex):
        visited = set()
        stack = [start_vertex]
        
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                print(vertex, end=' ')
                visited.add(vertex)
                
                for neighbor in reversed(graph[vertex]):
                    if neighbor not in visited:
                        stack.append(neighbor)
    
    print("\nDepth-First Search (DFS) starting from vertex A:")
    dfs(adjacency_list, 'A')

# Adjacency Matrix Representation
def adjacency_matrix_example():
    # Define the vertices
    vertices = ['A', 'B', 'C', 'D']
    
    # Number of vertices
    n = len(vertices)
    
    # Initialize an n x n matrix filled with zeros
    adjacency_matrix = [[0] * n for _ in range(n)]
    
    # Create a mapping from vertices to indices
    vertex_index_map = {vertices[i]: i for i in range(n)}
    
    # Define edges
    edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'D'), ('C', 'D')]
    
    # Add edges to the adjacency matrix
    for src, dest in edges:
        src_idx = vertex_index_map[src]
        dest_idx = vertex_index_map[dest]
        
        adjacency_matrix[src_idx][dest_idx] = 1
        adjacency_matrix[dest_idx][src_idx] = 1  # For undirected graph
    
    # Print the resulting adjacency matrix
    print("\nVertices:", vertices)
    print("Adjacency Matrix:")
    for row in adjacency_matrix:
        print(row)
        
    # Function to perform BFS starting from a given vertex
    def bfs(graph, start_vertex, vertices, vertex_index_map):
        visited = set()
        queue = deque([start_vertex])
        
        while queue:
            vertex = queue.popleft()
            if vertex not in visited:
                print(vertex, end=' ')
                visited.add(vertex)
                
                vertex_idx = vertex_index_map[vertex]
            
                for i in range(len(graph[vertex_idx])):
                    if graph[vertex_idx][i] == 1 and vertices[i] not in visited:
                        queue.append(vertices[i])
    
    print("\nBreadth-First Search (BFS) starting from vertex A:")
    bfs(adjacency_matrix, 'A', vertices, vertex_index_map)

if __name__ == "__main__":
    print("=== Adjacency List Representation ===")
    adjacency_list_example()
    
    print("\n=== Adjacency Matrix Representation ===")
    adjacency_matrix_example()

Output: