Learn

Welcome back to the Graph data structure! In this lesson, we’ll implement graph searching algorithms, also known as traversals.

Traversals are incredibly useful when you are trying to find a particular value or a path in a graph. We’ll first explore the depth-first traversal method for traversing through an acyclic graph. To recap, depth-first traversals iterate down each vertex, one neighbor at a time, before going back up and looking at the neighbor’s connected nodes. In this exercise, we will focus on traversing down the full length of one path and printing each node’s data value.

We’ll be using the Graph structures and classes defined in the Graphs lesson.

Instructions

1.

Create a new function dfs(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 stack and assign it to an array containing startNode. The stack represents the order of nodes to visit.

3.

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

4.

Add a while let loop that iterates while the stack is not empty and assigns the optional returned from popLast to a constant named currentNode.

5.

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

6.

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 appends them to the stack. This ensures that we will traverse through each depth of the graph.

7.

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

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?