Graph — Adjacency Matrix vs. Adjacency List

After this topic

You will understand what a graph is and the difference between the two ways of representing it: adjacency matrix and adjacency list.

Trees are a special case of graphs

Arrays, linked lists, trees — the data structures we've seen so far have simple relationships between data. Arrays have order, trees have hierarchy.

But real-world relationships are complex. People on social media follow each other. Cities are connected by roads. Web pages are linked together. A data structure that represents these many-to-many relationships is a graph.

A graph consists of nodes (or vertices) and edges that connect nodes. A tree is also a type of graph, but it is a special graph with the constraints of a "parent-child" relationship and "no cycles."

Undirected Graph vs. Directed Graph

Undirected Graph: If A and B are connected, you can go from A to B and from B to A. Like a Facebook friend relationship — if I'm friends with someone, they're also friends with me.

Directed Graph: You can only go from A to B, but not from B to A. Like following someone on Instagram — just because I follow someone doesn't mean they follow me back.

Adjacency Matrix: A 2D Array

Represent a graph with 5 nodes using a 5x5 matrix. If matrix[i][j] = 1, it means there is an edge from node i to node j.

A  B  C  D
A [ 0, 1, 1, 0 ]
B [ 1, 0, 0, 1 ]
C [ 1, 0, 0, 1 ]
D [ 0, 1, 1, 0 ]

This is an undirected graph with A-B, A-C, B-D, and C-D connected. Because it's undirected, the matrix is symmetric about the diagonal.

graph = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]

# Check if A and B are connected
if graph[0][1] == 1:
    print("A-B connected")  # O(1)

Advantage: Checking if two nodes are connected is O(1). Access it directly using the index.

Disadvantage: If there are N nodes, you need an N×N array. If there are 10,000 nodes, you need 100 million cells. Even if there are few edges, you still use all that space.

Adjacency List: A Linked List

For each node, store a "list of nodes connected to this node."

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]

This is the same graph, but represented in a different way.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}

# Iterate over A's neighbor nodes
for neighbor in graph['A']:
    print(neighbor)  # B, C

Advantage: Uses memory proportional to the number of edges. Even if there are 10,000 nodes, if there are only 100 edges, you only need space for 100.

Disadvantage: To check if two nodes are connected, you need to iterate over the list. In the worst case, it's O(N).

Which one should I use?

| Adjacency Matrix      | Adjacency List
---------+------------------+------------------
Space     | O(V^2)           | O(V + E)
Check Connection | O(1)             | O(degree)
Iterate Neighbors | O(V)             | O(degree)
Suitable Cases | Dense graph with many edges | Sparse graph with few edges

Dense Graph: Has many edges relative to the number of nodes. A network of airlines where there is a direct route between every city. The adjacency matrix is suitable.

Sparse Graph: Has few edges relative to the number of nodes. On a social network of 100 million users, each user follows an average of 200 people. The adjacency list is suitable.

Most real-world graphs are sparse graphs. Therefore, the adjacency list is the default choice. You can also think of the adjacency list first in coding tests.

Weighted Graph

Edges can have weights. This could be the distance between cities, network latency, etc.

In the adjacency matrix, instead of 1, put the weight value:

# matrix[A][B] = distance
matrix = [
    [0, 5, 3, 0],
    [5, 0, 0, 2],
    ...
]

In the adjacency list, represent it as a tuple:

graph = {
    'A': [('B', 5), ('C', 3)],
    'B': [('A', 5), ('D', 2)],
    ...
}

To find the shortest path in a weighted graph, use the Dijkstra algorithm instead of BFS. BFS is the shortest path based on the number of edges, while Dijkstra is the shortest path based on the sum of weights.

Key Takeaways

A graph is a data structure that represents many-to-many relationships with nodes and edges. The adjacency matrix has O(1) connection check but uses O(V^2) space. The adjacency list uses only O(V+E) space, and is the default choice for most real-world graphs.