13. Graph Representation

What you'll learn

• 1Choose between adjacency list and adjacency matrix
• 2Handle directed, undirected, weighted edges
• 3Read BOJ-style graph input quickly

Overview

Most graph algorithms work with either an adjacency list or an adjacency matrix. The list is space-efficient (O(V + E)); the matrix gives O(1) edge lookup but uses O(V²) space. For competitive programming, adjacency list is the default.

Core Concepts

1. Adjacency list

n = 5
adj = [[] for _ in range(n + 1)]    # 1-indexed nodes
edges = [(1, 2), (1, 3), (2, 4), (3, 5)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)   # remove this line for directed graphs

# Neighbors of node 1
for neighbor in adj[1]:
    ...   # O(degree)

2. Adjacency matrix

n = 5
mat = [[0] * (n + 1) for _ in range(n + 1)]
edges = [(1, 2), (1, 3)]
for u, v in edges:
    mat[u][v] = 1
    mat[v][u] = 1

# Is there an edge u-v?
mat[u][v]   # O(1)

3. Weighted graphs

# adjacency list with weights
adj = [[] for _ in range(n + 1)]
for u, v, w in weighted_edges:
    adj[u].append((v, w))
    adj[v].append((u, w))

for next_v, weight in adj[u]:
    ...

4. Comparison

Examples

Example 1 — src/01_adj_list.py

Build adjacency list from BOJ-format input, print all edges.

Example 2 — src/02_adj_matrix.py

Adjacency matrix with O(1) edge query.

Example 3 — src/03_weighted.py

Adjacency list with weights — needed for Dijkstra.

Example 4 — src/04_grid_as_graph.py

Treat a 2D grid as a graph with 4-directional movement (BFS/DFS staple).

Common Mistakes

1. Forgetting to add both directions for an undirected graph.
2. Using 0-indexed `adj = [[] for _ in range(n)]` when input is 1-indexed → IndexError or off-by-one.
3. Choosing a matrix when V > 1000 — runs out of memory.
4. Inserting duplicate edges silently when input contains parallel edges.

Recap

• Adjacency list is the default for sparse graphs.
• Adjacency matrix is reserved for dense graphs (V ≤ 500) or Floyd-Warshall.
• Weighted edges → use tuples in the adjacency list.

Try It

1. BOJ 1260 (DFS and BFS) — read graph, run both.
2. Build the adjacency list, then for each node print its neighbors.