Breadth-first search (BFS) is an algorithm for traversing tree or graph data structures. It starts at the root and explores all the neighboring nodes at the current depth before moving on to nodes at the next depth level.


Source

Implementation

The implementation of BFS may vary depending on the problem. The main idea of BFS is:

  • It has a visited array that collects all elements that have already been visited.
  • It has a queue with all elements it’s going to visit.
  • It loops through the queue, removes the first element, and appends it to the visited list.
  • Finally, it loops through all the neighbors and appends the neighbor to the queue if it has not been visited and is not already in the queue.

Code Example

func bfs(_ value: String) -> [String] {
    let graph: [String: [String]] = [
        "New York": ["Buenos Aires", "Cairo", "Tokyo", "London"]
    ]

    var visited: [String] = []
    var queue: [String] = []

    queue.append(value)

    while !queue.isEmpty {
        let tmp = queue.removeFirst()
        visited.append(tmp)
        
        if let neighbors = graph[tmp] {
            for neighbor in neighbors.sorted() {
                if !visited.contains(neighbor) && !queue.contains(neighbor) {
                    queue.append(neighbor)
                }
            }
        }
    }

    return visited
}

Thank you for reading! 😊