Breadth First Search (BFS)

Breadth first search is an algorithm to visit the nodes of a graph or a tree.

In BFS, we use a queue to track the nodes that we need to visit, and a hash table to track nodes we've visited.

Starting at the root node, we add all neighbor nodes to the queue, as long as they have not been visited.

The node is then considered processed, so we don't need to explore that node further.

We pop the next node from our queue, and repeat the process until the queue becomes empty, at which point we've explored the entire graph.

Traverse a graph

Step through the graph below and see how nodes become visited (marked in gray).

Breadth first search in Python

Given a graph as an adjacency list, here's how we visit its nodes through BFS.

Remember, the Python utility collections.deque() is used to model a queue, and a set to model a hash table for tracking visited nodes.

import collections

graph = {
    'A': ['B', 'D'],
    'B': ['D', 'F'],
    'C': ['A', 'E'],
    'D': ['B', 'C', 'F'],
    'E': ['D', 'F'],
    'F': [],
}

starting_node = 'A'

def bfs():
    queue = collections.deque()
    queue.append(starting_node)
    visited = set(starting_node)
    while queue:
        node = queue.popleft()
        print('visiting', node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)


print("Breadth-First Search")
bfs()

1import collections
2
3graph = {
4    'A': ['B', 'D'],
5    'B': ['D', 'F'],
6    'C': ['A', 'E'],
7    'D': ['B', 'C', 'F'],
8    'E': ['D', 'F'],
9    'F': [],
10}
11
12starting_node = 'A'
13
14def bfs():
15    queue = collections.deque()
16    queue.append(starting_node)
17    visited = set(starting_node)
18    while queue:
19        node = queue.popleft()
20        print('visiting', node)
21        for neighbour in graph[node]:
22            if neighbour not in visited:
23                visited.add(neighbour)
24                queue.append(neighbour)
25
26
27print("Breadth-First Search")
28bfs()
29

9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

1.Inorder TraversalEasy
2.Tree SumEasy
3.Tree HeightEasy
4.LCAMedium
5.Max Path SumHard
6.Search mazeMedium
7.Number of islandsMedium
8.Kth SmallestMedium
9.Sort K ArraysHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.