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.
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.
Next, create a variable
stack and assign it to an array containing
stack represents the order of nodes to visit.
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
stack is not empty and assigns the optional returned from
popLast 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 appends them to the stack. This ensures that we will traverse through each depth 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.