Graphs: types and representations

Vocabulary and types

A graph is a set of vertices (nodes) joined by edges (arcs).

• Undirected: edges work both ways (a two-way road, a friendship).
• Directed (digraph): each edge has a direction (a one-way street, 'follows' on social media, a web link).
• Weighted: each edge has a value such as distance, time or cost.

Two vertices joined by an edge are adjacent (neighbours). A graph differs from a tree because it can contain cycles and need not have a root.

Adjacency matrix

A 2D array where row i, column j holds 1 (or the weight) if there is an edge from i to j, and 0 (or blank / infinity) if not. For an undirected graph the matrix is symmetric about the leading diagonal.

Undirected graph: A-B, A-C, B-D, B-E, C-F, E-F

Adjacency list

Each vertex stores a list of its neighbours (with weights if needed), for example a dictionary of lists:

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}

Weighted: {"A": {"B": 4, "C": 2}, ...}

Choosing a representation

Which one to use depends on how many edges the graph has and what you need to do with it.

Worked example

Add a directed edge from D to F with weight 7 to both representations of a weighted directed graph.

1. Matrix: set the cell in row D, column F to 7. Column D, row F stays as it is, because the edge is one-way.
2. List: add F: 7 to D's list, so D: {..., F: 7}.

Answer: One cell in the matrix; one entry in D's list.

Check yourself

1. Which situation is best modelled by a directed graph?
   • Two-way roads between towns
   • Cables connecting computers in a LAN
   • Friendships, which are always mutual
   • Users following other users on a social network, where following need not be mutual
   Show answer

   Users following other users on a social network, where following need not be mutual. Direction matters when a relationship is one-way.

2. Why is the adjacency matrix of an undirected graph symmetric?
   • All weights are equal
   • Every edge between X and Y appears in row X column Y and in row Y column X
   • It has no edges
   • It contains cycles
   Show answer

   Every edge between X and Y appears in row X column Y and in row Y column X. Undirected edges go both ways.

3. In the undirected graph with edges A-B, A-C, B-D, B-E, C-F, E-F, how many neighbours does B have?
   Show answer

   3. B connects to A, D and E.

4. How many cells does the adjacency matrix of a graph with 9 vertices have?
   Show answer

   81. 9 x 9 = 81, whatever the number of edges.

5. What is an advantage of an adjacency matrix over an adjacency list?
   • It always uses less memory
   • Listing a vertex's neighbours is faster
   • Checking whether two vertices are connected takes constant time
   • It cannot store weights
   Show answer

   Checking whether two vertices are connected takes constant time. One array lookup answers the question.

6. A road network has 10 000 junctions, each joined to about 4 others. Which representation is better and why?
   • Adjacency list, because the graph is sparse and a matrix would hold 100 million mostly-empty cells
   • Adjacency matrix, because it is always faster
   • Adjacency matrix, because lists cannot store weights
   • Adjacency list, because matrices cannot be used for undirected graphs
   Show answer

   Adjacency list, because the graph is sparse and a matrix would hold 100 million mostly-empty cells. 10 000 x 10 000 = 10⁸ cells for about 20 000 edges.

7. In a weighted adjacency matrix, what does the value in row P, column Q show?
   • The number of vertices
   • The distance from P to every vertex
   • The weight of the edge from P to Q
   • Whether P is the start vertex
   Show answer

   The weight of the edge from P to Q. Cells store the weight, or a marker for no edge.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Subsidiary and Advanced Level in Computer Science specification (2026), Issue 1
• Pearson Edexcel IAL Computer Science sample assessment materials (Unit 3 paper, resource booklet and mark scheme)

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