Learn

So far, we are able to traverse the entirety of the graph. However, just like for our depth-first traversal, there will be a problem if the graph has a cycle.

If a graph contains a cycle, we would get stuck in an infinite loop, continuously iterating over the same neighbors with queue.enqueue(neighbor). To account for this, we can use a where statement in the for-in loop to ensure that we don’t enqueue nodes that we’ve already visited.

Instructions

1.

Inside the for-in loop iterating over each neighbor, add a where clause checking if visitedNodes already contains the neighbor.

2.

At the bottom of the file, you’ll find a commented-out example of calling the bfs(startingAt:) method in an example graph. Uncomment the code then run it to see what order the nodes are visited in.

Take this course for free

Mini Info Outline Icon
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.

Or sign up using:

Already have an account?