Graphs

This lesson covers graphs — a versatile data structure used to model relationships between objects. Graphs are fundamental to A-Level Computer Science and underpin routing, social networks, pathfinding, and many other applications.

---

What is a Graph?

A graph G is defined as a set of vertices (nodes) V and a set of edges (connections) E that connect pairs of vertices:

G = (V, E)

Unlike trees, graphs can contain cycles (paths that start and end at the same vertex), and there is no hierarchy (no root node).

Key Terminology

Term	Definition
Vertex (Node)	A data point in the graph.
Edge (Arc)	A connection between two vertices.
Adjacent	Two vertices connected by an edge are adjacent (neighbours).
Degree	The number of edges connected to a vertex.
Path	A sequence of vertices connected by edges.
Cycle	A path that starts and ends at the same vertex.
Connected graph	There is a path between every pair of vertices.

---

Types of Graphs

Directed vs Undirected

Type	Description	Example
Undirected	Edges have no direction — the connection is bidirectional.	Friendships on Facebook (if A is friends with B, then B is friends with A).
Directed (Digraph)	Edges have a direction — the connection is one-way.	Following on Twitter (A follows B does not mean B follows A).

Undirected:         Directed:
  A --- B            A → B
  |     |            ↓   ↑
  C --- D            C → D

Weighted vs Unweighted

Type	Description	Example
Unweighted	All edges are equal (no cost associated).	Simple connectivity maps.
Weighted	Each edge has a numerical value (weight/cost).	Road networks (distance), flight routes (cost).

Weighted graph:
  A --5-- B
  |       |
  3       2
  |       |
  C --7-- D

---

Representing Graphs

There are two main ways to represent a graph in a program:

1. Adjacency Matrix

An adjacency matrix is a 2D array where each cell [i][j] indicates whether there is an edge between vertex i and vertex j. For weighted graphs, the cell stores the weight instead of just 0/1.

Unweighted Example

Vertices: A(0), B(1), C(2), D(3)
Edges: A-B, A-C, B-D, C-D

    A  B  C  D
A [ 0  1  1  0 ]
B [ 1  0  0  1 ]
C [ 1  0  0  1 ]
D [ 0  1  1  0 ]

Weighted Example

    A  B  C  D
A [ 0  5  3  0 ]
B [ 5  0  0  2 ]
C [ 3  0  0  7 ]
D [ 0  2  7  0 ]

Python Implementation

# Adjacency matrix for an undirected weighted graph
vertices = ['A', 'B', 'C', 'D']
matrix = [
    [0, 5, 3, 0],  # A
    [5, 0, 0, 2],  # B
    [3, 0, 0, 7],  # C
    [0, 2, 7, 0],  # D
]

# Check if there's an edge between A and B
if matrix[0][1] != 0:
    print(f"Edge A-B with weight {matrix[0][1]}")

2. Adjacency List

An adjacency list stores, for each vertex, a list of its adjacent vertices (and optionally edge weights).

A: [(B, 5), (C, 3)]
B: [(A, 5), (D, 2)]
C: [(A, 3), (D, 7)]
D: [(B, 2), (C, 7)]

Python Implementation