You'll need to log in from a computer to start Introduction to Non-linear Data Structures in Swift. But you can practice or keep up your coding streak with the Codecademy Go app. Download the app to get started.

Learn

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.

### Instructions

1.

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.

2.

Next, create a variable queue and assign it to a Queue ofGraphNodes.

3.

Add the startNode to the beginning of the queue.

4.

Create a variable visitedNodes and assign it to an empty array of GraphNodes. visitedNodes represents the nodes we already visited.

5.

Add a while let loop that iterates while the queue is not empty, and assigns the optional returned from dequeue() to a constant named currentNode.

6.

Inside the while loop, if visitedNodes does not contain the currentNode, append currentNode to visitedNodes.

7.

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.

8.

Finally, return the visited nodes in the last line of the function instead of the empty array that you added in the first checkpoint.