Breadth-First Search (BFS) & Depth-first Search are traversal techniques for navigating all types of Graphs. Highly recommend reading the post on graph data structure patterns, which builds a foundation of how Graph representations appear in most coding interview questions. This post aims to teach you a single template for implementing and applying Breadth-first search on any graph coding interview questions.
We will go over the following three parts in this post:
BFS on Network of Nodes
BFS on a Grid or Matrix
BFS on a Tree (DAG or Directed Acyclic Graph) or Level Order traversal
Breadth-First Search Algorithm
Bread-First Search(BFS) algorithm is about visiting the immediate neighbors of a Node first before navigating to each neighbor's neighbor in the graph and so on. Let's take the Grid and Network of Nodes graph patterns and see how the BFS algorithm traverses them.
Rule of Thumb: When implementing breadth-first search, you will always use a Queue.
BFS on a Network of Nodes
BFS on a Grid or Matrix
As we saw earlier in our graph coding interview patterns post, we might be given a graph represented as a grid or table. Let's see how we can apply breadth-first search to a 2-dimensional grid.
Now that we see two examples of applying BFS to different graph representations, observe the similarity in the steps above. We can build out a generic template for this coding interview pattern.
Level Order Traversal or BFS on a Tree (DAG)
The Tree data structure is just another type of Graph, precisely, a Directed Acyclic Graph (DAG). Breadth-first search can be applied to a DAG or Tree using the same template above. BFS traversal on a tree is also referred to as a Level-Order traversal.
I recommend opening two browser tabs side-by-side and comparing the level order traversal on a tree with the generic graph BFS template. You will notice we have skipped parts related to maintaining a `visited` set of nodes. We don't need to maintain a visited set because Tree is a Directed-Acyclic graph. When we retrieve the current Node (call it A) and then process one of its neighbors(call it B). When we try to find neighbors of B, we will not see A as Node B doesn't point to Node A. This optimizes our space complexity when applying breadth-first search on a tree data structure.
In the next post, we will learn the Depth-First search traversal pattern and create a generic template as we did for the above BFS pattern that can be applied to any graph.