Graph Representation

A graph is a map. Imagine a country with cities (vertices, V) connected by roads (edges, E). A graph lets you model any network — flight routes, social connections, web links.

Two ways to store the map

You've built a map of 5 cities. Now where do you write down which roads connect which cities? You have two classic choices:

Adjacency List

Keep a contact list for each city. City A's list says: "I connect to B and C." City B's list says: "I connect to A and D." This is memory-efficient — you only store roads that actually exist. If most cities aren't directly connected, you save a ton of space.

pseudocode

graph = {
  A: [B, C],
  B: [A, D, E],
  C: [A, F],
  D: [B, F],
  E: [B, F],
  F: [C, D, E]
}

Adjacency Matrix

Draw a grid with every city on both axes. Put a 1 in the cell where city X and city Y share a road. Every pair of cities gets a cell — even ones with no road between them. Fast to check "is there a road from X to Y?" — but uses \(V^2\) space even if the map is mostly empty.

pseudocode

A B C D E F
A [0,1,1,0,0,0]
B [1,0,0,1,1,0]
C [1,0,0,0,0,1]
D [0,1,0,0,0,1]
E [0,1,0,0,0,1]
F [0,0,1,1,1,0]

Directed vs Undirected

An undirected graph has two-way roads — if you can drive from A to B, you can drive back. A directed graph (digraph) has one-way streets — a road from A to B doesn't mean there's a road from B to A. Think of Twitter follows vs Facebook friends.

Weighted Graphs

Roads have distances. A weighted graph stores a number on each edge — the cost, distance, or travel time. Weighted graphs are central to shortest-path algorithms like Dijkstra's and Bellman-Ford. In an adjacency list you store pairs: (neighbor, weight). In a matrix you store the weight instead of 1.

Adjacency List & Matrix

# Adjacency List (space-efficient)
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}
print("Neighbors of 0:", graph[0])  # [1, 2]
print("Edge 1-3 exists:", 3 in graph[1])  # True

# Adjacency Matrix (fast edge lookup)
n = 4
matrix = [[0]*n for _ in range(n)]
edges = [(0,1),(0,2),(1,3),(2,3)]
for u, v in edges:
    matrix[u][v] = matrix[v][u] = 1
for row in matrix:
    print(row)

Output

Neighbors of 0: [1, 2]
Edge 1-3 exists: True
[0, 1, 1, 0]
[1, 0, 0, 1]
[1, 0, 0, 1]
[0, 1, 1, 0]

Edge List & Weighted Graph

# Edge list representation
edge_list = [
    (0, 1, 4),   # (from, to, weight)
    (0, 2, 1),
    (1, 3, 2),
    (2, 3, 5)
]

# Build weighted adjacency list
from collections import defaultdict
wgraph = defaultdict(list)
for u, v, w in edge_list:
    wgraph[u].append((v, w))
    wgraph[v].append((u, w))

for node in sorted(wgraph):
    print(f"{node}: {wgraph[node]}")