Graph Representation

Overview

A graph is stored either as an adjacency list — a map from each vertex to its neighbors — or an adjacency matrix, a V×V grid of edge flags. Adjacency lists use O(V + E) space and iterate a vertex's neighbors in O(degree), which suits sparse graphs. Adjacency matrices use O(V²) space but answer "is there an edge between u and v?" in O(1), which suits dense graphs or frequent edge lookups.

Syntax / Usage

An adjacency list built with a defaultdict is the most common representation.

from collections import defaultdict

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

    def add_edge(self, u, v):        # O(1) for an undirected edge
        self.adj[u].append(v)
        self.adj[v].append(u)

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

g = Graph()
g.add_edge("a", "b")
g.add_edge("a", "c")
print(g.neighbors("a"))  # ['b', 'c']

Examples

An adjacency matrix gives O(1) edge existence checks at the cost of O(V²) memory:

class MatrixGraph:
    def __init__(self, n):
        self.n = n
        self.matrix = [[0] * n for _ in range(n)]

    def add_edge(self, u, v):     # O(1)
        self.matrix[u][v] = 1
        self.matrix[v][u] = 1

    def has_edge(self, u, v):     # O(1)
        return self.matrix[u][v] == 1

g = MatrixGraph(3)
g.add_edge(0, 1)
print(g.has_edge(0, 1))  # True
print(g.has_edge(0, 2))  # False

Run breadth-first search over an adjacency list to visit nodes level by level:

from collections import deque

def bfs(adj, start):
    visited = [start]
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in adj[node]:
            if neighbor not in visited:
                visited.append(neighbor)
                queue.append(neighbor)
    return visited

adj = {"a": ["b", "c"], "b": ["d"], "c": [], "d": []}
print(bfs(adj, "a"))  # ['a', 'b', 'c', 'd']

Common Mistakes

• Using an adjacency matrix for large sparse graphs, wasting O(V²) memory
• Adding an edge in only one direction when the graph is meant to be undirected
• Checking neighbor not in visited on a list (O(n)); a set makes lookups O(1)
• Assuming neighbor order is meaningful — it reflects insertion, not any sorting
• Forgetting isolated vertices that have no edges and never appear in an edge list

See Also

data-structures-graphs data-structures-hash-tables data-structures-priority-queues