Graph Representation

Concept

There are 3 main ways to store a graph in memory: edge list, adjacency list, and adjacency matrix. Each has different tradeoffs in space, speed, and which algorithms they work best with. Choosing the right representation is the first step in solving any graph problem.

When to Use

  • ▸Edge list — Kruskal's MST (sort edges by weight), Bellman-Ford (iterate all edges)
  • ▸Adjacency list — BFS, DFS, Dijkstra, topological sort — the most common and versatile
  • ▸Adjacency matrix — Floyd-Warshall, Prim's, dense graphs where you need O(1) edge lookup

Intuition

Edge list is just a bag of edges — simple but you can't quickly find neighbors of a node. Adjacency list stores a neighbor list per node — perfect for traversal since you directly iterate a node's neighbors. Adjacency matrix is a 2D table where adj[u][v] = weight — instant edge lookup but uses O(V^2) space so only works for small V. Most contest problems use adjacency list because it's space-efficient and supports all common algorithms.

Complexity

Time
Edge list: O(E) traverse, O(E) find neighbors | Adj list: O(degree) find neighbors | Adj matrix: O(1) edge lookup, O(V) find neighbors
Space
Edge list: O(E) | Adj list: O(V + E) | Adj matrix: O(V^2)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m;
    cin >> n >> m;

    // ============================================
    // 1. EDGE LIST
    // ============================================

    // Style A: {weight, {u, v}} — used in Kruskal
    // Sort by weight automatically with sort()
    vector<pair<int, pair<int, int>>> edges;

    int a, b, w;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> w;
        edges.push_back({w, {a, b}});
    }
    sort(edges.begin(), edges.end());

    // Style B: {{u, v}, weight} — used in Bellman-Ford
    // vector<pair<pair<int, int>, int>> edges;
    // for(int i = 0; i < m; i++){
    //     int u, v, w;
    //     cin >> u >> v >> w;
    //     edges.push_back({{u, v}, w});
    // }

    // ============================================
    // 2. ADJACENCY LIST (most common)
    // ============================================

    // Unweighted undirected graph
    vector<vector<int>> adj1(n);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        adj1[a].push_back(b);
        adj1[b].push_back(a);   // remove for directed
    }

    // Weighted undirected graph {neighbor, weight}
    vector<vector<pair<int, int>>> adj2(n);
    for(int i = 0; i < m; i++){
        int a, b, w;
        cin >> a >> b >> w;
        adj2[a].push_back({b, w});
        adj2[b].push_back({a, w});  // remove for directed
    }

    // Weighted directed graph (1-indexed)
    // vector<vector<pair<long long, long long>>> adj(n+1);
    // for(int i = 0; i < m; i++){
    //     long long a, b, c;
    //     cin >> a >> b >> c;
    //     adj[a].push_back({b, c});
    // }

    // C-style (works but not preferred):
    // vector<int> adj[n];

    // ============================================
    // 3. ADJACENCY MATRIX
    // ============================================

    // Used for Floyd-Warshall, Prim, dense graphs
    const int inf = 1e9+7;
    vector<vector<int>> adj3(n, vector<int>(n, inf));

    for(int i = 0; i < n; i++) adj3[i][i] = 0;

    int u, v;
    for(int i = 0; i < m; i++){
        cin >> u >> v >> w;
        adj3[u][v] = w;
        adj3[v][u] = w;  // remove for directed
    }

    return 0;
}

// Summary:
// +-----------------+------------------+--------------------+
// | Representation  | Best for         | Space              |
// +-----------------+------------------+--------------------+
// | Edge list       | Kruskal, B-Ford  | O(E)               |
// | Adjacency list  | BFS, DFS, Dijk   | O(V + E)           |
// | Adjacency matrix| Floyd, Prim      | O(V^2)             |
// +-----------------+------------------+--------------------+