Graph Representation

Prev Next

A graph is a set of vertices (nodes) connected by edges. Trees, which you've already seen, are actually a restricted special case of graphs (no cycles, exactly one path between any two nodes). Graphs drop those restrictions — any node can connect to any other, cycles are allowed, and a node can have any number of connections. Before running any graph algorithm you need to decide how to store one in memory — that's what this lesson covers.

Types of Graphs

Property	Meaning
Directed	Edges have a direction — an edge A→B does not imply B→A (e.g. "follows" on social media)
Undirected	Edges go both ways — if A connects to B, B connects to A (e.g. a friendship, a road between two cities)
Weighted	Each edge carries a cost/distance/value (e.g. flight duration, road distance)
Unweighted	Edges are just present or absent, with no associated cost

Example Graph

We'll represent this small undirected, weighted graph with 4 vertices both ways:

    A --- 4 --- B
    |           |
    2           3
    |           |
    C --- 1 --- D

Edges: A-B (4), A-C (2), B-D (3), C-D (1). Using integer indices A=0, B=1, C=2, D=3.

Adjacency Matrix

A 2D grid — in Python, a list of lists — where matrix[i][j] holds the edge weight between vertex i and j (or 0 if there's no edge). For an undirected graph, the matrix is symmetric.

# 4 vertices: A=0, B=1, C=2, D=3. 0 means "no edge".
matrix = [[0] * 4 for _ in range(4)]

def add_edge(matrix, u, v, weight):
    matrix[u][v] = weight
    matrix[v][u] = weight  # undirected -> set both directions

add_edge(matrix, 0, 1, 4)  # A-B
add_edge(matrix, 0, 2, 2)  # A-C
add_edge(matrix, 1, 3, 3)  # B-D
add_edge(matrix, 2, 3, 1)  # C-D

# Is there an edge between A(0) and C(2)? One list lookup:
connected = matrix[0][2] != 0  # True, weight 2

Time complexity: O(1) to check if an edge exists or read its weight — direct list indexing. Space complexity: O(V²) — the matrix allocates a slot for every possible pair of vertices, whether or not an edge exists between them.

Adjacency List

Instead of a full grid, each vertex keeps a list of only its actual neighbors (and, for a weighted graph, the weight to each). In Python the natural, idiomatic way to build this is a dict mapping each node to a list of (neighbor, weight) tuples — no fixed-size array required at all, and it reads almost like the graph itself. This is dramatically smaller for sparse graphs — most real-world graphs (social networks, road maps, dependency graphs) have far fewer edges than the V² a matrix would reserve space for.

# One dict entry per vertex, holding only its actual neighbors.
adj = {0: [], 1: [], 2: [], 3: []}

def add_edge(adj, u, v, weight):
    adj[u].append((v, weight))
    adj[v].append((u, weight))  # undirected -> add both directions

add_edge(adj, 0, 1, 4)  # A-B
add_edge(adj, 0, 2, 2)  # A-C
add_edge(adj, 1, 3, 3)  # B-D
add_edge(adj, 2, 3, 1)  # C-D

# Neighbors of A(0): iterate its list directly.
for neighbor, weight in adj[0]:
    print(f"A -> {neighbor} (weight {weight})")
# A -> 1 (weight 4)
# A -> 2 (weight 2)

Time complexity: O(degree(v)) to list vertex v's neighbors — you only touch edges that actually exist, versus scanning a full row of V in a matrix. Checking a specific edge is O(degree(v)) worst case (scanning the list) rather than O(1). Space complexity: O(V + E) — one dict entry per vertex plus one list entry per edge (two entries per undirected edge), far smaller than V² when E is much less than V².

Why a dict, not a list of lists: unlike Java where vertices are usually dense integer indices into an ArrayList, Python's dict lets a vertex be anything hashable — a string name, a tuple coordinate, an object — with no separate index-mapping step. That flexibility is a big part of why the adjacency list is the default choice in idiomatic Python graph code.

Which One Should You Pick?

Situation	Use
Dense graph (E close to V²)	Adjacency Matrix — O(1) edge checks, the space overhead is less painful
Sparse graph (most real graphs)	Adjacency List — much less memory, and traversal algorithms (BFS/DFS) only ever need each vertex's actual neighbors
Need "is there an edge from A to B?" very frequently	Adjacency Matrix, or a dict-of-sets adjacency list for O(1) lookups with list-like space savings
Running BFS, DFS, Dijkstra, MST algorithms	Adjacency List (dict of lists) — the standard choice for almost every graph algorithm you'll implement

Default to the adjacency list. Nearly every graph algorithm in this track — BFS, DFS, Dijkstra, Kruskal, Prim — is written against a dict-based adjacency list, because most interview graphs are sparse and traversal only ever needs "give me this node's neighbors," which a dict lookup gives you directly.

Next up: now that a graph can be stored, BFS & DFS covers the two fundamental ways to actually walk through one.

Prev Next