How do you implement a graph using adjacency list and adjacency matrix?

Python Data Structures - Interview Questions and Answers

Implementing a Graph Using Adjacency List and Adjacency Matrix in Python

Graphs can be represented in two primary ways:
1. Adjacency List – Space-efficient for sparse graphs.
2. Adjacency Matrix – Faster lookups but uses more space.

1. Graph Representation: Adjacency List

An adjacency list uses a dictionary where each key is a node, and the value is a list of adjacent nodes.
* Efficient for sparse graphs (O(V + E) space).
* Faster traversal (O(V + E) time complexity).
* Slower edge lookups (O(degree) time).

Implementation of Graph Using Adjacency List

class GraphAdjList:
    def __init__(self):
        self.graph = {}  # Dictionary to store adjacency list

    def add_edge(self, u, v):
        """ Adds an edge from u to v (undirected) """
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)  # Remove this for a directed graph

    def display(self):
        """ Prints adjacency list """
        for node in self.graph:
            print(f"{node} -> {self.graph[node]}")

# Example usage
g = GraphAdjList()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(3, 4)

g.display()
# Output:
# 1 -> [2, 3]
# 2 -> [1, 4]
# 3 -> [1, 4]
# 4 -> [2, 3]

* Best for graphs with fewer edges (sparse graphs).

2. Graph Representation: Adjacency Matrix

An adjacency matrix is a 2D matrix (V × V) where matrix[i][j] = 1 if there is an edge, otherwise 0.
* Fast edge lookup O(1).
* Good for dense graphs.
* Consumes more space O(V²).

Implementation of Graph Using Adjacency Matrix

class GraphAdjMatrix:
    def __init__(self, size):
        self.size = size
        self.matrix = [[0] * size for _ in range(size)]  # Initialize with zeros

    def add_edge(self, u, v):
        """ Adds an edge from u to v (undirected) """
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1  # Remove this for a directed graph

    def display(self):
        """ Prints adjacency matrix """
        for row in self.matrix:
            print(row)

# Example usage
g = GraphAdjMatrix(5)  # 5 nodes (0-4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)

g.display()
# Output:
# [0, 1, 1, 0, 0]
# [1, 0, 0, 1, 0]
# [1, 0, 0, 0, 1]
# [0, 1, 0, 0, 0]
# [0, 0, 1, 0, 0]

* Best for dense graphs (many edges).

3. Comparison: Adjacency List vs. Adjacency Matrix

Feature	Adjacency List	Adjacency Matrix
Space Complexity	O(V + E)	O(V²)
Edge Lookup	O(degree)	O(1)
Adding an Edge	O(1)	O(1)
Removing an Edge	O(degree)	O(1)
Best for	Sparse Graphs	Dense Graphs

4. When to Use Each?

* Adjacency List – When memory efficiency is needed (e.g., social networks, road networks).
* Adjacency Matrix – When fast edge lookup is required (e.g., Floyd-Warshall shortest path algorithm).