Breadth-First Search Algorithm in Kotlin

1. Introduction

Breadth-First Search (BFS) is a fundamental algorithm for traversing or searching tree or graph data structures. It starts at a chosen node (often the root in the case of a tree) and explores all of the neighbor nodes at the present depth before moving on to the nodes at the next depth level. BFS is particularly useful for finding the shortest path on unweighted graphs.

In this tutorial, we’ll explore the implementation of the BFS algorithm in Kotlin.

2. Understanding BFS

As we’ve touched upon, the BFS algorithm begins its traversal at a specific node, often the root in tree structures, and then explores all neighboring nodes at the current depth before advancing to nodes at the next depth level.

This level-wise traversal approach ensures that all nodes are reached efficiently, making it ideal for finding the shortest paths in graphs where all edges are of equal weight. The simple principle behind BFS, processing nodes level by level, allows for thoroughly exploring graphs, emphasizing its foundational role in computer science and its applicability across various programming languages.

3. Implementing BFS in Kotlin

Now that we’ve covered the theory, we’ll implement the BFS algorithm in Kotlin.

3.1. Defining a Graph

First, we need to define a graph. We’ll use an adjacency list as it’s a common and efficient way to represent graphs in Kotlin. Additionally, to provide a concrete example, we’ll initialize our graph with some nodes and edges to illustrate how BFS works in practice:

val graph = mutableMapOf<Int, List<Int>>(
    1 to listOf(2, 3, 4),
    2 to listOf(5, 6),
    3 to listOf(),
    4 to listOf(7, 8),
    5 to listOf(),
    6 to listOf(),
    7 to listOf(),
    8 to listOf()
)

To better understand the graph structure we’ll be traversing, let’s consider its visual representation:

      1
   /  |  \
  2   3   4
 / \     / \ 
5   6   7   8

This diagram helps us visualize the BFS traversal starting from the root node of “1”.

3.2. BFS Implementation

Let’s implement bfs() and relate it line by line to the theory we studied earlier:

fun bfs(graph: Map<Int, List<Int>>, start: Int): Set<Int> {
    val visited = mutableSetOf<Int>()
    val queue = ArrayDeque<Int>()
    queue.add(start)
    while (queue.isNotEmpty()) {
        val vertex = queue.removeFirst()
        if (vertex !in visited) {
            visited.add(vertex)
            graph[vertex]?.let { neighbors -> queue.addAll(neighbors.filterNot { it in visited }) }
        }
    }
    return visited
}

The code snippet above provides a practical implementation of the BFS algorithm, translating the theoretical concepts we’ve discussed into actionable Kotlin code. At its core, this implementation leverages a queue to explore nodes level by level, ensuring a systematic visitation pattern that adheres to the BFS paradigm.

The process begins by marking the start node as visited, then iteratively explores each node’s neighbors, traversing the graph in the broadest manner possible. This methodical approach guarantees that all nodes reachable from the starting point are visited, one level at a time.

3.3. Understanding the BFS Implementation

Having observed the BFS algorithm in action, let’s delve into the specifics of our implementation:

• Initialization: We first create a mutable set called visited to keep track of the nodes we have visited. This is important to prevent revisiting nodes, which could lead to an infinite loop in cyclic graphs. We also create a queue named queue to manage the nodes that need exploration. This queue will ensure that we explore nodes in the order of their discovery, adhering to the BFS strategy.
• Starting Node: The BFS algorithm begins by adding the starting node to the queue. This is our entry point into the graph.
• Traversal Loop: At the core of the BFS implementation is a loop that runs as long as there are nodes in the queue awaiting exploration. Inside this loop, we remove the next node for exploration (vertex) from the queue and check whether we’ve visited it. If we haven’t, we mark it as visited by including it in the visited set.
• Exploring Neighbors: For each unvisited node, we retrieve its neighbors from the graph. We then filter out the neighbors that have already been visited and add the remaining ones to the queue. This step ensures that we’ll eventually explore every node reachable from the starting node, in the order of closest to farthest from the start.
• Completion: Once the queue is empty, indicating no more nodes to explore, the loop terminates. At this point, the visited set contains all the nodes that were visited during the traversal, in the order they were visited. This set is then returned as the result of the BFS implementation.

4. Testing Our BFS Implementation

Finally, to ensure our BFS functions as expected, we need to test our implementation. Let’s validate that our code is correct by writing a JUnit test. Using the graph we first defined, we’ll traverse it with our BFS implementation and assert the order in which we’ve visited the nodes:

@Test
fun `test BFS traversal order`() {
    val graph = mapOf(
        1 to listOf(2, 3, 4),
        2 to listOf(5, 6),
        3 to listOf(),
        4 to listOf(7, 8),
        5 to listOf(),
        6 to listOf(),
        7 to listOf(),
        8 to listOf()
    )

    val traversalOrder = bfs(graph, 1)

    val levelOne = listOf(traversalOrder.first())
    assertThat(levelOne).containsExactly(1)

    val levelTwo = traversalOrder.drop(1).take(3)
    assertThat(levelTwo).containsExactlyInAnyOrder(2, 3, 4)

    val levelThree = traversalOrder.drop(4)
    assertThat(levelThree).containsExactlyInAnyOrder(5, 6, 7, 8)
}

This test proves that our BFS implementation correctly traverses the graph in the correct order from the root node. After invoking our bfs() function to obtain the traversal order, we slice the traversalOrder list to isolate each level of the graph. Finally, using assertions, we check that the nodes for each level are as expected, emphasizing the algorithm’s breadth-first approach.

5. Conclusion

Implementing the BFS algorithm in Kotlin provides a great way to explore graphs and trees efficiently. By leveraging Kotlin’s concise syntax and powerful standard library, developers can implement and apply BFS to solve a wide range of problems in both academic and real-world applications.