Swift Algorithm Club: Swift Breadth First Search

Finding the Way Back

You’re almost done!

At this point, you know that if the destination can’t be found, you’ll return nil. But if you do find the destination, you need to find your way back. Unfortunately, every room you’ve visited, you’ve also dequeued, leaving no record of how you found the destination!

To keep a record of your exploration, you’re going to replace your set of explored vertices with a dictionary, containing all your explored vertices and how you got there. Think of it as exploring a maze, and leaving a chalk arrow pointing towards all the rooms you explored – and when you come back to a room, following the directions the arrows are pointing from, to get back to the entrance.

If we kept track of all the arrows we drew, for any room we’ve visited, we can just look up the edge we took to get to it. That edge will lead back to a room we visited earlier, and we can look up the edge we took to get there as well, and so on back to the beginning.

Let’s try this out, starting by creating the following Visit enum type. You’ll have to create this outside the Graphable extension, because Swift 3 doesn’t allow nested generic types.

enum Visit<Element: Hashable> {
  case source
  case edge(Edge<Element>)
}

We’re being clear and Swifty here. In our look-up table, every item in the first column was a Vertex, but not every item in the second column is an Edge; one Vertex will always be the source vertex. If not, something has gone badly wrong and we’ll never get out of the graph!

Next modify your method as follows:

public func breadthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>) -> [Edge<Element>]? {
  var queue = Queue<Vertex<Element>>()
  queue.enqueue(source)
  var visits : [Vertex<Element> : Visit<Element>] = [source: .source] // 1

  while let visitedVertex = queue.dequeue() {
    // TODO: Replace this...
    if visitedVertex == destination {
     return []
    }
    let neighbourEdges = edges(from: visitedVertex) ?? []
    for edge in neighbourEdges {
      if visits[edge.destination] == nil { // 2
        queue.enqueue(edge.destination)
        visits[edge.destination] = .edge(edge) // 3
      }
    }
  }
  return nil
}

Let’s review what’s changed here:

1. This creates a Dictionary of Vertex keys and Visit values, and initializes it with the source vertex as a ‘source’ visit.
2. If the Dictionary has no entry for a vertex, then it hasn’t been enqueued yet.
3. Whenever you enqueue a vertex, you don’t just put the vertex into a set, you record the edge you took to reach it.

Finally, you can backtrack from the destination to the entrance! Update that if-statement with the TODO to this:

if visitedVertex == destination {
  var vertex = destination // 1
  var route: [Edge<Element>] = [] // 2

  while let visit = visits[vertex],
    case .edge(let edge) = visit { // 3

    route = [edge] + route
    vertex = edge.source // 4

  }
  return route // 5
}

Let’s review this section by section:

1. You created a new variable, to store each vertex which is part of the route.
2. You also created a variable to store your route.
3. You created a while-loop, which will continue as long as the visits Dictionary has an entry for the vertex, and as long as that entry is an edge. If the entry is a source, then the while-loop will end.
4. You added that edge to the start of your route, and set the vertex to that edge’s source. You’re now one step closer to the beginning.
5. The while-loop has ended, so your route must now be complete.

That’s it! You can test this out by adding the following to the end of your playground:

if let edges = dungeon.breadthFirstSearch(from: entranceRoom, to: treasureRoom) {
  for edge in edges {
    print("\(edge.source) -> \(edge.destination)")
  }
}

You should see the following print out in your console:

Entrance -> Rat
Rat -> Treasure

Where To Go From Here?

I hope you enjoyed this tutorial on the Swift breadth first search algorithm!

You’ve extended the behavior of all Graphable data types, so you can search for a route from any vertex to any other vertex. Better still, you know it’s a route with the shortest number of steps.

Here is a playground with the above code. You can also find the original implementation and further discussion in the breadth first search section of the Swift Algorithm Club repository.

This was just one of the many algorithms in the Swift Algorithm Club repository. If you’re interested in more, check out the repo.

It’s in your best interest to know about algorithms and data structures – they’re solutions to many real world problems, and are frequently asked as interview questions. Plus it’s fun!

So stay tuned for many more tutorials from the Swift Algorithm club in the future. In the meantime, if you have any questions on implementing breadth first search in Swift, please join the forum 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.