Adjacency Matrix Powering (Paths via Matrix Exponentiation)

Graph representation chooses how you store neighbors—adjacency lists are sparse-friendly; matrices help dense graphs and quick edge(u,v) checks.

Why this shows up in the real world

Maps & routing, social networks, and dependency systems are modeled as graphs—vertices are places or tasks, edges are roads or prerequisites.

Core idea (explained for students)

List: adj[u] = neighbors. Matrix: M[u][v]=1 or weight. Pick list when E is small; matrix when you need O(1) edge queries or Floyd–Warshall.

Try this in Python

# adjacency list: adj[u] = neighbors of u
adj: list[list[int]] = [
    [1, 2],
    [0, 3],
    [0],
    [1],
]
print(len(adj), adj[0])

Common mistakes

• Confusing directed vs undirected (store both directions?).
• O(n²) matrix when n=10⁵.

Key takeaways

• Default to adjacency list in interviews.
• Convert grid problems to nodes with 4-neighbor edges.