Define a graph using vertices (nodes) and edges (arcs)
Distinguish between directed and undirected, weighted and unweighted graphs
Represent graphs using adjacency matrices and adjacency lists
Compare adjacency matrix vs adjacency list representations
Graph Definition
What is a Graph?
A graph is a non-linear data structure consisting of vertices (nodes) connected by edges (arcs). Graphs model relationships between entities with no required hierarchical structure — unlike trees.
Types of Graph
Undirected: edges have no direction — relationship is two-way (e.g. Facebook friendships)
Directed (digraph): edges have a direction shown by arrows (e.g. Twitter follows, road one-way systems)
Weighted: edges carry a value (e.g. distance, cost, time)
Real-World Applications
• Road/transport networks (GPS routing) • Social networks (friend connections) • Internet topology (routers and links) • Dependency resolution (software packages) • Neural networks (nodes and weights)
Adjacency Matrix
Representing Graphs: Adjacency Matrix
An adjacency matrix is a 2D array where matrix[i][j] = 1 (or weight) if there is an edge from vertex i to vertex j, and 0 otherwise.
Example (undirected, 4 nodes A,B,C,D)
A B C D
A[0,1,1,0]
B[1,0,0,1]
C[1,0,0,1]
D[0,1,1,0]
Trade-offs
Advantages: O(1) edge lookup; simple to implement Disadvantages: O(V²) space regardless of edge count; inefficient for sparse graphs (few edges)
Adjacency List
Representing Graphs: Adjacency List
An adjacency list stores, for each vertex, a list of all vertices it is connected to. More memory-efficient for sparse graphs.
Example (same graph)
A → [B, C]
B → [A, D]
C → [A, D]
D → [B, C]
Trade-offs
Advantages: O(V+E) space — efficient for sparse graphs; easy to find all neighbours Disadvantages: O(degree) edge lookup — slower than matrix for checking if a specific edge exists
Exam Practice
OCR H446 Style · 4 marks
Compare an adjacency matrix and an adjacency list for representing a large graph with few edges. State which you would recommend and justify your answer.
[4 marks]
1
Adjacency matrix uses O(V²) memory regardless of the number of edges — for a large graph with few edges (sparse), most of the matrix entries are 0, wasting a large amount of memory.
1
Adjacency list uses O(V+E) memory — only edges that exist are stored, making it much more efficient for sparse graphs.
1
Recommended: adjacency list for a large sparse graph because it uses significantly less memory.
1
However, checking whether a specific edge exists is O(1) with a matrix vs O(degree) with a list. If edge lookup speed is critical, the matrix may be preferred despite higher memory use.
Common Mistakes
Don't Lose Marks
!
Saying a tree is a type of graph incorrectly — a tree IS a special case of a graph (connected, acyclic, undirected). However in the OCR spec, graphs and trees are treated as separate structures. Do not describe a tree as just a graph in exam answers unless the question specifically asks about the relationship.
!
Drawing an adjacency matrix for a directed graph as symmetric — an undirected graph's adjacency matrix is symmetric (if [i][j]=1 then [j][i]=1). A directed graph's matrix is NOT necessarily symmetric. Arrows only go one way.
!
Saying adjacency lists are always better — lists are better for sparse graphs. For dense graphs (many edges), a matrix provides faster edge lookup (O(1)) and may be preferable. Always justify your choice relative to the graph's density.