This lesson's interactive features are locked, please to keep using them

Breadth First Search (BFS)

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at a root (some arbitrary node on a graph), and explores all of the neighbor nodes at the present depth before going on to the nodes at the next level.

Click to play video

Try stepping through a small graph:

Stable Sorting

Non-integer sets are not "stable" in Python - the order of elements in a set is not guaranteed to be the same each time you iterate over it.

While testing, we want our algorithm to search the same way every time to make debugging easier. Python offers a sorted() function we can call on our set() that will return a sorted iterable.

sorted_items = sorted(unsorted_set)

Assignment

Graphs are useful at LockedIn for more than just representing social connections! We'll also use it to build our geographic search feature. We have a graph of cities, where each city is a vertex, and each road connecting two cities is an edge.

Complete the breadth_first_search method on the Graph class.

This method traverses a graph level by level starting from a specified vertex v, and returns all vertices in the order they were visited. The breadth-first approach ensures we explore all vertices at the current distance from the start before moving further away.

Initialize tracking structures:
- Create a list to track visited vertices
- Create a list to use as a queue for vertices waiting to be explored
Begin the search:
- Add the starting vertex v to the queue
Process the queue until empty:
- Remove the first vertex from the queue and add it to the visited list
- Get a sorted list of this vertex's neighbors
- For each neighbor, if it is neither visited nor queued, add it to the queue
When complete, return the visited list containing vertices in the order they were discovered

We're using unique strings now as our vertices, rather than integers