Graphs

Computer Science· Unit 10: Data types & structures, Topic 8· 15 min read

1. Key Terminology and Graph Types★★☆☆☆⏱ 4 min

📘 Definition

Graph

$G = (V, E)$

A non-linear data structure consisting of a finite set of vertices (nodes) and a finite set of edges that connect pairs of vertices.

Example:

A social network where users are vertices and friendships are edges.

Graphs are categorized based on edge properties and connectivity. The most common classifications tested in exams are listed below:

Directed vs Undirected: Directed graphs (digraphs) have edges with a one-way direction, while undirected graphs have bidirectional edges.
Weighted vs Unweighted: Weighted graphs assign a numerical weight to each edge, unweighted graphs do not.
Connected vs Disconnected: A connected graph has a path between every pair of vertices; disconnected graphs have at least two vertices with no connecting path.
Cyclic vs Acyclic: A cyclic graph contains at least one path that starts and ends at the same vertex; an acyclic graph has no cycles.

📐 Worked Example

Classify the following graph: A map of flight routes between cities, where each route has a listed distance in kilometers and can be flown in both directions.

1
First, check edge direction: flight routes can be flown both ways, so the graph is undirected.
2
Next, check for edge values: each route has a distance, so the graph is weighted.
3
Assuming all cities are reachable from each other, the graph is connected. Final classification: connected, undirected, weighted graph.

Exam tip:

Always check all three properties (direction, weight, connectivity) when asked to classify a graph; marks are awarded for each correct classification.

2. Graph Representation: Storage Methods★★★☆☆⏱ 6 min

🚫 No Calculator

Methods compared

Graphs are stored in memory using one of two common methods, both frequently compared in CIE exams:

Adjacency Matrix

A 2D array of size $∣ V ∣ \times ∣ V ∣$ , where entry $ma t r i x [i] [j]$ stores 1 (or the edge weight) if there is an edge between vertex $i$ and vertex $j$ , and 0 (or null) otherwise.

+ Pros: O(1) time to check if an edge exists between two vertices; Simple to implement for small graphs

− Cons: Wastes space for sparse graphs; O(|V|²) space complexity regardless of edge count

Adjacency List

An array of lists, where each index $i$ represents a vertex, and the list at index $i$ stores all connected vertices (and any edge weight).

+ Pros: More space-efficient for sparse graphs (most real-world graphs are sparse); O(|V| + |E|) space complexity

− Cons: Slower edge existence check (requires traversing the adjacency list)

📐 Worked Example

Write the adjacency matrix for the following undirected, unweighted graph with 4 vertices: Edges are (0,1), (0,2), (1,2), (2,3).

1
The matrix is 4×4 for 4 vertices, and symmetric for an undirected graph, giving the result:
2
$\begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}$
3
Diagonal entries are 0 because there are no self-loops in this graph.

3. Graph Traversal Algorithms★★★☆☆⏱ 5 min

📘 Definition

Graph Traversal

The process of visiting (exploring) every vertex and edge in a graph in a systematic order.

Example:

Used to find paths between nodes, check connectivity, and search for specific values.

Two core traversal algorithms are tested in CIE A-Level: Breadth-First Search (BFS) and Depth-First Search (DFS).

Breadth-First Search (BFS): Explores all vertices at the current depth level before moving to vertices at the next depth level. Uses a queue to track next vertices to visit.
Depth-First Search (DFS): Explores as far as possible along a single path before backtracking to explore other paths. Uses a stack (or recursion) to track next vertices to visit.

📐 Worked Example

List the order of vertices visited by BFS starting at vertex 0 for the 4-vertex graph from the previous example.

