Graph Traversal: Breadth-First Search

A graph is a data structure consisting of vertices (nodes) connected by edges. Graphs model real-world problems such as road networks, social networks, web page links, and computer networks. Graph traversal means visiting every vertex in the graph in a systematic way. At A-Level, you must understand two traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS).

---

Graph Representations

Before traversing a graph, you need to represent it in memory. There are two standard representations:

Adjacency Matrix

A 2D array where entry [i][j] = 1 if there is an edge from vertex i to vertex j, and 0 otherwise.

Example graph: 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 ]

Adjacency List

Each vertex stores a list of its neighbours.

A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C]