Swift Algorithm Club: Swift Breadth First Search

The Swift Algorithm Club is an open source project to implement popular algorithms and data structures in Swift.

Every month, the SAC team will feature a cool data structure or algorithm from the club in a tutorial on this site. If your want to learn more about algorithms and data structures, follow along with us!

In this tutorial, you’ll walk through a classic of search and pathfinding algorithms, the breadth first search.

This algorithm was first implemented by Chris Pilcher, and is now refactored for tutorial format.

This tutorial assumes you have read our Swift Graphs with Adjacency Lists and Swift Queue tutorials, or have equivalent knowledge.

Getting Started

In our tutorial on Swift Graphs with Adjacency Lists, we presented the idea of a graph as a way of expressing objects and the relationships between them. In a graph, each object is represented as a vertex, and each relationship is represented as an edge.

For example, a maze could be represented by a graph. Every junction in the maze can be represented by a vertex, and every passageway between junctions could be represented by an edge.

Breadth first search was discovered in the 1950’s by E. F. Moore, as an algorithm not just for finding a path through a maze, but for finding the shortest path through that maze. The idea behind breadth first search is simple:

1. Explore every single location within a set number of moves of the origin.
2. Then, incrementally increase that number until the destination is found.

Let’s take a look at an example.

An Example

Assume you are at the entrance to a maze.

The breadth first search algorithm works as follows:

1. Search your current location. If this is the destination, stop searching.



2. Search the neighbors of your location. If any of them are the destination, stop searching.



3. Search all the neighbors of those locations. If any of them are the destination, stop searching.



4. Eventually, if there is a route to the destination, you will find it, and always in the fewest number of moves from the origin. If you ever run out of locations to search, you know that the destination cannot be reached.

Note: As far as the Breadth First Search algorithm is concerned, the shortest route means the fewest number of moves, from one location to the next.

In our maze example, the Breadth First Search algorithm treats all the passageways between rooms in the maze as if they were the same length, even though this might not be true. Think of the shortest route as being the shortest list of directions through the maze, rather than the shortest distance

We’ll explore path-finding algorithms for the shortest distance in future tutorials.

Swift Breadth First Search

Let’s see what the breadth first search algorithm looks like in Swift.

Start by downloading the starter Playground for this tutorial, which has the data structures for a Swift adjacency list and Swift Queue included.

To recap, we defined a Graphable protocol which all graph data structures could conform to. We’re going to be extending that protocol, so we can add the breadth first search to all graphable types.

Here’s what the Graphable protocol looks like at the moment:

public protocol Graphable {
  associatedtype Element: Hashable
  var description: CustomStringConvertible { get }
  
  func createVertex(data: Element) -> Vertex<Element>
  func add(_ type: EdgeType, from source: Vertex<Element>, to destination: Vertex<Element>, weight: Double?)
  func weight(from source: Vertex<Element>, to destination: Vertex<Element>) -> Double?
  func edges(from source: Vertex<Element>) -> [Edge<Element>]?
}

At the top of your playground (right after import XCPlayground), let’s start by creating our extension:

extension Graphable {
  public func breadthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>) 
  -> [Edge<Element>]? {

  }
}

Let’s review this function signature:

• You’ve just declared a function which takes two vertices – the source, our starting point, and the destination, our goal – and returns a route in edges which will take you from the source to the destination.
• If the route exists, you expect it to be sorted! The first edge in the route will start from the source vertex, and the last edge in the route will finish at the destination vertex. For every pair of adjacent edges in the route, the destination of the first edge will be the same vertex as the source of the second edge.
• If the source is the destination, the route will be an empty array.
• If the route doesn’t exist, the function should return nil.

Breadth first search relies on visiting the vertices in the correct order. The first vertex to visit will always be the source. After that we’ll explore the source vertex’s neighbors, then their neighbors and so on. Every time we visit a vertex, we add its neighbors to the back of the queue.

We’ve encountered Queues before, so here’s an excellent opportunity to use one!

Update your function to this:

public func breadthFirstSearch(from source: Vertex<Element>, to destination: Vertex<Element>) 
 -> [Edge<Element>]? {

  var queue = Queue<Vertex<Element>>()
  queue.enqueue(source) // 1

  while let visitedVertex = queue.dequeue() { // 2
    if visitedVertex == destination { // 3
      return []
    }
    // TODO...
  }
  return nil // 4

}

