Graph BFS Implementation

Welcome to our session on Graph Algorithms Implementation.

A large proportion of real-world problems, from social networking to routing applications, can be represented as graphs. Thus, understanding and implementing graph algorithms is a key skill to have in your programming toolkit.

In this lesson, we introduce and explore one of the most fundamental graph traversal algorithms — the Breadth-First Search (BFS).

Let's take a sneak peek at the BFS algorithm. Given a graph and a starting vertex, BFS systematically explores the edges of the graph to "visit" each reachable vertex.

It does so by managing a queue of vertices to be explored. A crucial optimization in BFS is marking a node as visited the moment it is added to the queue. This prevents the same node from being added multiple times through different paths, keeping our search efficient. BFS is particularly useful because it finds the shortest path between the starting vertex and all other vertices in an unweighted graph.

In Kotlin, we represent the graph using a Map, where each key is a node and its value is a list of adjacent nodes. We use ArrayDeque to handle our queue operations.

Here's a sample BFS algorithm implemented in Kotlin that we will master:

import kotlin.collections.ArrayDeque

fun bfs(graph: Map<Int, List<Int>>, start: Int): List<Int> {
    val visited = mutableSetOf<Int>()
    val queue = ArrayDeque<Int>()
    val result = mutableListOf<Int>()

    // Mark as visited and enqueue the starting node
    visited.add(start)
    queue.addLast(start)

    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        result.add(node)
        
        val neighbors = graph[node] ?: emptyList()
        for (neighbor in neighbors) {
            // Check if already visited before enqueuing
            if (neighbor !in visited) {
                visited.add(neighbor)
                queue.addLast(neighbor)
            }
        }
    }

    return result
}

In many interview scenarios, the graph is not provided as an explicit adjacency list. Instead, it is implicit, such as a 2D grid or a set of movement rules (like a knight on a chessboard).

In these cases:

• Nodes are often represented by coordinates (row, col).
• Edges are defined by valid moves (e.g., up, down, left, right).
• Neighbors are calculated on the fly by applying offsets to the current position and checking if the new coordinates are within the grid boundaries and haven't been visited.

To handle movement efficiently, we often use direction arrays:

val directions = arrayOf(
    intArrayOf(0, 1),  // Right
    intArrayOf(0, -1), // Left
    intArrayOf(1, 0),  // Down
    intArrayOf(-1, 0)  // Up
)

// Inside the BFS loop:
for (dir in directions) {
    val newRow = currentRow + dir[0]
    val newCol = currentCol + dir[1]
    
    if (newRow in 0 until maxRows && newCol in 0 until maxCols && !visited[newRow][newCol]) {
        visited[newRow][newCol] = true
        queue.addLast(Pair(newRow, newCol))
    }
}

As we delve into this session, we will understand the mechanics behind BFS. Our study will include the concepts of traversal, the usefulness of the ArrayDeque data structure, and how to handle the discovery and processing of nodes using MutableSet and MutableList.

Equipped with these fundamentals, we'll practice a variety of problems that call for BFS to perform node-level searches in a graph, whether it is explicitly defined or hidden within a grid. Let's dive in and uncover the power of graph algorithms!