Representing graphs: adjacency matrix and adjacency list

Graph vocabulary

• Undirected: edges work both ways (a road). Directed: edges have a direction (a one-way street, 'follows').
• Weighted: each edge has a value such as a distance or cost.
• Neighbours (adjacent vertices) are those joined directly by an edge; the degree of a vertex is its number of edges.

Adjacency matrix

A 2D list where matrix[i][j] holds the weight of the edge from vertex i to vertex j (0, or another agreed value, for no edge). For an undirected graph the matrix is symmetric about the leading diagonal. Checking whether an edge exists is instant, but the matrix needs n² cells even when there are few edges.

Adjacency list

Each vertex stores only its neighbours. In Python, a dictionary of lists (unweighted) or a dictionary of dictionaries (weighted): adj["A"] = {"B": 4, "C": 1}. It uses memory in proportion to the number of edges and makes looping over neighbours fast; checking one particular edge means looking in a vertex's collection.

names = ["A", "B", "C", "D"]
matrix = [[0, 4, 1, 0],
          [4, 0, 2, 5],
          [1, 2, 0, 0],
          [0, 5, 0, 0]]
adj = {}
for i, a in enumerate(names):
    adj[a] = {}
    for j, b in enumerate(names):
        if matrix[i][j] != 0:
            adj[a][b] = matrix[i][j]
print(adj)
print("B neighbours:", list(adj["B"]), "degree:", len(adj["B"]))
print("edge C-D?", matrix[2][3] != 0, "D" in adj["C"])

Output:

{'A': {'B': 4, 'C': 1}, 'B': {'A': 4, 'C': 2, 'D': 5}, 'C': {'A': 1, 'B': 2}, 'D': {'B': 5}}
B neighbours: ['A', 'C', 'D'] degree: 3
edge C-D? False False

Directed graphs and choosing

In a directed adjacency list, an edge appears only in its starting vertex's list.

follows = {"Ann": ["Bo", "Cy"], "Bo": ["Cy"], "Cy": [], "Dee": ["Ann"]}
followers = {p: [q for q in follows if p in follows[q]] for p in follows}
print(followers)
edges = sum(len(v) for v in follows.values())
print("edges:", edges)

Output:

{'Ann': ['Dee'], 'Bo': ['Ann'], 'Cy': ['Ann', 'Bo'], 'Dee': []}
edges: 4

Worked example

Convert the adjacency list {'P': {'Q': 3}, 'Q': {'P': 3, 'R': 6}, 'R': {'Q': 6}} into an adjacency matrix with vertices in the order P, Q, R.

1. ```python adj = {"P": {"Q": 3}, "Q": {"P": 3, "R": 6}, "R": {"Q": 6}} order = list(adj) matrix = [[adj[a].get(b, 0) for b in order] for a in order] for row in matrix: print(row) ```
2. Output: ``` [0, 3, 0] [3, 0, 6] [0, 6, 0] ```

Answer: Row a, column b holds the weight from a to b, or 0 when there is no edge. The result is symmetric because the graph is undirected.

Check yourself

1. What does this program print? ```python adj = {"A": {"B": 2, "D": 7}, "B": {"A": 2}, "D": {"A": 7}} print(sorted(adj["A"]), adj["D"]["A"]) ```
   Show answer

   ['B', 'D'] 7. A's neighbours are B and D; the edge D to A has weight 7. Output: `['B', 'D'] 7`

2. What does this program print? ```python m = [[0, 1, 1, 1], [1, 0, 0, 1], [1, 0, 0, 0], [1, 1, 0, 0]] print(sum(m[0])) ```
   Show answer

   3. Row 0 has three 1s, so vertex 0 has degree `3`.

3. What does this program print? ```python m = [[0, 1, 1, 1], [1, 0, 0, 1], [1, 0, 0, 0], [1, 1, 0, 0]] print(sum(map(sum, m)) // 2) ```
   Show answer

   4. The matrix has 8 ones, but each undirected edge appears twice (i to j and j to i), so there are `4` edges.

4. How many cells does an adjacency matrix for a graph with 50 vertices contain?
   Show answer

   2500. An n by n matrix has n² = 2500 cells, whatever the number of edges.

5. An adjacency matrix is NOT symmetric about its leading diagonal. What does this tell you?
   • The graph is unweighted
   • The graph has no edges
   • The graph is stored incorrectly
   • The graph is directed
   Show answer

   The graph is directed. In an undirected graph matrix[i][j] always equals matrix[j][i]; a directed graph may have an edge one way only.

6. A road network has 10 000 junctions, and each junction connects to about 4 roads. Which representation is better, and why?
   • An adjacency matrix, because it is always faster
   • An adjacency list, because the graph is sparse and a matrix would need 100 million cells
   • An adjacency matrix, because the graph is dense
   • A single list of junction names
   Show answer

   An adjacency list, because the graph is sparse and a matrix would need 100 million cells. About 40 000 edge entries against 10 000² = 100 000 000 cells.

7. What does this program print? ```python follows = {"A": ["B"], "B": ["C", "A"], "C": []} print("C" in follows["B"], "B" in follows["C"]) ```
   Show answer

   True False. The list is directed: B to C exists, but C has no outgoing edges. Output: `True False`

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary/Advanced Level in Computer Science specification, Issue 1 (March 2026)
• Pearson Edexcel IAL Computer Science Unit 4 Programming Language Subset (PLS)
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 and Unit 4)

Last updated 8 November 2026. Spotted a mistake? Tell us.