Graph Representation (C++)

The most straightforward way to represent a graph is with a two-dimensional table (matrix). Imagine a spreadsheet where both the rows and columns are labeled with vertex numbers. Each cell in this table answers one simple question: "Is there an edge between vertex i and vertex j?"

If the answer is yes, we put a 1 (or the edge weight) in that cell. If no, we put a 0.

Think of a classroom seating chart. You have a grid where each row is a student and each column is also a student. If two students are friends, you mark an X in the cell where their row and column intersect. This grid is your adjacency matrix.

For a graph with V vertices, we create a V × V matrix called adj. For each edge (u, v):

• Undirected graph: Set adj[u][v] = 1 AND adj[v][u] = 1 (friendship is mutual)
• Directed graph: Set only adj[u][v] = 1 (a one-way connection)
• Weighted graph: Store the weight instead of 1: adj[u][v] = weight

In C++, the most natural way to create this matrix is using a 2D vector: vector<vector<int>> adj(V, vector<int>(V, 0)); — this gives us a V×V grid initialized to all zeros, ready to be filled as we process edges.

Let's build the adjacency matrix for Example 1: V = 3, edges = [(0,1), (0,2), (1,2)], undirected.

Step 1: Create a 3×3 matrix initialized with all zeros.

mat = [[0, 0, 0],
       [0, 0, 0],
       [0, 0, 0]]

Each cell mat[i][j] represents whether there is an edge from vertex i to vertex j.

Step 2: Process edge (0, 1). Set mat[0][1] = 1.

mat = [[0, 1, 0],
       [0, 0, 0],
       [0, 0, 0]]

Step 3: Since the graph is undirected, also set mat[1][0] = 1 (the mirror entry).

mat = [[0, 1, 0],
       [1, 0, 0],
       [0, 0, 0]]

Step 4: Process edge (0, 2). Set mat[0][2] = 1.

mat = [[0, 1, 1],
       [1, 0, 0],
       [0, 0, 0]]

Step 5: Mirror entry: set mat[2][0] = 1.

mat = [[0, 1, 1],
       [1, 0, 0],
       [1, 0, 0]]

Step 6: Process edge (1, 2). Set mat[1][2] = 1.

mat = [[0, 1, 1],
       [1, 0, 1],
       [1, 0, 0]]

Step 7: Mirror entry: set mat[2][1] = 1.

mat = [[0, 1, 1],
       [1, 0, 1],
       [1, 1, 0]]

Step 8: All 3 edges have been processed. The adjacency matrix is complete. Notice the matrix is symmetric along the diagonal (because the graph is undirected), and the diagonal itself is all zeros (no self-loops).

1. Read the number of vertices V and edges E.
2. Create a V × V matrix (2D array) initialized with all zeros.
3. For each edge (u, v) in the input:
   • Set mat[u][v] = 1 (or the weight for weighted graphs).
   • If the graph is undirected, also set mat[v][u] = 1 (mirror entry).
   • If the graph is directed, only set mat[u][v] (one direction).
4. The matrix is now ready. To check if an edge exists between vertices i and j, simply read mat[i][j].
5. To find all neighbors of vertex i, scan the entire row i and collect all columns j where mat[i][j] != 0.

Time Complexity:

• Building the matrix: O(V² + E)

  • Initializing the V×V matrix takes O(V²) time (every cell set to 0).
  • Processing each of the E edges takes O(1) per edge (direct cell assignment), so O(E) total.
  • Overall: O(V²) dominates since V² ≥ E for simple graphs.

• Checking if edge (u, v) exists: O(1) — direct array lookup mat[u][v].

• Finding all neighbors of vertex u: O(V) — must scan the entire row u, checking each of the V cells.

Space Complexity: O(V²)

The matrix always uses V² cells regardless of how many edges actually exist. For a graph with 1,000 vertices but only 5 edges, we still allocate 1,000,000 cells — 999,990 of which are wasted zeros. This is the key limitation of the adjacency matrix.

