Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

A vertex is reachable from if there is a path from to . An exhaustive search starts at a vertex and visits every reachable vertex exactly once, without repeating visits. A random walk might also reach every vertex, but it is inefficient. BFS and DFS are the two exhaustive methods.

Basic Idea

Breadth-first search (BFS) from a start vertex first discovers every vertex one edge away, then every vertex two edges away, and so on. The frontier between discovered and undiscovered vertices grows uniformly, one edge per round. On a binary tree this explores one level per round.

Queue Implementation

BFS uses a FIFO queue:

  • add start to a queue q
  • while q is not empty: take the front value v, add it to visited and remove it from q
  • add all unvisited adjacent vertices of v to the back of q (left to right)

Python Code with Adjacency List

def bfs(graph, start):
    visited = [False] * (len(graph) + 1)
    queue = [start]
    visited[start] = True
    order = []
    while queue:
        vertex = queue.pop(0)            # dequeue the front element
        order.append(vertex)
        for neighbor in graph[vertex]:
            if not visited[neighbor]:
                queue.append(neighbor)
                visited[neighbor] = True # mark when added, so no duplicates
    return order

For a binary tree the same loop appends node.left then node.right to the queue, giving the level order, e.g. [1, 2, 3, 4, 5, 6, 7, 8].

Shortest Path Lengths

Because BFS explores in rounds, the round in which a vertex is discovered equals its number of edges from the start. One extra line records it:

distances[neighbor] = distances[vertex] + 1   # when neighbor is first added

This gives the shortest path length in an unweighted graph. For weighted graphs BFS is not enough, and Dijkstra's algorithm is used instead.

Time Complexity

In the worst case every vertex is visited once, , and every edge is checked to find neighbours, . So BFS takes for vertices and edges.