When it comes to exploring graphs, trees, or even grid-based structures, one of the most important algorithms to know is Breadth-First Search (BFS). Unlike Depth-First Search (DFS), which dives deep into a branch before backtracking, BFS explores all nodes level by level. This makes it ideal for finding the shortest path between nodes, searching through networks, or traversing data structures where distance or layers matter.
with hands-on learning.
get the skills and confidence to land your next move.
BFS is widely used in computer science and programming because it ensures that all nodes at the same level are visited before moving deeper. It’s particularly helpful in real-world applications like social networks to find connections, in maps to find the shortest route, and in puzzles or games for optimal solutions. Learning BFS in Kotlin not only strengthens your grasp on queues and loops but also provides a foundation for solving many practical problems efficiently.
Program 1: BFS Using Queue on a Graph
This program demonstrates the standard BFS traversal on a graph represented by an adjacency list.
import java.util.LinkedList
import java.util.Queue
fun bfs(graph: Map<Int, List<Int>>, start: Int) {
val visited = mutableSetOf<Int>()
val queue: Queue<Int> = LinkedList()
queue.add(start)
visited.add(start)
while (queue.isNotEmpty()) {
val node = queue.poll()
println(node)
for (neighbor in graph[node] ?: emptyList()) {
if (!visited.contains(neighbor)) {
visited.add(neighbor)
queue.add(neighbor)
}
}
}
}
fun main() {
val graph = mapOf(
0 to listOf(1, 2),
1 to listOf(0, 3, 4),
2 to listOf(0, 4),
3 to listOf(1, 5),
4 to listOf(1, 2, 5),
5 to listOf(3, 4)
)
println("BFS Traversal starting from node 0:")
bfs(graph, 0)
}In this program, a queue ensures that nodes are explored level by level. Beginners can see how BFS systematically visits neighbors, making it ideal for scenarios where the shortest path matters.
Program 2: BFS on a Binary Tree
BFS can also be applied to trees, often referred to as level-order traversal.
import java.util.LinkedList
import java.util.Queue
data class TreeNode(val value: Int, val left: TreeNode? = null, val right: TreeNode? = null)
fun bfsBinaryTree(root: TreeNode?) {
if (root == null) return
val queue: Queue<TreeNode> = LinkedList()
queue.add(root)
while (queue.isNotEmpty()) {
val node = queue.poll()
println(node.value)
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
}
fun main() {
val tree = TreeNode(1,
TreeNode(2, TreeNode(4), TreeNode(5)),
TreeNode(3, TreeNode(6), TreeNode(7))
)
println("BFS Traversal of Binary Tree:")
bfsBinaryTree(tree)
}This program shows how BFS can traverse a tree level by level. For beginners, it highlights how a queue can control the order of processing nodes effectively.
Program 3: BFS for Shortest Path in Unweighted Graph
BFS is useful for finding the shortest distance between nodes in an unweighted graph.
import java.util.LinkedList
import java.util.Queue
fun shortestPath(graph: Map<Int, List<Int>>, start: Int, target: Int): Int {
val visited = mutableSetOf<Int>()
val queue: Queue<Pair<Int, Int>> = LinkedList()
queue.add(Pair(start, 0))
visited.add(start)
while (queue.isNotEmpty()) {
val (node, distance) = queue.poll()
if (node == target) return distance
for (neighbor in graph[node] ?: emptyList()) {
if (!visited.contains(neighbor)) {
visited.add(neighbor)
queue.add(Pair(neighbor, distance + 1))
}
}
}
return -1
}
fun main() {
val graph = mapOf(
0 to listOf(1, 2),
1 to listOf(0, 3, 4),
2 to listOf(0, 4),
3 to listOf(1, 5),
4 to listOf(1, 2, 5),
5 to listOf(3, 4)
)
val distance = shortestPath(graph, 0, 5)
println("Shortest path from 0 to 5: $distance")
}Here, BFS guarantees the shortest path in an unweighted graph by exploring nodes layer by layer. Beginners can see BFS’s practical application in network and routing problems.
Program 4: BFS on a Grid (Maze Traversal)
BFS can also traverse 2D grids or mazes, finding the shortest route from a starting cell.
import java.util.LinkedList
import java.util.Queue
fun bfsGrid(grid: Array<IntArray>, startX: Int, startY: Int) {
val rows = grid.size
val cols = grid[0].size
val visited = Array(rows) { BooleanArray(cols) }
val directions = arrayOf(intArrayOf(1,0), intArrayOf(-1,0), intArrayOf(0,1), intArrayOf(0,-1))
val queue: Queue<Pair<Int, Int>> = LinkedList()
queue.add(Pair(startX, startY))
visited[startX][startY] = true
while (queue.isNotEmpty()) {
val (x, y) = queue.poll()
println("Visiting: ($x, $y)")
for (dir in directions) {
val newX = x + dir[0]
val newY = y + dir[1]
if (newX in 0 until rows && newY in 0 until cols &&
!visited[newX][newY] && grid[newX][newY] == 1) {
visited[newX][newY] = true
queue.add(Pair(newX, newY))
}
}
}
}
fun main() {
val grid = arrayOf(
intArrayOf(1, 1, 0, 0),
intArrayOf(1, 1, 0, 1),
intArrayOf(0, 0, 1, 1),
intArrayOf(0, 1, 1, 0)
)
println("BFS Traversal on Grid:")
bfsGrid(grid, 0, 0)
}This program illustrates BFS exploring connected cells level by level. Beginners can relate it to solving maze or shortest path problems in games or simulations.
Program 5: BFS to Check Connectivity in a Graph
BFS can also be used to check if a graph is fully connected.
import java.util.LinkedList
import java.util.Queue
fun isConnected(graph: Map<Int, List<Int>>, start: Int): Boolean {
val visited = mutableSetOf<Int>()
val queue: Queue<Int> = LinkedList()
queue.add(start)
visited.add(start)
while (queue.isNotEmpty()) {
val node = queue.poll()
for (neighbor in graph[node] ?: emptyList()) {
if (!visited.contains(neighbor)) {
visited.add(neighbor)
queue.add(neighbor)
}
}
}
return visited.size == graph.size
}
fun main() {
val graph = mapOf(
0 to listOf(1, 2),
1 to listOf(0, 3, 4),
2 to listOf(0, 4),
3 to listOf(1, 5),
4 to listOf(1, 2, 5),
5 to listOf(3, 4)
)
println("Graph is connected: ${isConnected(graph, 0)}")
}BFS visits all reachable nodes, making it easy to check whether every node can be accessed from a starting point. Beginners can see BFS applied in practical scenarios like network validation.
Frequently Asked Questions (FAQ)
Q1: What is Breadth-First Search (BFS)?
BFS is a graph traversal algorithm that explores nodes level by level using a queue.
Q2: When should I use BFS?
BFS is useful when you want the shortest path, check connectivity, or explore a graph layer by layer.
Q3: How does BFS differ from DFS?
BFS explores all neighbors first (level by level), while DFS explores as deep as possible before backtracking.
Q4: Can BFS handle weighted graphs?
Standard BFS works for unweighted graphs; for weighted graphs, algorithms like Dijkstra are used.
Q5: What is the time complexity of BFS?
BFS has a time complexity of O(V + E), where V is the number of vertices and E is the number of edges.
Conclusion
Breadth-First Search is an essential algorithm for graph, tree, and grid traversal. In Kotlin, BFS can be implemented using queues, allowing systematic exploration of nodes or cells. By practicing BFS, beginners can strengthen their understanding of traversal strategies, queues, and problem-solving for shortest path or connectivity challenges. Mastering BFS opens the door to more advanced graph algorithms and real-world applications like routing, maze-solving, and social network analysis.
