Graph Implementation

Graph Implementation: Adjacency Matrix and Adjacency List

Graphs are one of the most versatile and essential data structures in computer science. From mapping out social networks to determining the shortest path in GPS navigation, graphs model real-world connections flawlessly.

However, understanding what a graph is conceptually is only half the battle. To leverage graphs in your algorithms, you must know how to represent them in code. In this comprehensive guide, we will explore the two most popular ways to implement a graph in Data Structures and Algorithms (DSA): the Adjacency Matrix and the Adjacency List.

1. The Adjacency Matrix

An Adjacency Matrix is a 2D array (or matrix) of size V x V, where V represents the number of vertices (nodes) in the graph.

If a graph has 5 vertices, the adjacency matrix will be a 5x5 grid.

• If there is an edge connecting vertex i to vertex j, the matrix at row i and column j will have a value of 1.
• If there is no edge, the value will be 0.
• For weighted graphs, the value at matrix[i][j] will simply be the weight of the edge instead of 1.

Advantages of Adjacency Matrix

• Fast Edge Lookup: Checking if an edge exists between two specific nodes takes O(1) constant time. You just check matrix[i][j].
• Simple to Implement: A 2D array is a primitive and highly understandable data structure natively supported by almost all programming languages.

Disadvantages of Adjacency Matrix

• High Memory Consumption: It always requires O(V^2) space, regardless of how many edges actually exist. For a graph with 10,000 users and only 20,000 connections, a 10,000x10,000 matrix will waste an enormous amount of memory storing zeros.
• Slow to Add Vertices: Adding a new vertex requires creating a completely new (V+1) x (V+1) matrix and copying over the old data, taking O(V^2) time.

Example: Adjacency Matrix in Python

class Graph:
    def __init__(self, num_vertices):
        self.V = num_vertices
        # Initialize a V x V matrix with all zeros
        self.matrix = [[0 for _ in range(num_vertices)] for _ in range(num_vertices)]
    def add_edge(self, u, v, directed=False):
        # Add an edge from node u to node v
        self.matrix[u][v] = 1
        if not directed:
            # For undirected graphs, add an edge from v back to u
            self.matrix[v][u] = 1 
    def print_graph(self):
        print("Adjacency Matrix:")
        for row in self.matrix:
            print(row)
# Create a graph with 4 vertices (0 to 3)
g = Graph(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

g.print_graph()

2. The Adjacency List

An Adjacency List represents a graph as an array (or dictionary) of lists. The size of the array is equal to the number of vertices.

Instead of storing every possible connection like a matrix, each vertex simply maintains a dynamic list containing only the vertices it is directly connected to.

Advantages of Adjacency List

• Space Efficient: It only requires O(V + E) space, where E is the number of edges. This makes it the absolute best choice for sparse graphs (graphs with few edges relative to nodes).
• Fast Iteration: Finding all the neighbors of a specific vertex takes time proportional only to the number of neighbors, not the total number of vertices in the graph.

Disadvantages of Adjacency List

• Slow Edge Lookup: Checking if an edge exists between node i and node j requires iterating through the list of node i's neighbors. In the worst-case scenario, this takes O(V) time.

Example: Adjacency List in Python

class GraphList:
    def __init__(self, num_vertices):
        self.V = num_vertices
        # Initialize a list of empty lists for each vertex
        self.adj_list = [[] for _ in range(num_vertices)]
    def add_edge(self, u, v, directed=False):
        # Add vertex v to the list of vertex u
        self.adj_list[u].append(v)
        if not directed:
            # For undirected graphs, add u to the list of v
            self.adj_list[v].append(u)
    def print_graph(self):
        print("Adjacency List:")
        for i in range(self.V):
            print(f"Vertex {i}: {self.adj_list[i]}")
# Create a graph with 4 vertices (0 to 3)
g_list = GraphList(4)
g_list.add_edge(0, 1)
g_list.add_edge(0, 2)
g_list.add_edge(1, 2)
g_list.add_edge(2, 3)

g_list.print_graph()

3. Directed and Weighted Graphs

So far, we've primarily discussed Undirected and Unweighted graphs. But real-world data often has strict directions (like Twitter followers) and costs (like distances between cities).

• Directed Graphs: Edges point in a specific direction. In an Adjacency Matrix, this means matrix[A][B] might be 1, but matrix[B][A] might be 0. In an Adjacency List, you only append B to A's list, not vice versa. (Note: Our Python snippets above already support this by simply passing directed=True!)
• Weighted Graphs: Edges have numerical values (weights). In an Adjacency Matrix, instead of storing 1s, you store the actual weight (e.g., matrix[A][B] = 5). In an Adjacency List, you store a tuple or object instead of just the destination node (e.g., adj_list[A].append((B, 5))).

A Directed Weighted Graph alongside its Adjacency Matrix representation.

4. Comparison Summary

To summarize, choosing between these two graph implementations depends heavily on the properties of your data and the operations you need to perform frequently.

Note: Dense graphs are networks where the number of edges is close to the maximum possible number of edges (V^2). Sparse graphs have far fewer edges overall.