B4.1.5 · Abstract data types (ADTs)
Graphs
By the end you can
Construct and evaluate graph data structures, comparing 2D adjacency matrix and dynamic adjacency list memory representations.
While trees restrict connections to strict parent-child hierarchies with a single root, many real-world systems are far more complex: airline flight maps, road networks, social media friendships, and the World Wide Web itself. A is a general non-linear data structure capable of modeling arbitrary network relationships.
Vertices, edges, and graph types#
A graph $G = (V, E)$ consists of:
- Vertices (nodes) $V$: The individual entities (e.g. airports, web pages, users).
- Edges $E$: The links connecting pairs of vertices.
Graphs are classified according to edge properties:
- Undirected Graph: Edges are symmetric two-way streets. If $A$ connects to $B$, then $B$ connects to $A$.
- Directed Graph (Digraph): Edges have one-way arrows. A link from $A \rightarrow B$ does not allow travel from $B \rightarrow A$.
- Weighted Graph: Each edge carries a numerical weight representing distance, transit time, or financial cost (used by GPS navigation algorithms like Dijkstra’s).
Representing graphs in memory#
Computers store graphs using two primary representation strategies:
- :A 2D square matrix of size $V \times V$ where
matrix[u][v] = 1if an edge connects vertex $u$ to vertex $v$, and0otherwise.- Pros: Checking if edge $(u, v)$ exists takes instantaneous $O(1)$ time.
- Cons: Consumes $O(V^2)$ memory space regardless of whether edges exist. If a social network has 1,000,000 users, a matrix requires 1 trillion entries!
- :An array or hash map of linked lists. Each vertex stores a list containing only its actual connected neighbors.
- Pros: Consumes only $O(V + E)$ memory, making it far superior for sparse graphs (where each node connects to only a few neighbors).
- Cons: Checking if an edge exists takes $O(k)$ time where $k$ is the degree (number of neighbors) of vertex $u$.
Check yourself
Graphs and representations
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 8 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Compare an adjacency matrix and an adjacency list representation of a graph in terms of space complexity and edge lookup efficiency.
[4]Compare: Similarities and differences, about both things, point by point.
2.Distinguish between a directed graph and an undirected graph, providing a real-world computing example of each.
[2]Distinguish: Make the differences between two things clear.
3.Explain what a weighted graph is and state one practical application where weights are essential.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
In a nutshell
- A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections).
- Graphs can be directed (one-way edges) or undirected (two-way edges), and unweighted or weighted (edges have numerical costs/distances).
- An adjacency matrix is a 2D V x V array with O(1) edge lookup but O(V²) memory consumption.
- An adjacency list uses O(V + E) memory by storing only active neighbors, making it ideal for sparse graphs.