Kodeco Forums

Swift Algorithm Club: Depth First Search

🎓 Courses & Articles
1

Learn how to implement the depth-first search algorithm in Swift, in this step by step tutorial with downloadable sample code.

This is a companion discussion topic for the original entry at https://www.raywenderlich.com/661-swift-algorithm-club-swift-depth-first-search
2

This tutorial is great! The visuals really help explain the different between Deepth-first and Breadth-First Search.

I did notice that you pass in the end vertex to this implementation of the algorithm. That does make sense for a simple example, I am not sure this would be an algorithm you would implement in the real world. Obviously it depends on the problem you are trying to solve, but how often will you know the end vertex?

It could make sense to pass in the end vertex if you know what you are looking for in a particular graph. What if you don’t know? I can think of one example of path finding where you may not know where the end is, thus you have to search all possiblilties.

How difficult would it be to implement a depth-first search algorithm without the end vertex? This implement ration would have to have logic to keep track how “deep” it is and return that integer, and the longest path. I imagine the run time of this algorithm might be on the order of n^2. What do you guys think?

3

@sprichard, yes this example is specific to finding a path from vertex A to vertex B. In the case where you don’t know where the end vertex is you would have to traverse the whole graph. The algorithm would try to visit every possible vertex, and backtrack till it can’t anymore.

So for this example, in the outer loop, you simply don’t need to check for the end vertex
outer: while let vertex = stack.peek(), vertex != end {...}

The algorithm would stop once the stack is empty.

As for the time complexity. You traverse every vertex of the graph once. Which would be O(V). Also we are using an adjacency list. Every vertex has a list of edges that we have to traverse. This would be O(E) Overall though it would be O(V+E).

Hope this helps :slight_smile:

4

Alternatively - perhaps you have a graph with a lot of vertices, and one or more of them might satisfy your criteria for an end vertex.

Copy the search function, but with the following two changes to the copy:

  1. Instead of to end: Vertex as an argument, write toVertexSatisfying goalFunction: (Vertex) -> Bool.
  2. In the outer loop’s while condition, replace vertex != end with goalFunction(vertex) != true.

What this means is:

  1. instead of looking for one specific vertex known in advance, the search function now takes as an argument a function which ought to return ‘true’ if the vertex is an acceptable end point, and ‘false’ if it isn’t.
  2. the search function will continue until a vertex is acceptable.
5

Assuming that the algorithm will always traverse the left side first before the right. Depth-first search will start exploring all the vertices on the left-most branch.

Doesn’t this example instead depict an algorithm that traverses the right side first before the left?

1 Like
6

This tutorial is more than six months old so questions are no longer supported at the moment for it. We will update it as soon as possible. Thank you! :]