Instead of reserving space for every possible edge (V² cells), what if we only stored the edges that actually exist?

Imagine a phone contact list. You do not have a slot for every person in the world — you only store the numbers of people you actually know. Each person has their own list of contacts, and the length of each list varies.

The adjacency list works the same way. We create an array of V lists (one per vertex). For each edge (u, v):

• Add v to vertex u's list (vertex u has neighbor v)
• For undirected graphs, also add u to vertex v's list

Now each vertex stores only its actual neighbors — no wasted space for non-existent edges.

In C++, the most idiomatic way is to use a vector of vectors: vector<vector<int>> adj(V);. Each inner vector adj[i] starts empty and grows dynamically as we add neighbors using push_back(). For weighted graphs, we use vector<vector<pair<int,int>>> adj(V); where each pair stores (neighbor, weight).

This is the standard representation used in nearly all competitive programming and real-world graph algorithms (BFS, DFS, Dijkstra, etc.) because it is both space-efficient and fast for neighbor iteration.

Let's build the adjacency list for Example 1: V = 3, edges = [(0,1), (0,2), (1,2)], undirected.

Step 1: Create 3 empty lists, one per vertex.

adj[0] = []
adj[1] = []
adj[2] = []

Step 2: Process edge (0,1). Add vertex 1 to adj[0].

adj[0] = [1]
adj[1] = []
adj[2] = []

Step 3: Since the graph is undirected, also add vertex 0 to adj[1].

adj[0] = [1]
adj[1] = [0]
adj[2] = []

Step 4: Process edge (0,2). Add vertex 2 to adj[0].

adj[0] = [1, 2]
adj[1] = [0]
adj[2] = []

Step 5: Mirror: add vertex 0 to adj[2].

adj[0] = [1, 2]
adj[1] = [0]
adj[2] = [0]

Step 6: Process edge (1,2). Add vertex 2 to adj[1].

adj[0] = [1, 2]
adj[1] = [0, 2]
adj[2] = [0]

Step 7: Mirror: add vertex 1 to adj[2].

adj[0] = [1, 2]
adj[1] = [0, 2]
adj[2] = [0, 1]

Step 8: All edges processed. The adjacency list is complete. Each vertex stores exactly the vertices it is connected to — no wasted entries.

1. Read the number of vertices V and edges E.
2. Create an array of V empty lists (in C++: vector<vector<int>> adj(V);).
3. For each edge (u, v) in the input:
   • Add v to adj[u] (vertex u has neighbor v). In C++: adj[u].push_back(v);
   • If undirected, also add u to adj[v]. In C++: adj[v].push_back(u);
   • If directed, only add to adj[u].
   • For weighted edges with weight w, store pairs: adj[u].push_back({v, w});
4. The list is now ready. To find all neighbors of vertex i, iterate over adj[i].
5. To check if edge (u, v) exists, scan adj[u] for value v (takes O(degree(u)) time).

Time Complexity:

• Building the list: O(V + E)

  • Creating V empty lists takes O(V).
  • Processing each of the E edges takes O(1) per edge (appending to a vector/list is amortized O(1)).
  • Total: O(V + E).

• Checking if edge (u, v) exists: O(degree(u)) — must scan vertex u's neighbor list. In the worst case, degree(u) can be V−1, but on average for sparse graphs it is much smaller.

• Finding all neighbors of vertex u: O(degree(u)) — just iterate over adj[u]. This is optimal because you only visit the actual neighbors, not all V vertices.

Space Complexity: O(V + E)

• V lists (one per vertex) contribute O(V).
• For an undirected graph, each edge appears in two lists, contributing 2E total entries → O(E).
• For a directed graph, each edge appears once → O(E).
• Total: O(V + E).

For sparse graphs (E << V²), this is dramatically better than the O(V²) adjacency matrix. For a graph with V = 10,000 and E = 20,000, the adjacency list uses roughly 50,000 entries vs. 100,000,000 cells for the matrix.

Summary of Trade-offs: