iOS Interview - Breadth-First Search

April 13, 2024 • 5 min read • #swift, #interview, #leetcode

Breadth-First Search (BFS) is a popular graph traversal algorithm used in computer science. It is a method for searching a tree or graph data structure for a node that satisfies a given property. BFS explores all the neighbors of a node at the present depth level before moving on to the nodes at the next depth level. This means it explores levels of the graph layer by layer.

How BFS Works:

Start with a given source node.
Mark the source node as visited.
Create a queue, and enqueue the source node into it.
While the queue is not empty: a. Dequeue a node from the front of the queue. b. Process the dequeued node. c. Enumerate the neighbors of the dequeued node. d. For each neighbor:
- If the neighbor node has not been visited:
  - Mark it as visited.
  - Enqueue the neighbor node into the queue.
The BFS traversal is complete when the queue becomes empty.

BFS can be used to solve various problems, such as finding the shortest path between two nodes, connectivity checks, or reaching a particular node from the source node.

Example: Finding the Shortest Distance in a Unweighted Graph

Let’s implement the Breadth-First Search algorithm using Swift. First, we’ll create a simple Graph structure to represent our graph:

struct Graph {
    var adjList: [Int: [Int]]

    init() {
        self.adjList = [:]
    }

    mutating func addEdge(_ v1: Int, _ v2: Int) {
        if adjList[v1] == nil {
            adjList[v1] = []
        }
        if adjList[v2] == nil {
            adjList[v2] = []
        }

        adjList[v1]?.append(v2)
        adjList[v2]?.append(v1)
    }
}

Now that we have our Graph structure, let’s implement the Breadth-First Search algorithm:

func bfs(graph: Graph, start: Int) {
    var visited = Set<Int>()
    var queue = [Int]()

    visited.insert(start)
    queue.append(start)

    while !queue.isEmpty {
        let currentNode = queue.removeFirst()
        print("Visited: \(currentNode)")

        if let neighbors = graph.adjList[currentNode] {
            for neighbor in neighbors {
                if !visited.contains(neighbor) {
                    visited.insert(neighbor)
                    queue.append(neighbor)
                }
            }
        }
    }
}

Finally, let’s create a sample graph and perform a Breadth-First Search on it:

var graph = Graph()
graph.addEdge(1, 2)
graph.addEdge(1, 3)
graph.addEdge(2, 4)
graph.addEdge(2, 5)
graph.addEdge(3, 6)
graph.addEdge(3, 7)

bfs(graph: graph, start: 1)

Output:

Visited: 1
Visited: 2
Visited: 3
Visited: 4
Visited: 5
Visited: 6
Visited: 7

Problems:

102. Binary Tree Level Order Traversal

Leetcode: 102. Binary Tree Level Order Traversal

class TreeNode {
  var val: Int
  var left: TreeNode?
  var right: TreeNode?
  init(_ val: Int) {
    self.val = val
    self.left = nil
    self.right = nil
  }
}

// Time complexity = O(n) since each node is processed exactly once.
// Space complexity = O(n) to keep the output structure which contains n node values
func levelOrder(_ root: TreeNode?) -> [[Int]] {
    // Ensure the tree is not empty
    guard let root = root else {
      return []
    }

    var output = [[Int]]()

    // Initialise the queue and add the root node into the queue for processing
    var queue = [TreeNode]()
    queue.append(root)

    // iterate over the queue, process nodes inside the queue until the queue is empty
    while queue.isEmpty == false {
      // start new level
      // number of elements in the current level
      var levelNodeCount = queue.count
      var levelNodes = [Int]()

      // Process all nodes in the current level
      for _ in 0..<queue.count {
        // Retrieve and Remove the first-in node from the queue
        let node = queue.removeFirst()

        // Add this node into the array holding nodes for the current level
        levelNodes.append(node.val)

        // Add Left child node into the queue for the next processing iteration
        if let left = node.left{
            queue.append(left)
        }
        // Add right child node into the queue for the next processing iteration
        if let right = node.right{
          queue.append(right)
        }
      }

      // Add nodes by level
      output.append(levelNodes)
    }
    return output
}

let root2 = TreeNode(1)
let node22 = TreeNode(2)
let node23 = TreeNode(3)
let node24 = TreeNode(4)
let node25 = TreeNode(5)
let node26 = TreeNode(6)
let node27 = TreeNode(7)
root2.left = node22
root2.right = node23
node22.left = node24
node22.right = node25
node23.left = node26
node23.right = node27

print(levelOrder(root2)) // [[1], [2, 3], [4, 5, 6, 7]]

Conclusion:

Breadth-First Search is a powerful algorithm for traversing graphs and solving various problems related to graph connectivity and shortest paths. It provides a systematic way to explore a graph layer by layer, making it an essential tool in computer science and algorithm design.