Graphs

A graph is a data structure consisting of a set of vertices (nodes) connected by edges (arcs). Graphs model relationships between entities: road networks, social networks, circuit diagrams, dependency trees, and more.

Key terminology:

Term	Meaning
Vertex (node)	An entity in the graph
Edge (arc)	A connection between two vertices
Directed graph (digraph)	Edges have a direction (one-way)
Undirected graph	Edges have no direction (two-way)
Weighted graph	Edges carry a numeric value (cost, distance, time)
Unweighted graph	All edges treated as equal

Example — undirected weighted graph (road network):

     A ---4--- B
     |         |
     2         3
     |         |
     C ---1--- D
      \       /
        --5--

Vertices: A, B, C, D. Edge A–B has weight 4; edge C–D has weight 1.

Undirected graph — edges are bidirectional; if A connects to B then B connects to A.

Directed graph (digraph) — edges are one-way; A → B does not imply B → A.

Undirected:         Directed:
A --- B             A --→ B
|   /               ↑   /
C                   C

Applications:

• Undirected: friendship networks (mutual), road maps (two-way streets)
• Directed: Twitter follows (one-way), web page links, task dependencies

(Extra context — not required by AQA 4.2.4) A graph with no cycles is a directed acyclic graph (DAG), used in build systems, spreadsheet dependencies, and scheduling.

An adjacency matrix represents a graph as a 2D array where matrix[i][j] indicates whether there is an edge from vertex $i$ to vertex $j$.

• Unweighted: 1 if an edge exists, 0 if not
• Weighted: the edge weight if an edge exists, 0 (or ∞) if not

Example — the road network from slide 1:

Vertices: A=1, B=2, C=3, D=4

     A  B  C  D
A  [ 0  4  2  0 ]
B  [ 4  0  0  3 ]
C  [ 2  0  0  1 ]
D  [ 0  3  1  0 ]  (weight 5 edge C–D already shown as C→D=1, but let's use the simpler example)

Note: for undirected graphs the matrix is symmetric (value at [i][j] equals value at [j][i]).

Space complexity: $O(V^2)$ — always allocates a $V\times V$ array regardless of edge count.

An adjacency list stores a list of neighbours for each vertex. Each vertex maps to the list of vertices it connects to (and optionally the edge weights).

Example — same graph:

A: [(B, 4), (C, 2)]
B: [(A, 4), (D, 3)]
C: [(A, 2), (D, 1)]
D: [(B, 3), (C, 1)]

Space complexity: $O(V+E)$ — uses space proportional to the number of vertices plus the number of edges.

Comparison:

	Adjacency matrix	Adjacency list
Space	$O(V^2)$	$O(V+E)$
Check if edge exists	$O(1)$	$O(\text{degree})$
List all neighbours	$O(V)$	$O(\text{degree})$
Best for	Dense graphs (many edges)	Sparse graphs (few edges)

A dense graph has close to $V^2$ edges; a sparse graph has far fewer. Most real-world networks (road maps, social networks) are sparse — adjacency lists are usually more efficient.

The choice of representation depends on the graph's characteristics and the operations required:

Use an adjacency matrix when:

• The graph is dense (many edges)
• Frequent edge-existence checks are needed
• Memory is not a constraint

Use an adjacency list when:

• The graph is sparse (few edges, as in most real applications)
• Memory efficiency matters
• Operations mainly iterate over neighbours (as in BFS and DFS)

Worked example — representing a social network of 1 million users:

• Matrix would require $10^{12}$ cells — impractical
• Each user has on average 200 friends → total edges ≈ $10^8$
• Adjacency list uses space proportional to $10^6+10^8$ — manageable

1. Forgetting that undirected adjacency matrices are symmetric

In an undirected graph, if matrix[A][B] = 4 then matrix[B][A] must also be 4. Missing the symmetric entry loses marks in matrix construction questions.

2. Confusing vertices and edges in Big-O analysis

$O(V^2)$ refers to vertices squared; $O(V+E)$ refers to vertices plus edges. Substituting one for the other produces wrong complexity claims.

3. Using an adjacency matrix for a sparse graph

A social network or the Internet is sparse. Claiming a matrix is the better choice is incorrect without justifying that the graph is dense.

4. Stating that a tree is not a graph

A tree is a special case of a graph: connected, undirected, and with no cycles. All the graph representations apply to trees.