Breadth First Search Fast AF

4 min readDec 20, 2022

Breadth first search (BFS) is an algorithm that is commonly used to explore a graph or tree structure. It is an efficient way to traverse a large data structure and find a specific node or group of nodes. In this tutorial, we will be implementing BFS in Swift and discussing how it works.

Before we start, let’s define some terms that we will be using throughout this tutorial:

Node: A node is a data point in a graph or tree structure.
Edge: An edge is a connection between two nodes in a graph or tree structure.
Adjacency list: An adjacency list is a data structure that represents a graph or tree as a list of nodes and their adjacent nodes.

To implement BFS in Swift, we will start by defining a class for our graph. This class will have a property called adjacencyList that is a dictionary where the keys are the nodes in the graph and the values are arrays of their adjacent nodes.

class Graph {
  var adjacencyList: [Int: [Int]] = [:]
}

Next, we will define a function called addEdge that will add an edge between two nodes in our graph. This function will take in two integers, fromNode and toNode, and add toNode to the array of adjacent nodes for fromNode.

class Graph {
  var adjacencyList: [Int: [Int]] = [:]
  
  func addEdge(fromNode: Int, toNode: Int) {
    adjacencyList[fromNode, default: []].append(toNode)
  }
}

Now that we have our graph set up, we can start implementing the BFS algorithm. We will define a function called breadthFirstSearch that takes in a startNode and a goalNode. This function will return a boolean indicating whether the goalNode can be reached from the startNode.

The first step in BFS is to create a queue and add the startNode to it. The queue will be used to keep track of which nodes need to be visited.

class Graph {
  var adjacencyList: [Int: [Int]] = [:]
  
  func addEdge(fromNode: Int, toNode: Int) {
    adjacencyList[fromNode, default: []].append(toNode)
  }
  
  func breadthFirstSearch(startNode: Int, goalNode: Int) -> Bool {
    var queue = [startNode]
  }
}

Next, we will create a visited set to keep track of which nodes have already been visited. This will help us avoid getting stuck in a loop if there are any cycles in the graph.

class Graph {
  var adjacencyList: [Int: [Int]] = [:]
  
  func addEdge(fromNode: Int, toNode: Int) {
    adjacencyList[fromNode, default: []].append(toNode)
  }
  
  func breadthFirstSearch(startNode: Int, goalNode: Int) -> Bool {
    var queue = [startNode]
    var visited: Set<Int> = []
  }
}

Now we can start the main loop of the BFS algorithm. We will continue looping as long as the queue is not empty. Inside the loop, we will take the first element from the queue and add it to the visited set. Then, we will check if the current node is the goalNode. If it is, we will return true to indicate that the goalNode can be reached from the startNode.

class Graph {
  var adjacencyList: [Int: [Int]] = [:]
  
  func addEdge(fromNode: Int, toNode: Int) {
    adjacencyList[fromNode, default: []].append(toNode)
  }
  
  func breadthFirstSearch(startNode: Int, goalNode: Int) -> Bool {
    var queue = [startNode]
    var visited: Set<Int> = []
    
    while !queue.isEmpty {
      let currentNode = queue.removeFirst()
      visited.insert(currentNode)
      
      if currentNode == goalNode {
        return true
      }
    }
    
    return false
  }
}

If the goalNode has not been found, we will add all of the adjacent nodes of the current node to the queue. This ensures that we are exploring all possible paths from the startNode before moving on to the next node.

class Graph {
  var adjacencyList: [Int: [Int]] = [:]
  
  func addEdge(fromNode: Int, toNode: Int) {
    adjacencyList[fromNode, default: []].append(toNode)
  }
  
  func breadthFirstSearch(startNode: Int, goalNode: Int) -> Bool {
    var queue = [startNode]
    var visited: Set<Int> = []
    
    while !queue.isEmpty {
      let currentNode = queue.removeFirst()
      visited.insert(currentNode)
      
      if currentNode == goalNode {
        return true
      }
      
      for node in adjacencyList[currentNode, default: []] {
        if !visited.contains(node) {
          queue.append(node)
        }
      }
    }
    
    return false
  }
}

Now that we have our BFS algorithm implemented, let’s test it out with an example graph. We will create a graph with 5 nodes and add edges between them. Then, we will run the breadthFirstSearch function to see if we can reach the goalNode from the startNode.

let graph = Graph()

graph.addEdge(fromNode: 1, toNode: 2)
graph.addEdge(fromNode: 1, toNode: 3)
graph.addEdge(fromNode: 2, toNode: 4)
graph.addEdge(fromNode: 3, toNode: 5)

let startNode = 1
let goalNode = 5

if graph.breadthFirstSearch(startNode: startNode, goalNode: goalNode) {
  print("The goal node can be reached from the start node.")
} else {
  print("The goal node cannot be reached from the start node.")
}

The output of this code should be “The goal node can be reached from the start node.” This is because there is a path from the startNode to the goalNode in our graph.

BFS is a useful algorithm for exploring a graph or tree structure and finding a specific node or group of nodes. It is an efficient way to traverse a large data structure and is often used in problems such as finding the shortest path in a maze or determining the reachability of nodes in a graph.

If you want to learn more about BFS and other graph traversal algorithms, you can check out the following resources:

I hope this tutorial was helpful in understanding how to implement BFS in Swift and how it works. If you have any questions or suggestions, feel free to leave a comment below.

Breadth First Search Fast AF

Written by Swift Fast AF