Understand graphs, vertices and edges, directed, undirected and weighted graphs, and how a graph is represented as an adjacency matrix or an adjacency list.

What this dot point is asking

AQA wants you to define a graph in terms of vertices and edges, distinguish directed, undirected and weighted graphs, and represent a graph as either an adjacency matrix or an adjacency list, with the trade-offs between them.

Graphs, vertices and edges

• Undirected graph: edges have no direction, so a connection works both ways (like a two-way road or a mutual friendship).
• Directed graph (digraph): each edge has a direction, shown by an arrow (like a one-way street or a web hyperlink that points from one page to another).
• Weighted graph: each edge has a weight, such as distance, time or cost, used in shortest-path problems.

A graph is the most general of the structures in this module: a tree is just a special graph (connected, with no cycles), and a list is a graph where each vertex links to the next. Recognising graphs in real problems (social networks, transport maps, dependencies between tasks) is part of what the specification expects.

Adjacency matrix

Adjacency list

The rule of thumb is: use a matrix for a small or dense graph where fast edge look-up matters, and use a list for a large or sparse graph where memory matters. Most real-world graphs (road networks, the web) are sparse, so adjacency lists dominate in practice, while small fixed graphs in exam questions are often shown as matrices because they are easy to lay out.

To make the sparse-versus-dense distinction concrete: a graph is dense when the number of edges is close to the maximum possible (roughly $n^2$ for $n$ vertices), and sparse when it has far fewer. A road network is sparse because each junction connects to only a handful of others, never to thousands; a fully connected social clique would be dense. Since the adjacency matrix always uses $n^2$ cells regardless of edges, it is only memory-competitive when the graph is dense enough to fill most of those cells, which is rarely the case in practice.

The two representations also differ in which operations they make cheap, and this drives the choice as much as memory does. A matrix answers "is there an edge between $i$ and $j$?" in constant time by a single array look-up, which suits algorithms that test specific connections repeatedly. An adjacency list answers "what are the neighbours of $i$?" quickly by iterating one short list, which suits traversal algorithms such as breadth-first and depth-first search and Dijkstra's algorithm, where you repeatedly need a vertex's neighbours. Matching the representation to the dominant operation is the kind of reasoning higher-mark questions reward.