What is Breadth First Search?
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.
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 thevisited
list. - Finally, it loops through all the
neighbors
and appends the neighbor to thequeue
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
}