1
Initialize queue with vertex 0, mark 0 as visited. Dequeue 0, add to visited order:
2
$Visited = [0]$
3
Enqueue all unvisited neighbors of 0 (1, 2), mark as visited. Dequeue 1, add to visited order:
4
$Visited = [0, 1]$
5
All neighbors of 1 are already visited. Dequeue 2, add to visited order:
6
$Visited = [0, 1, 2]$
7
Enqueue unvisited neighbor 3. Dequeue 3, add to visited order. Traversal complete:
8
$Final BFS order = [0, 1, 2, 3]$

✓ Quick check

Which data structure is used for DFS traversal?
- Queue
- Stack
- Array
- Linked List
Reveal answer
1 —
Correct! DFS uses a stack to track the next path to explore, while BFS uses a queue.

4. Real-World Applications of Graphs★★☆☆☆⏱ 3 min

CIE exams often ask you to explain why graphs are a suitable data structure for a given problem. Common applications of graphs include:

Social networks (modeling users and connections/friendships)
Navigation systems (modeling locations and road/flight connections)
Task dependency graphs for project scheduling
Web graph modeling (web pages and hyperlinks)
Electrical circuit design (modeling components and connections)

📐 Worked Example

Explain why a graph is a suitable data structure for modeling a network of water pipes.

1
Graphs can model pipe junctions as vertices, and the pipes themselves as edges between junctions.
2
Additional properties like pipe diameter or flow capacity can be stored as weights on the edges.
3
Graph traversal algorithms can find paths between any two junctions for flow analysis and leak detection. No other common data structure can model arbitrary connections between entities as flexibly as a graph.

Exam tip:

When asked why graphs are suitable, always explicitly state what vertices and edges represent in your answer to get full marks.

5. Common Pitfalls

Wrong move:

Assuming all adjacency matrices are symmetric

Why:

Symmetry only applies to undirected graphs, directed graphs do not have symmetric adjacency matrices

Correct move:

Check if the graph is directed or undirected before commenting on matrix symmetry

Wrong move:

Confusing BFS and DFS data structures: stating BFS uses a stack and DFS uses a queue

Why:

This is one of the most common exam mistakes that costs easy 1-2 markers

Correct move:

Memorize: BFS = Breadth = Broad = Queue, DFS = Depth = Deep = Stack

Wrong move:

Claiming adjacency lists are always more efficient than adjacency matrices

Why:

Efficiency depends on graph density; for dense graphs, adjacency matrices are more efficient

Correct move:

Compare efficiency based on density: adjacency matrices for dense graphs, adjacency lists for sparse graphs

Wrong move:

Forgetting to mark vertices as visited during traversal

Why:

Unmarked vertices cause infinite loops when traversing cyclic graphs

Correct move:

Always maintain a visited array or set to track explored vertices during traversal

6. Quick Reference Cheatsheet

Category	Item	Key Properties
Storage	Adjacency Matrix	$∣ V ∣ \times ∣ V ∣$ array, O(1) edge check
Storage	Adjacency List	Array of lists, space efficient for sparse graphs
Traversal	BFS	Queue, level-order search, shortest path unweighted
Traversal	DFS	Stack/recursion, path-first search, cycle detection
Graph Type	Directed	Edges one-way, asymmetric adjacency matrix
Graph Type	Undirected	Edges bidirectional, symmetric adjacency matrix
Graph Type	Weighted	Edges have associated numerical weights
Graph Type	Unweighted	Edges have no additional stored value

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2022 · 12
Adjacency matrix construction
2023 · 11
Graph traversal comparison
2021 · 13
Storage method comparison

Going deeper

syllabusCIE 9618 Official Syllabus

What's Next

Graphs are a fundamental non-linear data structure that form the basis for many advanced algorithms in computer science, including shortest path algorithms like Dijkstra's and minimum spanning tree algorithms tested in CIE 9618. Mastery of graph basics is critical for both Paper 1 multiple choice and theory questions, as well as programming practical questions where you may be asked to implement a graph or traversal algorithm. Understanding the trade-offs between storage methods and traversal approaches will help you select the right solution for any problem, and prepares you for more advanced graph topics that build on these core concepts.