Week 4: Breadth-first Search (BFS)

Breadth-first Search (BFS) appears in interviews a lot. If an interview question is about graph, 99% of the times it is testing you BFS. It is very simple and versatile, just like binary search, so it is worthy to spend some time and tackle it down. BFS can be used in tree traversal and finding the shortest path in an undirected graph. It uses a queue to keep track on elements that are waiting for search. In Python, we use collections.deque to realize this functionality. 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s