Now it’s time to focus on breadth-first traversal! As a reminder, the breadth-first traversal iterates through the graph in layers. It goes down one layer, which comprises of the start node’s direct neighbors. Then it proceeds down to the next layer, which consists of all the nodes that are neighbors of the nodes in the previous layer.
Instead of using a
stack to iterate through the nodes, we will use a queue to traverse through the graph. Queues have are first-in first-out (FIFO). This is the appropriate data structure here because all of a node’s neighbors will be visited before moving on. The workspace includes the Queue implementation from an earlier lesson. Note that the function is almost exactly identical to the dfs(startingAt:) method, except that it uses a queue instead of a stack.
Create a new function
bfs(startingAt:) with an argument label of
startingAt and parameter name
startNode of type
GraphNode. The function should return an array of
GraphNodes. For now, return an empty array so that the code compiles.
Next, create a variable
queue and assign it to a
startNode to the beginning of the
Create a variable
visitedNodes and assign it to an empty array of
visitedNodes represents the nodes we already visited.
while let loop that iterates while the
queue is not empty, and assigns the optional returned from
dequeue() to a constant named
while loop, if
visitedNodes does not contain the
We’ll also want to add all of the
currentNode‘s neighbors to the stack. Create a
for-in loop that iterates through the
currentNode neighbors and enqueues them. This ensures that we will traverse through each layer of the graph.
Finally, return the visited nodes in the last line of the function instead of the empty array that you added in the first checkpoint.