Swift Algorithm Club: Swift Depth First Search

4. All edges visited.

print("backtrack from \(vertex)") 
stack.pop()

So what happens if all the edges have been visited? If all the edges from the current vertex has been visited, that means we reached a dead-end. So backtrack and pop it off the stack.

Once the top of the stack contains the end vertex, you have found a path from start to finish!

Finally let’s test out the algorithm. Add the following line at the end of the playground:

print(depthFirstSearch(from: s, to: e, graph: adjacencyList))

This is all you need to implement depth-first search! You should see the following output at the bottom of the playground, displaying the path to the exit:

E
F
D
B
A
S

You think you have depth-first search algorithm nailed down?

Quiz

From vertex S to vertex C using depth-first search. How many backtracked vertices were there?

[spoiler title=”Solution”]
5 vertices backtracked

backtrack from G
backtrack from E
backtrack from F
backtrack from D
backtrack from B

[/spoiler]

Where To Go From Here?

Here is the final playground with all the code for the depth-first search algorithm in Swift.

There’s also a recursive version of depth-first search in the Swift Algorithm Club’s repository. So be sure to check that out!

I hope you enjoyed this tutorial on creating pathfinding algorithms with depth-first search in Swift! There are many applications with graphs and this is just one of them.

So stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions or comments, please join the discussion below.

If you enjoyed what you learned in this tutorial, why not check out our Data Structures and Algorithms in Swift book, available on our store?

In Data Structures and Algorithms in Swift, you’ll learn how to implement the most popular and useful data structures and when and why you should use one particular datastructure or algorithm over another. This set of basic data structures and algorithms will serve as an excellent foundation for building more complex and special-purpose constructs.

As well, the high-level expressiveness of Swift makes it an ideal choice for learning these core concepts without sacrificing performance.

• You’ll start with the fundamental structures of linked lists, queues and stacks, and see how to implement them in a highly Swift-like way.
• Move on to working with various types of trees, including general purpose trees, binary trees, AVL trees, binary search trees and tries.
• Go beyond bubble and insertion sort with better-performing algorithms, including mergesort, radix sort, heap sort and quicksort.
• Learn how to construct directed, non-directed and weighted graphs to represent many real-world models, and traverse graphs and trees efficiently with breadth-first, depth-first, Dijkstra’s and Prim’s algorithms to solve problems such as finding the shortest path or lowest cost in a network.
• And much, much more!

By the end of this book, you’ll have hands-on experience solving common issues with data structures and algorithms — and you’ll be well on your way to developing your own efficient and useful implementations.