Breadth-First Search
Graphs Overview
Count: 10
Like Depth-First Search, breadth-first search is also used to traverse graphs. In this section, we'll cover how to implement BFS on both adjacency lists and matrices, as well as the types of problems that are best solved using BFS.
Just like with depth-first search, the most important thing to remember when implementing BFS on a graph is to keep track of visited nodes to avoid infinite loops. If we try to enqueue a node that has already been visited, we should skip it instead of adding it to the queue.
BFS on an Adjacency List
To traverse a graph represented with an adjacency list with BFS:
- Choose a starting node and add it to the queue (we start with the first node in the adjacency list Node "1" in the example below).
- While the queue is not empty, remove the node at the front of the queue and add it to the set of visited nodes.
- Add the children of the node to the back of the queue (if they haven't been visited yet).
- Repeat steps 2 and 3 until the queue is empty.
The animation shows how BFS traverses the graph represented by:
Solution
Python
adjList = {"1": ["2", "4"],"2": ["1", "3"],"3": ["2", "4"],"4": ["1", "3", "5"],"5": ["4"]}
Visualization
Python
from collections import dequedef bfs(start):visited = set([start])queue = deque([start])while queue:node = queue.popleft()for neighbor in adjList[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)
0 / 11
BFS on an Matrix (2D Grid)
To traverse a graph represented as a matrix with BFS:
- Choose a starting node and add it to the queue (we start with top left node in the example below).
- While the queue is not empty, remove the node at the front of the queue and add it to the set of visited nodes.
- Add the four neighbors of the node to the back of the queue (if they haven't been visited yet and are within the bounds of the matrix).
- Repeat steps 2 and 3 until the queue is empty.
The animation shows how BFS traverses the graph represented by:
Solution
Python
matrix = [[0, 0, 0],[0, 1, 1],[0, 1, 0]]
Visualization
Python
from collections import dequedef bfs(grid):visited = set()# up, down, left, rightdirections = [(-1, 0), (1, 0), (0, -1), (0, 1)]queue = deque([(0, 0)])visited.add((0, 0))while queue:row, col = queue.popleft()# enqueue neighborsfor dr, dc in directions:n_row = row + drm_col = col + dc# check bounds and if neighbor is visitedif 0 <= n_row < len(grid) \and 0 <= m_col < len(grid[0]) \and (n_row, m_col) not in visited:queue.append((n_row, m_col))visited.add((n_row, m_col))
0 / 20
Nodes at a Level
Like binary trees, graphs can also have levels. In a graph, a level is defined as the number of edges between the root node and the current node, which is also known as the "distance" between the two nodes.
This is the primary use case of BFS in graphs: to solve questions that involve traversing the graph level-by-level, so we should be familiar with this pattern for both adjacency lists and matrices.
And just like binary trees, the BFS algorithm can be extended to know when we have finished processing all nodes at a level. We can do this by adding a for-loop that iterates over the size of the queue at the beginning of each level.
Adjacency List Level-By-Level
Solution
Python
from collections import dequedef bfs_levels(graph, start):queue = deque([start])visited = set()visited.add(start)levels = []while queue:level_size = len(queue)current_level = []for _ in range(level_size):node = queue.popleft()current_level.append(node)for neighbor in graph[node]:if neighbor not in visited:visited.add(neighbor)queue.append(neighbor)# IMPORTANT# we have finished processing all nodes at the current levellevels.append(current_level)return levels
Matrix Level-By-Level
Solution
Python
from collections import dequedef bfs_level_by_level(matrix):rows, cols = len(matrix), len(matrix[0])directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]# start at the top-left cornerqueue = deque([(0, 0)])visited = set([(0, 0)])levels = []while queue:level_size = len(queue)current_level = []for _ in range(level_size):row, col = queue.popleft()current_level.append((row, col))for dr, dc in directions:r, c = row + dr, col + dcif 0 <= r < rows and 0 <= c < cols and (r, c) not in visited:visited.add((r, c))queue.append((r, c))# IMPORTANT# we have finished processing all nodes at this levellevels.append(current_level)return levels
Shortest Path in a Graph
A consequence of the level-by-level nature of BFS traversal is that we can use it to find the shortest path between two nodes in a graph. Because BFS traverses the graph level-by-level, the first time we reach the destination node will be on the shortest path between the two nodes.
The animation below shows how BFS finds the shortest path between the top left node in the matrix and the first node with value "1":
Visualization
0 / 8
Compare this to depth-first search, where the first path it encounters might not be the shortest path between two nodes:
Visualization
simple matrix DFS traversal
0 / 19
To find the shortest path using DFS, we would have to explore all possible paths and then compare the lengths of each path to find the shortest one at the end. This makes BFS a better choice for any question that involves finding the shortest path between two nodes in a graph.
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.