Adjacency matrix and adjacency list

Two ways to store a graph, and choosing between them for dense and sparse graphs.

A4.2Trees and graphsA level25 min

A list of edges stores a graph, but every question you ask it means searching all the edges. Programs store graphs in one of two standard ways instead: an adjacency matrix or an adjacency list. Knowing both, and being able to justify choosing one, is a favourite exam question.

The adjacency matrix

An adjacency matrix is a two-dimensional array with one row and one column for each vertex. The cell in row u, column v records the edge from u to v. At GCSE you used two-dimensional arrays for grids of readings; here the grid records who is joined to whom.

In an unweighted graph each cell holds 1 for an edge and 0 for none. In a weighted graph it holds the weight. This is the warehouse graph from the last lesson:

Three things to notice:

• The graph is undirected, so the matrix is symmetric about the leading diagonal (top left to bottom right): row B, column E holds the same 2 as row E, column B. A directed graph's matrix is usually not symmetric.
• The leading diagonal is all 0, because no vertex has an edge to itself.
• Here 0 means "no edge". If 0 could be a real weight, use a value that cannot be one, such as infinity (∞) or None. Exam questions often write ∞ or leave the cell blank.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

VERTICES = ["A", "B", "C", "D", "E", "F"]
EDGES = [("A", "B", 5), ("A", "D", 3), ("B", "C", 4), ("B", "D", 6),
         ("B", "E", 2), ("C", "F", 7), ("D", "E", 8), ("E", "F", 1)]

n = len(VERTICES)
matrix = [[0] * n for i in range(n)]     # n rows, each its own list of n zeros
for u, v, w in EDGES:
    i = VERTICES.index(u)
    j = VERTICES.index(v)
    matrix[i][j] = w
    matrix[j][i] = w                     # undirected: the edge goes both ways

for i in range(n):
    print(VERTICES[i], matrix[i])

print("B to E:", matrix[1][4])           # one look answers "is there an edge?"
print("C to D:", matrix[2][3])

Run this in the simulator

[[0] * n for i in range(n)] makes n separate rows. The shortcut [[0] * n] * n does not: it puts the same row in the list n times, so setting one cell would change that column in every row.

The adjacency list

An adjacency list stores, for each vertex, a list of only the vertices it is joined to. In Python a dictionary of lists does this naturally; in a language without dictionaries it is an array of linked lists. For a weighted graph each entry holds the neighbour and the weight.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

GRAPH = {
    "A": [("B", 5), ("D", 3)],
    "B": [("A", 5), ("C", 4), ("D", 6), ("E", 2)],
    "C": [("B", 4), ("F", 7)],
    "D": [("A", 3), ("B", 6), ("E", 8)],
    "E": [("B", 2), ("D", 8), ("F", 1)],
    "F": [("C", 7), ("E", 1)],
}

for neighbour, w in GRAPH["B"]:
    print("B to", neighbour, "takes", w, "s")

# is there an edge from B to E? search B's list
found = False
for neighbour, w in GRAPH["B"]:
    if neighbour == "E":
        found = True
print("B to E:", found)

entries = 0
for v in GRAPH:
    entries = entries + len(GRAPH[v])
print("entries:", entries)

Run this in the simulator

The list has 16 entries for 8 edges, because an undirected edge appears in the lists of both of its ends: the handshake lemma again. A directed edge appears once, in the list of the vertex it leaves.

Which to use

Write V for the number of vertices and E for the number of edges.

A worked example. Divide a large mat into a 10 by 10 grid of zones, with an edge between zones side by side. That is 100 vertices, so a matrix has 100 × 100 = 10,000 cells. But each zone has at most 4 neighbours: the grid has 90 edges across and 90 up and down, 180 in total, so the adjacency list holds only 360 entries. Nearly every cell of the matrix would be 0. The graph is sparse, and the list is the right choice.

Now take direct flights between 20 airports where almost every pair is connected. The matrix has 400 cells and nearly all of them are used, so it wastes little memory, and it answers "is there a direct flight from X to Y?" in one look. That graph is dense, and the matrix is a sound choice.

The traversals in the next two lessons spend their time going from each vertex to its neighbours, which is exactly what the list is good at.

Task: matrix and list

The graph in EDGES is directed and weighted, as drawn below: ("A", "B", 4) is an edge from A to B of weight 4, and there is no edge from B to A unless one is listed. VERTICES gives the order of the matrix's rows and columns. Build an adjacency matrix called matrix, a list of lists with matrix[i][j] holding the weight of the edge from VERTICES[i] to VERTICES[j] and 0 where there is no edge, and print it one row per line: the vertex, a colon, then the row's values separated by single spaces, such as A: 0 4 0 7. Then build an adjacency list as a dictionary, with each vertex's neighbours in the order their edges appear in EDGES, and print it one vertex per line in VERTICES order, in the form A -> B(4) D(7). Build both from EDGES: do not type the rows.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

VERTICES = ["A", "B", "C", "D"]
EDGES = [("A", "B", 4), ("A", "D", 7), ("B", "C", 3), ("C", "A", 2), ("D", "C", 5), ("B", "D", 1)]

n = len(VERTICES)

Challenges

1. Print the matrix with every arrow reversed. What does row A tell you now?
2. Write in_degree(v) using the matrix and out_degree(v) using the list. Which representation makes each one easier, and why?
3. A graph has 1,000 vertices and each has about 5 neighbours. How many cells does its adjacency matrix have? About how many entries does its adjacency list hold if the edges are directed?