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
Inside the for-in
loop iterating over each neighbor, add a where
clause checking if visitedNodes
already contains the neighbor.
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.