Graph representations

Prerequisites

• Arrays, including 2D arrays.
• Linked lists or dynamic arrays.
• The words vertex (node), edge, degree.

The analogy

How it works

Notation: $V$ = number of vertices, $E$ = number of edges. The graph here is undirected: an edge A–B is stored in both directions.

Start with one graph, two layouts, by hand

Vertices A, B, C, D (indices 0–3). Edges: A–B, A–C, B–C, C–D. Predict, then open "Check".

Finish the picture: directed and weighted

Change the graph: make it directed (A → B, A → C, B → C, C → D) and give each edge a weight.

• Directed matrix. Predict: is the matrix still symmetric?
  Check

  No. m[A][B] = 1 but m[B][A] = 0. There are now only 4 ones, one per arrow.

• Weighted edges. Predict how to store a weight of 7 on A → B in each layout.
  Check

  Matrix: put 7 in m[A][B] instead of 1 (0 or ∞ for "no edge"). List: store pairs, A: (B, 7), (C, …).

The rule in plain words

Adjacency matrix: a $V \times V$ array; cell $(u, v)$ holds 1 (or the weight) if there is an edge $u \to v$.

Adjacency list: for each vertex, the list of its neighbours. Use a matrix for dense graphs and constant-time edge checks; use lists for sparse graphs, which is most real ones.

The code

Read this code after you have filled in the matrix by hand. It will make more sense.

void add_edge(int m[][4], int u, int v) {      /* undirected: store both ways */
    m[u][v] = 1;
    m[v][u] = 1;
}

void degrees(int m[][4], int n, int deg[]) {
    for (int u = 0; u < n; u++) {
        deg[u] = 0;
        for (int v = 0; v < n; v++) deg[u] += m[u][v];   /* count the 1s in row u */
    }
}

graph LR
  A((A)) --- B((B))
  A --- C((C))
  B --- C
  C --- D((D))
          

How fast is it?

An undirected simple graph has at most one edge per pair of vertices, and the sum of degrees counts every edge twice:

A graph with $E$ close to $V^2$ is dense; with $E$ close to $V$ it is sparse.

Common mistakes

• Storing only one direction of an undirected edge.
• Choosing a matrix for a huge sparse graph and running out of memory.
• Using 0 for "no edge" in a weighted graph where 0 can also be a real weight.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• A matrix answers edge queries in $O(1)$ because the answer is one cell m[u][v].
• A matrix needs $O(V^2)$ memory because it stores every pair, edge or not.
• Lists need $O(V + E)$ memory because they store only real edges.
• Traversals cost $O(V + E)$ on lists because each list is scanned once and their lengths sum to $2E$.
• Undirected edges appear twice because each endpoint is a neighbour of the other.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How are an adjacency matrix and adjacency lists like a tick grid versus friend lists?
   Sample answer

   The grid has a cell for every pair and ticks the friends, mostly empty; the lists only record actual friendships.

2. Encode A–B, A–C, B–C, C–D: give row A of the matrix and C's list.
   Sample answer

   Row A is 0 1 1 0. C's list is A, B, D.

3. Why does add_edge write both m[u][v] and m[v][u]?

   A good answer mentions undirected edges.

   Sample answer

   The graph is undirected, so v is u's neighbour and u is v's neighbour; the matrix must be symmetric.

4. So what are the two standard graph representations, in one sentence each?
   Sample answer

   An adjacency matrix is a $V \times V$ grid marking each edge; an adjacency list stores, for each vertex, the list of its neighbours.

5. Why is BFS $O(V^2)$ on a matrix but $O(V + E)$ on lists?

   A good answer looks at how neighbours are found.

   Sample answer

   On a matrix, finding neighbours scans a whole row of $V$ cells for every vertex. On lists you only scan real neighbours, and all lists together have $2E$ entries.

6. Compare memory, edge check and neighbour listing for both.
   Sample answer

   Matrix: $O(V^2)$, $O(1)$, $O(V)$. List: $O(V + E)$, $O(\deg u)$, $O(\deg u)$.

7. When would you still choose a matrix?
   Sample answer

   For small or dense graphs, or when the algorithm checks "is u–v an edge?" constantly, as Floyd-Warshall does.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out directed/weighted variants and the degree-sum formula. I'd keep the grid-versus-friend-list analogy, the 4-vertex example, and "dense → matrix, sparse → list".

External resources

• VisuAlgo: Graph data structures: draw a graph and see its matrix, list and edge list side by side.
• GeeksforGeeks: Graph representations: matrix and list with code.
• Wikipedia: Adjacency list: trade-offs against the matrix.
• MIT OCW 6.006: lecture on graph representations and BFS.

Videos

• YouTube search: adjacency matrix vs list: a short comparison.