Graph Representation

Analogy categoryAnalogies

Introduction

A graph is a data structure made of vertices (nodes) connected by edges. Graphs model relationships such as social networks, road maps, and dependency chains. Unlike trees, graphs can contain cycles and a vertex can have any number of neighbors. Choosing the right representation is the first decision when solving a graph problem, since it determines the time and space complexity of every algorithm you build on top of it.

🏏

Cricket analogy: Like a network of players connected by "has played alongside" edges — unlike a tournament bracket tree, this network can loop back (two players teamed up on multiple franchises), and how you record those connections shapes every stat query you run later.

Representation/Syntax

python

from collections import defaultdict

# Adjacency list using a dictionary of lists
adj_list = defaultdict(list)

def add_edge(u, v, directed=False):
    adj_list[u].append(v)
    if not directed:
        adj_list[v].append(u)

add_edge('A', 'B')
add_edge('A', 'C')
add_edge('B', 'D')

print(dict(adj_list))

# Adjacency matrix using a 2D list
n = 4  # number of vertices, indexed 0..3
adj_matrix = [[0] * n for _ in range(n)]
adj_matrix[0][1] = 1
adj_matrix[1][0] = 1  # undirected edge 0-1

# Edge list
edge_list = [(0, 1), (0, 2), (1, 3)]

Explanation

An adjacency list stores, for each vertex, only its actual neighbors, so it uses O(V + E) space and is efficient for sparse graphs — most real-world graphs. An adjacency matrix uses a V x V grid where cell [i][j] indicates an edge between i and j; it takes O(V^2) space but gives O(1) edge-existence lookups, which suits dense graphs or algorithms that repeatedly ask 'are u and v connected?'. An edge list is simply a list of (u, v) pairs, compact and convenient for algorithms like Kruskal's that process edges independent of vertex structure, but slow for neighbor lookups since it requires a scan.

🏏

Cricket analogy: An adjacency list is like each player keeping a short list of only the teammates they've actually played with, efficient when most players share few teammates; an adjacency matrix is a full grid of every possible pairing marked yes/no, instant lookup but wasteful if most pairs never played together; an edge list is just a flat list of "player A played with player B" pairs, compact but slow to check a specific pairing.

Example

python

class Graph:
    def __init__(self, directed=False):
        self.directed = directed
        self.adj = defaultdict(list)

    def add_edge(self, u, v, weight=1):
        self.adj[u].append((v, weight))
        if not self.directed:
            self.adj[v].append((u, weight))

    def neighbors(self, u):
        return self.adj[u]

g = Graph()
g.add_edge('A', 'B', 5)
g.add_edge('A', 'C', 2)
for node, weight in g.neighbors('A'):
    print(f'A -> {node} (weight {weight})')

Complexity

Adjacency list: O(V + E) space, O(1) to add an edge, O(degree(v)) to iterate neighbors, O(degree(v)) to check if an edge exists. Adjacency matrix: O(V^2) space regardless of edge count, O(1) to check or add an edge, O(V) to iterate neighbors. For sparse graphs (E much less than V^2), adjacency lists are almost always preferred; for dense graphs or when constant-time edge lookups matter, matrices win.

🏏

Cricket analogy: An adjacency list costs O(V+E) space and lets you instantly list a player's actual co-players in O(degree) time; an adjacency matrix costs O(V^2) space regardless of how many pairs actually played together, but checking one specific pair is O(1), lists win for a sparse domestic circuit, matrices for a small round-robin where every check matters.

Key Takeaways

Adjacency list: O(V+E) space, best for sparse graphs and neighbor iteration.
Adjacency matrix: O(V^2) space, best for dense graphs and O(1) edge lookups.
Edge lists are compact and ideal for edge-centric algorithms like Kruskal's MST.
Directed graphs add edges one-way; undirected graphs add edges to both endpoints.
Weighted graphs store (neighbor, weight) pairs instead of plain neighbors.

Practice what you learned

1. What is the space complexity of an adjacency list for a graph with V vertices and E edges?

2. Which representation gives O(1) time to check if an edge exists between two vertices?

3. For a sparse graph with V=10000 and E=15000, which representation is most space-efficient?

4. In an undirected graph represented as an adjacency list, adding edge (A, B) requires which action?

5. Which representation is most convenient for algorithms like Kruskal's that sort all edges globally?

Was this page helpful?

Graph Traversal: BFS and DFS

Topics covered

#Python#DataStructuresStudyNotes#DataStructures#GraphRepresentation#Graph#Representation#Syntax#Explanation#StudyNotes#SkillVeris