Chapter 67

Refactoring: Choosing Representation

Picking the wrong graph representation costs time or memory. Here's the decision framework — and how to switch between them when a problem demands it.

Decision Framework

Use adjacency list when:

Sparse graph (E ≪ V²). V can be large (10⁵+). You need to iterate neighbours. This is 90% of problems.

Use adjacency matrix when:

V ≤ 1000. You need O(1) edge queries. You're using Floyd-Warshall. The graph is dense (E ≈ V²/2).

🚨 Wrong choice consequences

Matrix for V=10⁵: 10¹⁰ entries = 40 GB. List for dense V=10³: O(V²) iterations if you frequently check edge existence. Match the tool to the graph.

Converting Between Representations

C++ — list → matrix

vector> list_to_matrix(vector>& adj, int V) {
    vector> mat(V, vector(V, 0));
    for (int u = 0; u < V; u++)
        for (int v : adj[u])
            mat[u][v] = 1;
    return mat;
}

Key Takeaways

→Adj list: O(V+E) memory — default choice.
→Adj matrix: O(V²) memory — only for V ≤ 1000 or dense graphs.
→Know both — problems sometimes force one or the other.

Practice

Codeforces 1730A: Planets