# 7.2 Adjacency Matrix & Adjacency List

> Two ways to store a graph in memory, what each costs, and when to choose which.

Chapter: Graphs · ~45 min · medium
URL: https://dsa.fetehadin.com/learn/graph-representation

## Mental model

Two ways to write down who knows whom in a class.

**A big table** (adjacency matrix): rows and columns are students, and you put a 1 where two students know each other. Checking any pair is instant, but a class of 1,000 needs a million cells, mostly zeros.

**A contact list per student** (adjacency list): each student keeps a list of only the people they know. It is compact, and listing a student's friends is fast. But checking "does A know B?" means scanning A's list.

### Adjacency matrix

```cpp
int m[V][V] = {};
m[u][v] = m[v][u] = 1;   // undirected edge u–v
```

- Space **O(V²)**, whatever the number of edges.
- Edge check **O(1)**.
- Symmetric for undirected graphs. For weighted graphs, store the weight instead of 1.

### Adjacency list

```cpp
vector<vector<int>> adj(V);
adj[u].push_back(v);
adj[v].push_back(u);     // undirected: both ends
```

- Space **O(V + E)**.
- Looping over neighbours costs only **deg(u)**.

### Which one?

- **Sparse** graphs (most real ones): **list**.
- **Dense** graphs, or when you need many fast "is there an edge?" checks: **matrix**.

## C++ code: graph-rep.cpp

```cpp
#include <iostream>
#include <vector>
using namespace std;

const int V = 6;

int main() {
    int edges[][2] = {{0, 1}, {0, 3}, {1, 2}, {1, 4}, {3, 4}, {2, 5}, {4, 5}};

    int matrix[V][V] = {};                    // O(V²) space
    vector<vector<int>> list(V);              // O(V + E) space
    for (auto& e : edges) {
        int u = e[0], v = e[1];
        matrix[u][v] = matrix[v][u] = 1;      // undirected: both directions
        list[u].push_back(v);
        list[v].push_back(u);
    }

    cout << "Adjacency matrix:\n   ";
    for (int j = 0; j < V; j++) cout << j << " ";
    cout << "\n";
    for (int i = 0; i < V; i++) {
        cout << i << ": ";
        for (int j = 0; j < V; j++) cout << matrix[i][j] << " ";
        cout << "\n";
    }

    cout << "Adjacency list:\n";
    for (int i = 0; i < V; i++) {
        cout << i << " ->";
        for (int v : list[i]) cout << " " << v;
        cout << "   (degree " << list[i].size() << ")\n";
    }

    cout << "edge 1-4? " << (matrix[1][4] ? "yes" : "no") << ", edge 0-5? " << (matrix[0][5] ? "yes" : "no") << "\n";
}
```

Expected output:

```text
Adjacency matrix:
   0 1 2 3 4 5 
0: 0 1 0 1 0 0 
1: 1 0 1 0 1 0 
2: 0 1 0 0 0 1 
3: 1 0 0 0 1 0 
4: 0 1 0 1 0 1 
5: 0 0 1 0 1 0 
Adjacency list:
0 -> 1 3   (degree 2)
1 -> 0 2 4   (degree 3)
2 -> 1 5   (degree 2)
3 -> 0 4   (degree 2)
4 -> 1 3 5   (degree 3)
5 -> 2 4   (degree 2)
edge 1-4? yes, edge 0-5? no
```

## Complexity

| Case | Cost |
| --- | --- |
| space | matrix O(V²) · list O(V + E) |
| is there an edge u–v? | matrix O(1) · list O(deg u) |
| visit all neighbours of u | matrix O(V) · list O(deg u) |
| add an edge | matrix O(1) · list O(1) |


For BFS/DFS the list gives **O(V + E)** and the matrix gives **O(V²)**.

## Videos

- [Graph Representation: Adjacency Matrix](https://youtu.be/9C2cpQZVRBA) (mycodeschool): The adjacency matrix, its cost, and when it wastes space.
- [Graph Representation: Adjacency List](https://youtu.be/k1wraWzqtvQ) (mycodeschool): The adjacency list and a clear side-by-side cost comparison.

## Exam lens

Likely questions:

- Draw the adjacency matrix and adjacency list of a given graph.
- Compare the space and time costs of the two representations.
- Which representation suits a sparse graph? A dense one? Why?
- How do you store a weighted graph in each representation?

Common mistakes:

- Setting only `m[u][v]` for an undirected edge. Set `m[v][u]` too.
- Saying the list is always better. Edge lookup is O(1) only in the matrix.
- Forgetting that an undirected edge appears **twice** in the list.

## Quick check

1. An undirected graph has V = 1000, E = 3000. Which representation uses less memory?
   A. matrix
   B. list
   C. same
   D. depends on the weights
   Answer: B. Matrix = 1,000,000 cells. List ≈ V + 2E = 7,000 entries.

2. The adjacency matrix of an undirected graph is always…
   A. diagonal
   B. symmetric
   C. all ones
   D. upper triangular
   Answer: B. m[u][v] = m[v][u] for every edge.

3. Checking "is there an edge between u and v?" is O(1) in…
   A. the matrix
   B. the list
   C. both
   D. neither
   Answer: A. The list must scan u's neighbours.

4. How many entries does the adjacency list of an undirected graph hold in total?
   A. E
   B. 2E
   C. V
   D. V²
   Answer: B. Each edge is stored once at each end.

## Practice

**Trace by hand.** Vertices 0–3, undirected edges 0–1, 0–2, 1–2, 2–3. Write the adjacency matrix and adjacency list.

Solution:

```text
   0 1 2 3
0: 0 1 1 0
1: 1 0 1 0
2: 1 1 0 1
3: 0 0 1 0
```
List: `0 → 1 2` · `1 → 0 2` · `2 → 0 1 3` · `3 → 2`


**Implement it.** Store a **weighted** undirected graph both ways. Use `vector<vector<pair<int,int>>>` for the list (neighbour, weight) and 0 for "no edge" in the matrix.

Hint: `adj[u].push_back({v, w}); adj[v].push_back({u, w}); m[u][v] = m[v][u] = w;`

**Problems:**

- [Find if Path Exists in Graph](https://leetcode.com/problems/find-if-path-exists-in-graph/) (easy). Hint: Build an adjacency list from the edge array, then BFS or DFS from source.
- [Find Center of Star Graph](https://leetcode.com/problems/find-center-of-star-graph/) (easy). Hint: Count degrees with a list. The center has degree n − 1.

## Mastery checklist

- [ ] I can draw both representations of a graph.
- [ ] I can state the space and time costs of each.
- [ ] I can choose the right one for a sparse or dense graph.
- [ ] I can build an adjacency list in C++ with vector<vector<int>>.