Graphs

This lesson covers graphs — a versatile and powerful data structure used to model relationships between objects. Graphs are a key topic in the OCR A-Level Computer Science (H446) specification, section 1.4.

---

What is a Graph?

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

G = (V, E)

Graphs differ from trees because they can contain cycles (paths that loop back), there is no hierarchy (no root), and any vertex can connect to any other vertex.

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.
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	A path exists between every pair of vertices.
Complete graph	Every vertex is connected to every other vertex.

---

Types of Graphs

Directed vs Undirected

Type	Description	Example
Undirected	Edges have no direction — bidirectional	Friendships (if A knows B, B knows A)
Directed (Digraph)	Edges have a direction — one-way	Web links (page A links to B, but B may not link to A)

Undirected:         Directed:
  A --- B            A --> B
  |     |            |     ^
  C --- D            v     |
                     C --> D

In a directed graph, each edge has a start vertex and an end vertex. The in-degree of a vertex is the number of edges coming in; the out-degree is the number of edges going out.

Weighted vs Unweighted

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

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

---

Representing Graphs

1. Adjacency Matrix

An adjacency matrix is a 2D array where cell [i][j] indicates whether there is an edge between vertex i and vertex j.

• For unweighted graphs: 1 = edge exists, 0 = no edge.
• For weighted graphs: the cell stores the weight (0 or infinity = no edge).

Unweighted Undirected 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 ]

Note: For undirected graphs, the matrix is symmetric (matrix[i][j] == matrix[j][i]).

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 ]

Directed Example

Edges: A->B, A->C, C->D, D->B

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

Note: For directed graphs, the matrix is not necessarily symmetric.

Python Implementation

# Adjacency matrix for 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 edge exists between A and B
if matrix[0][1] != 0:
    print(f"Edge A-B with weight {matrix[0][1]}")

# Find all neighbours of vertex A (index 0)
for j in range(len(vertices)):
    if matrix[0][j] != 0:
        print(f"A -> {vertices[j]} (weight {matrix[0][j]})")

---

2. Adjacency List