Challenge: Implement breadth-first search

We'll cover the following

Implement BFS

In this step, you'll finish implementing the doBFS() function, which performs a breadth-first search on a graph and returns an array of objects describing each vertex.

For each vertex vv, the object's distance property should be vertex vv's distance from the source, and the predecessor property should be vertex vv's predecessor on a shortest path from the source. If there is no path from the source to vertex vv, then vv's distance and predecessor should both be null. The source's predecessor should also be null.

In the starter code, the function initializes the distance and predecessor values to null, and then enqueues the source vertex. It is up to you to implement the rest of the algorithm, as described in the pseudocode.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy