Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Exhaustive Graph Search
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
startto a queueq - while
qis not empty: take the front valuev, add it to visited and remove it fromq - add all unvisited adjacent vertices of
vto the back ofq(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 orderFor 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 addedThis 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.