Learn
So far, we are able to traverse the entirety of the graph. However, there will be a problem if the graph has a cycle.
If there was a cycle, for example a path from one vertex to itself, we would be stuck in an infinite loop, continuously iterating over the same neighbors using stack.append(neighbor). To account for this, we can use a where statement in the for-in loop to ensure nodes are not duplicated.
Instructions
1.
Inside the for-in loop iterating over each neighbor, add a where clause checking if visitedNodes already contains the neighbor.
2.
At the bottom of the file, you’ll find a commented-out example of calling the dfs(startingAt:) method in an example graph. Uncomment the code then run it to see what order the nodes are visited in.
Take this course for free
By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.