Let’s review this section by section:

This dequeues a vertex from the queue (as long as the queue isn’t empty) and calls it the visited vertex.

In the first iteration, the visited vertex will be the source vertex and the queue will immediately be empty. However, if visiting the source vertex adds more vertices to the loop, the search will continue.

1. This creates a queue for vertices, and enqueues the source vertex.

2. This dequeues a vertex from the queue (as long as the queue isn’t empty) and calls it the visited vertex.

   In the first iteration, the visited vertex will be the source vertex and the queue will immediately be empty. However, if visiting the source vertex adds more vertices to the loop, the search will continue.

3. This checks whether the visited vertex is the destination. If it is, the search ends immediately. For now you return an empty list, which is the same as saying the destination was found. Later you’ll compose a more detailed route.
4. If the queue runs out of vertices, you return nil. This means the destination wasn’t found, and no route to it is possible.

We now need to enqueue the visited vertex’s neighbors. Replace the TODO with the following code:

let neighbourEdges = edges(from: visitedVertex) ?? [] // 1
for edge in neighbourEdges {
  queue.enqueue(edge.destination)
} // 2

Let’s review this section by section:

This uses the Graphable protocol’s edges(from:) method to get the array of edges from the visited vertex. Remember that the edges(from:) function returns an optional array of edges. This means if the array is empty, or nil, then there are no edges beginning with that vertex.

Because, for the purposes of our search, the empty list and nil mean the same thing – no neighbors to add to the queue – we’ll nil-coalesce the optional array with the empty list to remove the optional.

1. This uses the Graphable protocol’s edges(from:) method to get the array of edges from the visited vertex. Remember that the edges(from:) function returns an optional array of edges. This means if the array is empty, or nil, then there are no edges beginning with that vertex.

   Because, for the purposes of our search, the empty list and nil mean the same thing – no neighbors to add to the queue – we’ll nil-coalesce the optional array with the empty list to remove the optional.

2. You can now safely use a for-loop with the list of edges, to enqueue each edge’s destination vertex.

We’re not quite done here yet. There’s a subtle danger in this search algorithm! What problem would you run into if you ran the search algorithm on this example? Ignore the fact that the treasure room isn’t connected to the graph.

Work out what happens every time we visit a vertex with pen and paper, if that helps.

[spoiler title=”What problem would you run into if you ran the search algorithm on this example?”]

1. The breadth first search function creates a queue, and enqueues the entrance room.
2. The first time we go through the while loop, we dequeue the entrance room and visit it. The entrance room doesn’t have the treasure, so we explore the entrance room’s neighbors. The entrance room has one neighbor, the spider room, so we enqueue that.
3. The second time we go through the while loop, we dequeue the spider room and visit it. The spider room doesn’t have the treasure, so we explore the spider room’s neighbors. The spider room has one neighbor, the entrance room, so we enqueue that.
4. The third time we go through the while loop, we dequeue the entrance room…

The problem is: we’ve been here before!

To fix this problem, We need to remember the vertices we visit so we don’t visit them more than once.
[/spoiler]

There are several ways to do this. Update your code to this:

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

  while let visitedVertex = queue.dequeue() {
    if visitedVertex == destination {
      return []
    }
   let neighbourEdges = edges(from: visitedVertex) ?? []
    for edge in neighbourEdges {
      if !enqueuedVertices.contains(edge.destination) { // 2
        enqueuedVertices.insert(visitedVertex) // 3
        queue.enqueue(edge.destination)
      }
    }
  }
  return nil
}

Let’s review what’s changed:

1. This creates a set of vertices, to represent the list of vertices you’ve encountered so far. Remember that the Vertex type is Hashable, so we don’t need to do any more work than this to make a set of vertices.
2. Whenever you examine a neighboring vertex, you first check to see if you’ve encountered it so far.
3. If you haven’t encountered it before, you add it to both queues: the list of “vertices to process” (queue) and the list of “vertices encountered” (enqueuedVertices).

This means the search is considerably safer. You now can’t visit more vertices than are in the graph to begin with, so the search must eventually terminate.