Breadth First Search (BFS)

Start here Breadth first search explores a graph layer by layer: first everything 1 step away, then everything 2 steps away, and so on — like ripples spreading out when you drop a stone in water. A bonus: BFS automatically finds the shortest path (fewest edges) to every reachable vertex.

The idea #

Start at a source vertex.

1. First visit all vertices one step away.
2. Then all vertices two steps away.
3. ... and so on.

Every visited vertex must be explored once: look at its neighbours and visit the ones not yet visited. Never explore a vertex twice.

So we keep track of two things:

• Which vertices have been visited (a visited dictionary: True / False).
• Which visited vertices are still waiting to be explored — kept in a queue.

Everyday example: News spreads in a class. You tell your friends (1 step). They tell their friends (2 steps). Nobody tells the same news twice to someone who already knows it.

The queue — first in, first out #

A queue is like a line at a ticket counter: whoever joins first is served first.

class Queue:
    def __init__(self):
        self.queue = []
    def addq(self, v):              # join at the back
        self.queue.append(v)
    def delq(self):                 # leave from the front
        v = None
        if not self.isempty():
            v = self.queue[0]
            self.queue = self.queue[1:]
        return v
    def isempty(self):
        return self.queue == []
    def __str__(self):
        return str(self.queue)

q = Queue()
for i in range(3):
    q.addq(i)
    print(q)            # [0]   then [0, 1]   then [0, 1, 2]
print(q.isempty())      # False
for j in range(3):
    print(q.delq(), q)  # 0 [1, 2]   then 1 [2]   then 2 []
print(q.isempty())      # True

(Note: self.queue[1:] copies the list, so this simple delq is O(n). Python's collections.deque has a truly O(1) popleft(). For learning, the simple class is fine.)

The BFS algorithm #

1. Set visited[v] = False for every vertex. Start with an empty queue.
2. Visit the start vertex: mark it True and add it to the queue.
3. While the queue is not empty:

- Remove the vertex j at the front of the queue and explore it: - For each neighbour k of j: if k is not visited, mark it visited and add it to the queue.

1. Stop when the queue is empty.

def BFSList(AList, v):
    visited = {}
    for i in AList.keys():
        visited[i] = False
    q = Queue()

    visited[v] = True
    q.addq(v)

    while (not q.isempty()):
        j = q.delq()
        for k in AList[j]:
            if (not visited[k]):
                visited[k] = True
                q.addq(k)

    return visited

Full trace — BFS from vertex 7 (undirected airline graph) #

Adjacency list: 0:[1, 2, 4], 1:[0, 2], 2:[0, 1], 3:[4, 5, 6], 4:[0, 3, 7], 5:[3, 6, 7, 8], 6:[3, 5], 7:[4, 5, 8], 8:[5, 7, 9], 9:[8].

All 10 vertices are visited → every city is reachable from 7.

How long does BFS take? #

Let n = number of vertices and m = number of edges. Each reachable vertex is visited once (added to the queue) and explored once (removed from the queue). Exploring a vertex means checking all its edges.

Why is the sum of degrees 2m? In an undirected graph each edge (i, j) is counted twice: once in degree(i) and once in degree(j). (Check: the undirected airline graph has 13 edges; its degrees are 3, 2, 2, 3, 3, 4, 2, 3, 3, 1, which add up to 26 = 2 × 13 ✔.)

This "add up the cost over the whole run instead of per step" reasoning is another example of amortised analysis.

Why we keep n and m separate: a connected graph can have anywhere from n − 1 edges to n(n − 1)/2 edges. If m is much smaller than n², the adjacency list is much faster. O(n + m) — "linear time" — is the best possible for graphs, because you must look at every vertex and edge at least once.

Recording paths — the parent #

BFS tells us whether k is reachable. To get the actual route, remember who discovered k:

When exploring j marks k as visited, set parent[k] = j.

Then from any vertex, follow parent links back to the start.

def BFSListPath(AList, v):
    (visited, parent) = ({}, {})
    for i in AList.keys():
        visited[i] = False
        parent[i] = -1
    q = Queue()

    visited[v] = True
    q.addq(v)

    while (not q.isempty()):
        j = q.delq()
        for k in AList[j]:
            if (not visited[k]):
                visited[k] = True
                parent[k] = j
                q.addq(k)

    return (visited, parent)

Recording distance — the level #

Even better: instead of True/False, store each vertex's level (number of edges from the start). Use −1 for "not visited yet".

def BFSListPathLevel(AList, v):
    (level, parent) = ({}, {})
    for i in AList.keys():
        level[i] = -1
        parent[i] = -1
    q = Queue()

    level[v] = 0
    q.addq(v)

    while (not q.isempty()):
        j = q.delq()
        for k in AList[j]:
            if (level[k] == -1):
                level[k] = level[j] + 1
                parent[k] = j
                q.addq(k)

    return (level, parent)

Result of BFS from 7:

Shortest path from 7 to 2: start at 2 and follow parents: 2 → parent 0 → parent 4 → parent 7. Reverse it: 7 – 4 – 0 – 2 (3 edges, matches level[2] = 3).

level[k] is the length of the shortest path from the start to k, counted in number of edges.

(Later in the course we'll see weighted graphs, where edges have costs like distance or ticket price; there "shortest" means least total cost, and BFS alone is not enough.)

In one line: BFS explores level by level using a queue, takes O(n + m) with adjacency lists (O(n²) with a matrix), and its parent/level records give shortest paths in number of edges.

Exam words: BFS, visited, explored, queue (FIFO), addq, delq, level, parent, shortest path (number of edges), O(n²) matrix, O(n + m) list, sum of degrees = 2m, amortised.

Quick check #