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]

Feature	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Check if edge exists	O(1)	O(degree)
List all neighbours	O(V)	O(degree)
Best for	Dense graphs	Sparse graphs

---

Breadth-First Search (BFS)

How It Works

BFS explores a graph level by level. Starting from a source vertex, it first visits all vertices at distance 1, then all vertices at distance 2, and so on. It uses a queue (FIFO) to track which vertex to visit next.

Algorithm Steps

1. Enqueue the starting vertex and mark it as visited.
2. While the queue is not empty: a. Dequeue the front vertex (call it v). b. Process v (e.g., print it or record it). c. For each unvisited neighbour of v, mark it as visited and enqueue it.

Pseudocode

PROCEDURE BFS(graph, start)
    CREATE queue
    CREATE visited set
    ENQUEUE start
    ADD start TO visited
    WHILE queue IS NOT EMPTY
        v = DEQUEUE
        OUTPUT v
        FOR EACH neighbour OF v IN graph
            IF neighbour NOT IN visited THEN
                ADD neighbour TO visited
                ENQUEUE neighbour
            END IF
        END FOR
    END WHILE
END PROCEDURE

Trace Example

Consider this graph:

    A --- B --- E
    |         |
    C --- D ---+

Adjacency list:

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

BFS starting from A: