A graph is a data structure consisting of a set of vertices (also called nodes) connected by edges (also called arcs). Graphs model relationships — who is connected to whom, which cities are linked by roads, which web pages link to each other — making them one of the most powerful and widely used structures in computing.
What makes graphs different from other data structures?
A list, array, or queue arranges data in a strict linear sequence: each item has at most one predecessor and one successor. A tree branches in one direction (parent to children). A graph has none of these restrictions — any vertex can connect to any other, in any number of connections, potentially in both directions. This freedom makes graphs the natural choice whenever the data involves complex, many-to-many relationships.
Think of a social network: you have friends, each of your friends has friends, and those friends may also be friends with each other. No linear structure or tree can cleanly represent this web of connections. A graph can.
What are the key vocabulary terms?
| Term | Definition |
|---|---|
| Vertex (node) | A point in the graph, representing an entity (city, person, web page) |
| Edge (arc) | A connection between two vertices |
| Directed graph (digraph) | Edges have direction — A→B does not imply B→A |
| Undirected graph | Edges have no direction — if A connects to B, B connects to A |
| Weighted graph | Each edge carries a numerical weight (distance, cost, time) |
| Unweighted graph | Edges simply indicate connection, with no numeric value |
| Path | A sequence of vertices connected by edges from one vertex to another |
| Cycle | A path that starts and ends at the same vertex |
| Degree | The number of edges connected to a vertex |
What are directed and undirected graphs?
Undirected graph: Edges are bidirectional — you can travel along them in either direction. A map of roads where every street is two-way is an undirected graph. If vertex A and vertex B are connected, you can go from A to B and from B to A.
Directed graph (digraph): Each edge has an arrow — you can only travel in the specified direction. A map of one-way streets is a directed graph. A→B does not mean B→A.
Undirected: Directed:
A --- B A --> B
| / |
C -- v
C
The internet is a directed graph: page A can link to page B without page B linking back.
What is a weighted graph?
A weighted graph assigns a value to each edge — typically representing distance, cost, time, or capacity. The edge between London and Birmingham might carry the weight 163 (kilometres). Algorithms like Dijkstra's shortest path algorithm use these weights to find the most efficient route through a network.
Worked example — weighted undirected graph (distances in miles):
| Edge | Weight |
|---|---|
| A — B | 5 |
| A — C | 8 |
| B — C | 3 |
| B — D | 7 |
| C — D | 4 |
To travel from A to D:
- Route A→B→D: 5 + 7 = 12
- Route A→C→D: 8 + 4 = 12
- Route A→B→C→D: 5 + 3 + 4 = 12
All three happen to cost the same here — in larger graphs, the differences are substantial and finding the minimum is non-trivial.
How is a graph stored in a computer? (Adjacency matrix)
One common representation is an adjacency matrix — a 2D array where row i and column j contain 1 (or the edge weight) if there is an edge from vertex i to vertex j, and 0 otherwise.
Graph: 4 vertices (A=0, B=1, C=2, D=3) with edges A-B, A-C, B-D, C-D (undirected, unweighted):
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
For an undirected graph, the matrix is always symmetric (the upper-right and lower-left triangles mirror each other). For a directed graph, row i→column j has a 1 only if there is an edge FROM i TO j.
Adjacency list (alternative): Each vertex stores a list of its neighbours. More memory-efficient for sparse graphs (few edges relative to vertices); adjacency matrices are faster for checking whether two specific vertices are connected.
What real-world problems do graphs model?
| Application | Vertices | Edges | Directed? | Weighted? |
|---|---|---|---|---|
| Road navigation (sat-nav) | Junctions | Roads | Both | Yes (distance/time) |
| Internet routing | Routers | Network links | Yes | Yes (bandwidth) |
| Social networks | People | Friendships | No (usually) | No |
| Dependency resolution | Software packages | "Requires" relationships | Yes | No |
| Airline routes | Airports | Flights | Yes | Yes (distance/price) |
Frequently asked questions
What is the difference between a graph and a tree?
A tree is a special type of graph with exactly one path between any two vertices — no cycles, and one designated root. Graphs have no such restrictions: they can contain cycles, multiple paths between vertices, and no designated root. Every tree is a graph, but not every graph is a tree. Family trees, decision trees, and folder hierarchies are trees; road networks and social networks are general graphs.
What is Dijkstra's algorithm?
Dijkstra's algorithm finds the shortest (minimum-weight) path from one source vertex to all other vertices in a weighted, non-negative graph. It works by maintaining a set of visited vertices and always extending the current shortest known path. At GCSE you may be asked to trace Dijkstra's algorithm by hand — the key rule is: always pick the unvisited vertex with the smallest current known distance.
What is a spanning tree?
A spanning tree of a graph is a subgraph that connects all vertices without any cycles, using the minimum number of edges (exactly n−1 edges for n vertices). A minimum spanning tree (MST) additionally minimises the total edge weight. MSTs are used in network design — laying cables or pipelines to connect all locations at minimum total cost. Kruskal's and Prim's algorithms both find MSTs and may appear at GCSE extension level.
Can a graph have no edges?
Yes — a graph with vertices but no edges is called an empty graph or null graph. It represents a situation where entities exist but have no relationships between them. At the other extreme, a complete graph (Kn) has an edge between every pair of vertices — for 4 vertices, that is 6 edges. The density of a graph (ratio of actual edges to maximum possible edges) affects which data structure (adjacency matrix vs adjacency list) is more efficient to use.
Master graph data structures and algorithm tracing with Professor Turing's interactive tutoring at aitutors.me.