# Graphs

> Computer Science · CIE A-Level 9618
> Source: https://www.owlsprep.com/study/cie-9618-u10-graphs/

Graphs are flexible non-linear data structures used to model relationships between entities. This guide covers key terminology, storage methods, traversal algorithms, and common exam requirements for CIE 9618.

**Prerequisites:** [Non-linear data structures](https://www.owlsprep.com/study/cie-9618-u10-non-linear-data-structures/); [Trees](https://www.owlsprep.com/study/cie-9618-u10-trees/)

## Learning objectives

- Define key graph terminology and distinguish between common graph types
- Compare adjacency matrix and adjacency list graph storage methods
- Implement and trace BFS and DFS graph traversal algorithms
- Identify appropriate use cases for graphs in real-world problems

## Key Terminology and Graph Types

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

*Notation:* $G = (V, E)$

*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.

## Graph Representation: Storage Methods

**Comparing methods**

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 $matrix[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.

*Calculator:* forbidden

## Graph Traversal Algorithms

**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]$$

**Check your understanding**

1. Which data structure is used for DFS traversal?

   - Queue
   - Stack
   - Array
   - Linked List

   *Answer:* Stack

   *Why:* Correct! DFS uses a stack to track the next path to explore, while BFS uses a queue.

## Real-World Applications of Graphs

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.

## Common pitfalls

- **Wrong:** Assuming all adjacency matrices are symmetric
  - Why it fails: Symmetry only applies to undirected graphs, directed graphs do not have symmetric adjacency matrices
  - Correct: Check if the graph is directed or undirected before commenting on matrix symmetry
- **Wrong:** Confusing BFS and DFS data structures: stating BFS uses a stack and DFS uses a queue
  - Why it fails: This is one of the most common exam mistakes that costs easy 1-2 markers
  - Correct: Memorize: BFS = Breadth = Broad = Queue, DFS = Depth = Deep = Stack
- **Wrong:** Claiming adjacency lists are always more efficient than adjacency matrices
  - Why it fails: Efficiency depends on graph density; for dense graphs, adjacency matrices are more efficient
  - Correct: Compare efficiency based on density: adjacency matrices for dense graphs, adjacency lists for sparse graphs
- **Wrong:** Forgetting to mark vertices as visited during traversal
  - Why it fails: Unmarked vertices cause infinite loops when traversing cyclic graphs
  - Correct: Always maintain a visited array or set to track explored vertices during traversal

## 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 |

## 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.

- [Trees](https://www.owlsprep.com/study/cie-9618-u10-trees/)
- [Hash tables](https://www.owlsprep.com/study/cie-9618-u10-hash-tables/)
- [Programming](https://www.owlsprep.com/study/cie-9618-u11-overview/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/cie-9618-u10-graphs/