Breadth First Search

 

There are plenty of sources online that describe a Breadth First Search on an unweighted graph. I wanted to highlight 2 key components of the BFS algorithm in this post

• Tracking Neighbors
• Tracking Visited

Tracking Neighbors

During the traversal of a graph, we need to ensure that we don't lose track of the nodes that we have yet to process.

A Queue ensures that all elements that were added first get processed first. And this makes this an ideal data structure to ensure that we process all neighbor nodes first - "breadth first"

Tracking Visited

We also want to ensure that a node isn't processed more than once. This is easy to keep track in a map , set or array

BFS vs DFS

In a DFS (Depth First Search), the graph traversal will be biased towards processing all child elements of a neighbor node before getting to the other neighbors.

A Stack (LIFO) ensures that recently added elements are processed first. This makes it ideal to use in a DFS algorithm when tracking nodes. A stack will ensure that we process all child elements of a neighbor first - "depth first"