Graph representations

A graph has vertices (nodes) and edges. Represent with adjacency list (vector of neighbors—sparse friendly) or adjacency matrix (n×n—dense, O(1) edge lookup).

Directed vs undirected

• Undirected — edge (u,v) both ways
• Directed — edge u → v only
• Weighted — cost on edges (distances, capacities)

Adjacency list

#include 
#include 

int main() {
    int n = 4;
    std::vector> adj(n);
    auto add = [&](int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    };
    add(0, 1); add(0, 2); add(1, 3);
    std::cout << "neighbors of 0: ";
    for (int v : adj[0]) std::cout << v << " ";
    std::cout << "\n";
    return 0;
}

Space

List: O(V+E). Matrix: O(V²). Social networks and road maps are usually sparse—lists win.

Important interview questions and answers

1. Q: When matrix?
   A: Dense graphs, need fast edge existence check, small fixed V.
2. Q: SciPy sparse link?
   A: CSR sparse matrices mirror adjacency lists—see SciPy sparse preview.

Self-check

1. Compare adjacency list vs matrix space.
2. How add undirected edge in list form?

Pitfall: Building adjacency matrix for sparse graphs wastes O(V²) memory.