Graphs: Directed, Undirected & How to Represent Them (OCR A-Level CS 1.4.2)
OCR A-Level CS 1.4.2: graphs explained — nodes and edges, directed vs undirected vs weighted, adjacency matrix vs adjacency list, and when to use each.
Free Graphs revision resources (OCR A-Level Computer Science, 1.4.2)
We’ve made exam-style practice for this exact topic, free to download: Graphs question sheet, mark scheme and cheat sheet. Grab them, have a go, then read the full guide below.
Graphs model connections — friends in a social network, roads between cities, links between web pages. Spec points 1.4.2(b) and (c) cover the graph data structure: directed and undirected graphs, and how they're represented with an adjacency matrix or an adjacency list. Exam questions ask you to draw a graph from a representation (or vice versa) and to contrast the two representations.
Let's define the graph, the three flavours you need, and the two ways to store one.
What is a graph?
A graph is a set of nodes (also called vertices) connected by edges (also called arcs). Unlike a tree, a graph has no hierarchy — any node can connect to any other, and the connections can form loops. Graphs are perfect for modelling networks of relationships.
The three types you must know:
Undirected graph — edges have no direction; a connection between A and B works both ways (like a friendship: if A is friends with B, B is friends with A).
Directed graph (digraph) — edges have a direction, shown by an arrow; A → B does not imply B → A (like "follows" on social media, or one-way streets).
Weighted graph — each edge carries a weight (a value or cost), such as the distance or time between two cities. Weights can appear on directed or undirected graphs.
Representing a graph: adjacency matrix
An adjacency matrix is a 2-D array (a grid) with one row and one column per node. Each cell records whether an edge exists between that pair of nodes: a 1 (or the weight) if there's an edge, 0 if not.
For an undirected graph the matrix is symmetrical (an edge A–B appears as both A,B and B,A).
For a directed graph it isn't — A→B fills one cell but not the reverse.
For a weighted graph, store the weight in the cell instead of a 1.
A matrix makes it instant to check whether two specific nodes are connected, and easy to add or remove an edge. The downside: it uses space for every possible edge, so for a sparse graph (few edges) most of the grid is 0 — wasted memory.
Representing a graph: adjacency list
An adjacency list stores, for each node, a list of just the nodes it is directly connected to. It's often implemented as an array (or dictionary) of nodes, each pointing to a list of its neighbours.
This only stores edges that actually exist, so it's much more memory-efficient for sparse graphs. The trade-off: to check whether two specific nodes are connected, you have to search a node's list rather than reading one cell.
Choosing between them
Adjacency matrix | Adjacency list | |
|---|---|---|
Structure | 2-D grid (node × node) | List of neighbours per node |
Memory | Stores every possible edge | Stores only existing edges |
Best for | Dense graphs (many edges) | Sparse graphs (few edges) |
Check if A–B connected | Read one cell (fast) | Search A's list |
Add an edge | Set one cell | Add to a list |
The rule of thumb: a dense graph favours the matrix (it's compact and quick to query); a sparse graph favours the list (it avoids storing all those zeros).
Worked example
Take an undirected graph with nodes A, B, C, D where the edges are A–B, A–C and C–D. As an adjacency list: A → [B, C], B → [A], C → [A, D], D → [C]. As an adjacency matrix (rows/cols A,B,C,D) the 1s appear at A-B, B-A, A-C, C-A, C-D and D-C — symmetrical because the graph is undirected. Notice the list stores six entries while the matrix stores all sixteen cells (mostly 0) — for this sparse graph, the list is leaner.
Common exam mistakes
Forgetting symmetry. An undirected graph's adjacency matrix is symmetrical; a directed graph's is not.
Putting weights in the wrong place. For a weighted graph, store the weight in the matrix cell or alongside the neighbour in the list — not just a 1.
Mixing up matrix and list strengths. Matrix = quick edge check, good for dense graphs; list = memory-efficient, good for sparse graphs.
Confusing graphs with trees. A tree is a special graph with a hierarchy and no cycles; a general graph can have cycles and no root.
Drawing directed edges without arrows. Directed graphs must show the arrow direction.
Quick recap
A graph = nodes connected by edges; no hierarchy, can contain cycles.
Undirected (two-way edges), directed (one-way, arrows), weighted (edges carry a value).
Adjacency matrix: 2-D grid, a 1/weight per edge; symmetrical if undirected; best for dense graphs.
Adjacency list: each node lists its neighbours; stores only real edges; best for sparse graphs.
Matrix = fast edge lookup but more memory; list = memory-efficient but slower lookup.
Frequently asked questions
What is a graph in computer science? A graph is a data structure made of nodes (vertices) connected by edges (arcs). Unlike a tree it has no hierarchy, so any node can be connected to any other and the connections can form cycles, making graphs ideal for modelling networks of relationships.
What is the difference between a directed and an undirected graph? In an undirected graph the edges have no direction, so a connection between two nodes works both ways. In a directed graph the edges have a direction shown by an arrow, so an edge from A to B does not imply an edge from B to A.
What is a weighted graph? A weighted graph is one in which each edge carries a value, called a weight, representing something like the distance, cost or time associated with that connection. Weights can be used on both directed and undirected graphs, for example to model distances between cities.
What is an adjacency matrix? An adjacency matrix is a two-dimensional array with one row and column per node, where each cell records whether an edge exists between that pair of nodes, using a 1 (or the weight) for an edge and 0 otherwise. For an undirected graph the matrix is symmetrical.
What is an adjacency list? An adjacency list stores, for each node, a list of only the nodes it is directly connected to. It is often an array or dictionary of nodes each pointing to a list of neighbours, and it stores only the edges that actually exist, making it memory-efficient for sparse graphs.
When should you use an adjacency matrix instead of an adjacency list? An adjacency matrix is best for a dense graph with many edges, because it is compact relative to the number of edges and lets you check whether two nodes are connected by reading a single cell. An adjacency list is better for a sparse graph because it avoids storing space for edges that do not exist.
