Graph Representation

Table of Contents +

So you know what a graph is. It is a bunch of vertices joined by edges. But here is the real question. How do you keep a graph inside a program? A computer does not understand a drawing on paper. It only understands arrays and lists. So we need a way to write the graph down in code.

There are two common ways to do this. One is the adjacency matrix, which is a 2D grid. The other is the adjacency list, which is a list of neighbors for each vertex. Both store the same graph. They just store it in a different shape. Let us walk through both. We will build the same small graph in code. Then we will compare them.

🗺️ The Small Graph We Will Build

Let us pick one tiny graph and use it the whole time. That way you can see both methods describe the exact same thing.

We have 4 vertices, numbered 0, 1, 2, 3. The edges are:

  • 0 connected to 1
  • 0 connected to 2
  • 1 connected to 2
  • 2 connected to 3

It is an undirected graph. So if 0 is connected to 1, then 1 is also connected to 0. The connection goes both ways.

0

1

2

3

Now let us store this graph in two different ways.

🟦 Way 1: Adjacency Matrix

Think of a school attendance sheet. Names go down the side. The same names go across the top. You put a tick in a cell when two people are friends. That is exactly an adjacency matrix.

An adjacency matrix is a 2D grid of size V by V. Here V is the number of vertices. The cell at row i and column j is 1 when there is an edge between vertex i and vertex j. Otherwise it is 0.

For our graph, the grid looks like this:

0 1 2 3
0 0 1 1 0
1 1 0 1 0
2 1 1 0 1
3 0 0 1 0

See how the grid is a mirror across the diagonal? Row 0 column 1 is 1. And row 1 column 0 is also 1. That is because the graph is undirected. The edge counts both ways.

Here are the steps to build it:

  1. Make a V by V grid and fill every cell with 0.
  2. For each edge between u and v, set cell [u][v] to 1.
  3. The graph is undirected, so also set cell [v][u] to 1.
  4. To print the neighbors of a vertex i, walk across its row. Pick every column j where the cell is 1.
adjacency_matrix.py
V = 4


# Set the edge both ways because the graph is undirected
def add_edge(matrix, u, w):
    matrix[u][w] = 1
    matrix[w][u] = 1


# Walk across row i and print every column that is 1
def print_neighbors(matrix, i):
    neighbors = [j for j in range(V) if matrix[i][j] == 1]
    print(f"Neighbors of {i}: {' '.join(map(str, neighbors))}")


# Start with a V by V grid of all zeros
matrix = [[0] * V for _ in range(V)]


add_edge(matrix, 0, 1)
add_edge(matrix, 0, 2)
add_edge(matrix, 1, 2)
add_edge(matrix, 2, 3)


for i in range(V):
    print_neighbors(matrix, i)

The output of the above code will be:

Neighbors of 0: 1 2
Neighbors of 1: 0 2
Neighbors of 2: 0 1 3
Neighbors of 3: 2

Note

Checking if an edge exists between i and j is just reading cell [i][j]. That is one step, so it is O(1). But the grid always holds V times V cells, even when most are 0. So the space is O(V^2) no matter how few edges you have.

🟩 Way 2: Adjacency List

Now think about your phone contacts. You do not store one giant grid of every person against every other person. You just keep, for each person, a short list of who they talk to. That is an adjacency list.

An adjacency list keeps, for each vertex, a list of the vertices it is directly connected to. No big grid. Just small lists. When a vertex has few neighbors, its list stays short. So you only spend space on edges that really exist.

For our graph, the lists look like this:

  • 0 has [1, 2]
  • 1 has [0, 2]
  • 2 has [0, 1, 3]
  • 3 has [2]

Here are the steps to build it:

  1. Make an array of V empty lists, one for each vertex.
  2. For each edge between u and v, add v to the list of u.
  3. The graph is undirected, so also add u to the list of v.
  4. To print the neighbors of a vertex i, just print its list. No scanning needed.
adjacency_list.py
V = 4


# Add the edge both ways because the graph is undirected
def add_edge(adj, u, w):
    adj[u].append(w)
    adj[w].append(u)


# Print every vertex stored in i's list
def print_neighbors(adj, i):
    print(f"Neighbors of {i}: {' '.join(map(str, adj[i]))}")


# Start with V empty lists, one per vertex
adj = [[] for _ in range(V)]


add_edge(adj, 0, 1)
add_edge(adj, 0, 2)
add_edge(adj, 1, 2)
add_edge(adj, 2, 3)


for i in range(V):
    print_neighbors(adj, i)

The output of the above code will be:

Neighbors of 0: 1 2
Neighbors of 1: 0 2
Neighbors of 2: 0 1 3
Neighbors of 3: 2

Note

Notice the C output prints neighbors in reverse order, like Neighbors of 0: 2 1. That is because the C version adds each new neighbor to the front of a linked list. The neighbors are the same. Only the order they come out differs. The order inside a neighbor list does not change the graph.

⚖️ Matrix or List: Which One?

So which one should you use? It depends on how full the graph is.

A graph is sparse when it has far fewer edges than the most it could have. Most real graphs are sparse. Think of a road map. A city is not directly connected to every other city. So an adjacency list usually wins. It only spends space on the edges that are really there.

Here is the side by side comparison. V is the number of vertices. E is the number of edges.

What you compare Adjacency Matrix Adjacency List
Space used O(V^2) O(V + E)
Check if edge i to j exists O(1) O(degree of i)
Visit all neighbors of i O(V) O(degree of i)
Add an edge O(1) O(1)
Best for Dense graphs, fast edge checks Sparse graphs, saving space

Tip

Here is a quick rule of thumb. Do you mostly ask “is there an edge between these two?” and the graph is small or dense? Pick the matrix. Do you mostly ask “who are my neighbors?” and the graph is large or sparse? Pick the list. Most graph problems use the list.

A few mistakes students make a lot:

  • Forgetting to add the edge both ways in an undirected graph. If you only set [u][v] and skip [v][u], half your edges go missing.
  • Using a matrix for a huge graph with few edges. A graph with a million vertices needs a matrix of a million times a million cells. That will not fit in memory.
  • Thinking the order inside a neighbor list matters. It does not. [1, 2] and [2, 1] describe the same connections.

🧩 What You’ve Learned

  • ✅ A graph can be stored as an adjacency matrix, a V by V grid where cell [i][j] is 1 when an edge exists.
  • ✅ A graph can also be stored as an adjacency list, where each vertex keeps a small list of its neighbors.
  • ✅ The matrix gives O(1) edge lookup but always uses O(V^2) space, even for few edges.
  • ✅ The list uses only O(V + E) space, so it is the better choice for sparse graphs.
  • ✅ In an undirected graph you must add every edge both ways.
  • ✅ The order of neighbors inside a list does not change the graph.

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    In an adjacency matrix, what does the cell at row i and column j equal to 1 mean?

    Why: A value of 1 at [i][j] means an edge connects vertex i and vertex j.

  2. 2

    How much space does an adjacency matrix use for a graph with V vertices?

    Why: A matrix is always a V by V grid, so it uses O(V^2) space no matter how few edges exist.

  3. 3

    For a large graph with very few edges (a sparse graph), which representation is usually better?

    Why: An adjacency list uses O(V + E) space, so it saves a lot of memory when edges are few.

  4. 4

    Why do we add an edge both ways (u to w and w to u) for our graph?

    Why: In an undirected graph the edge has no direction, so both vertices must list each other.

Score: 0 / 4

🚀 What’s Next?

Previous Graph Terminology Next Breadth-First Search (BFS)

Share & Connect

Share on LinkedIn