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.
- If the neighbor node has not been visited:
- 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.
Further Reading: