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
Inside the for-in
loop iterating over each neighbor, add a where
clause checking if visitedNodes
already contains the neighbor.
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.