Breadth-First Search, or BFS, is a key algorithm used to traverse graphs or tree-like structures. Unlike Depth-First Search, which explores deeply before backtracking, BFS explores all neighbors of a node before moving to the next level. This makes BFS especially useful in finding the shortest path in unweighted graphs, level order traversal, and exploring networks. Understanding BFS gives beginners a strong foundation in graph theory and helps develop skills for practical applications like routing, puzzle solving, and social network analysis.
with hands-on learning.
get the skills and confidence to land your next move.
Implementing BFS in Scala is straightforward, and it teaches beginners how to use queues, track visited nodes, and handle graph traversal iteratively. Practicing BFS also helps in visualizing how graphs are explored layer by layer, making it easier to solve problems in coding interviews and real-world applications.
Program 1: BFS Using a Queue on an Adjacency List
This program demonstrates the classic BFS approach using a queue on a simple integer-labeled graph.
import scala.collection.mutable
object BFSQueue {
def bfs(start: Int, graph: Map[Int, List[Int]]): Unit = {
val visited = mutable.Set[Int]()
val queue = mutable.Queue[Int]()
queue.enqueue(start)
visited += start
while (queue.nonEmpty) {
val node = queue.dequeue()
println(node)
for (neighbor <- graph.getOrElse(node, Nil)) {
if (!visited.contains(neighbor)) {
queue.enqueue(neighbor)
visited += neighbor
}
}
}
}
def main(args: Array[String]): Unit = {
val graph = Map(
0 -> List(1, 2),
1 -> List(0, 3, 4),
2 -> List(0, 5),
3 -> List(1),
4 -> List(1, 5),
5 -> List(2, 4)
)
println("BFS traversal starting from node 0:")
bfs(0, graph)
}
}This BFS uses a queue to explore nodes level by level. Beginners can see how the queue keeps track of nodes to visit next while the visited set prevents revisiting nodes, which is essential in graphs with cycles.
Program 2: BFS on a Graph with String Nodes
BFS is flexible and works on graphs with string-labeled nodes as well. This program shows BFS traversal on a graph with letters.
import scala.collection.mutable
object BFSStringNodes {
def bfs(start: String, graph: Map[String, List[String]]): Unit = {
val visited = mutable.Set[String]()
val queue = mutable.Queue[String]()
queue.enqueue(start)
visited += start
while (queue.nonEmpty) {
val node = queue.dequeue()
println(node)
for (neighbor <- graph.getOrElse(node, Nil)) {
if (!visited.contains(neighbor)) {
queue.enqueue(neighbor)
visited += neighbor
}
}
}
}
def main(args: Array[String]): Unit = {
val graph = Map(
"A" -> List("B", "C"),
"B" -> List("A", "D", "E"),
"C" -> List("A", "F"),
"D" -> List("B"),
"E" -> List("B", "F"),
"F" -> List("C", "E")
)
println("BFS traversal starting from node A:")
bfs("A", graph)
}
}Using strings demonstrates BFS’s versatility. Beginners learn how the algorithm adapts to different types of data while maintaining the same traversal logic.
Program 3: BFS for Shortest Path in an Unweighted Graph
BFS can find the shortest path between two nodes in an unweighted graph. This example tracks the distance from the start node.
import scala.collection.mutable
object BFSShortestPath {
def bfsShortestPath(start: Int, end: Int, graph: Map[Int, List[Int]]): Int = {
val visited = mutable.Set[Int]()
val queue = mutable.Queue[(Int, Int)]()
queue.enqueue((start, 0))
visited += start
while (queue.nonEmpty) {
val (node, distance) = queue.dequeue()
if (node == end) return distance
for (neighbor <- graph.getOrElse(node, Nil)) {
if (!visited.contains(neighbor)) {
queue.enqueue((neighbor, distance + 1))
visited += neighbor
}
}
}
-1 // Path not found
}
def main(args: Array[String]): Unit = {
val graph = Map(
0 -> List(1, 2),
1 -> List(0, 3, 4),
2 -> List(0, 5),
3 -> List(1),
4 -> List(1, 5),
5 -> List(2, 4)
)
val distance = bfsShortestPath(0, 5, graph)
println(s"Shortest path from 0 to 5 is: $distance")
}
}This program illustrates a practical application of BFS. Beginners see how BFS explores nodes systematically and keeps track of distances, making it ideal for shortest path problems in unweighted graphs.
Program 4: BFS on a Grid (2D Matrix)
BFS can explore grids, such as finding connected components or spreading waves. This example visits all connected cells with value 1.
import scala.collection.mutable
object BFSGrid {
def bfs(grid: Array[Array[Int]], startRow: Int, startCol: Int): Unit = {
val visited = Array.ofDim[Boolean](grid.length, grid(0).length)
val queue = mutable.Queue[(Int, Int)]()
val directions = List((0,1), (0,-1), (1,0), (-1,0))
queue.enqueue((startRow, startCol))
visited(startRow)(startCol) = true
while (queue.nonEmpty) {
val (row, col) = queue.dequeue()
println(s"Visited cell ($row, $col)")
for ((dr, dc) <- directions) {
val r = row + dr
val c = col + dc
if (r >= 0 && c >= 0 && r < grid.length && c < grid(0).length && grid(r)(c) == 1 && !visited(r)(c)) {
queue.enqueue((r, c))
visited(r)(c) = true
}
}
}
}
def main(args: Array[String]): Unit = {
val grid = Array(
Array(1, 1, 0),
Array(0, 1, 1),
Array(1, 0, 1)
)
println("BFS traversal on grid starting from cell (0,0):")
bfs(grid, 0, 0)
}
}Exploring grids with BFS helps beginners understand practical applications such as maze solving, flood fill algorithms, and island counting problems.
Program 5: BFS for Level Order Traversal in a Binary Tree
BFS can traverse trees level by level. This example demonstrates BFS on a binary tree.
import scala.collection.mutable
case class TreeNode(value: Int, left: TreeNode = null, right: TreeNode = null)
object BFSBinaryTree {
def levelOrder(root: TreeNode): Unit = {
if (root == null) return
val queue = mutable.Queue[TreeNode]()
queue.enqueue(root)
while (queue.nonEmpty) {
val node = queue.dequeue()
println(node.value)
if (node.left != null) queue.enqueue(node.left)
if (node.right != null) queue.enqueue(node.right)
}
}
def main(args: Array[String]): Unit = {
val root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
println("Level order traversal of binary tree:")
levelOrder(root)
}
}BFS is the standard method for level order traversal in trees. Beginners can see how BFS can be applied to tree structures, not just general graphs.
Frequently Asked Questions (FAQ)
This section answers common beginner questions about Breadth-First Search in Scala.
Q1: What is BFS used for?
BFS is used for graph traversal, finding shortest paths in unweighted graphs, level order traversal in trees, and exploring grids.
Q2: Can BFS handle both directed and undirected graphs?
Yes, BFS works on both, but the traversal behavior and cycle detection may differ slightly.
Q3: Is BFS better than DFS?
It depends on the task. BFS is better for shortest paths and level-wise exploration, while DFS is better for deep traversal and backtracking problems.
Q4: Can BFS be implemented using recursion?
BFS is typically iterative using a queue. Recursive BFS is possible but less common and more complex.
Q5: How does BFS handle visited nodes?
BFS keeps a set or array of visited nodes to prevent revisiting and avoid infinite loops in cyclic graphs.
Conclusion
Breadth-First Search is an essential graph and tree traversal algorithm that explores nodes level by level. In Scala, BFS can be implemented with a queue, and it adapts easily to integers, strings, grids, and tree structures. Practicing BFS helps beginners understand graph traversal, shortest path finding, and level-wise exploration. By experimenting with different BFS implementations, learners build confidence in solving real-world problems and coding challenges efficiently.
