BFS in Kotlin. Breath First Search

In this implementation, we define a Graph class that stores the graph as an adjacency list. The addEdge method adds an undirected edge between two vertices.

Kotlin

import java.util.*

class Graph(val numVertices: Int) {
    private val adjacencyList = Array(numVertices) { mutableListOf<Int>() }

    fun addEdge(src: Int, dest: Int) {
        adjacencyList[src].add(dest)
        adjacencyList[dest].add(src)
    }

The bfs method performs BFS starting from the given startVertex. We maintain a visited array to keep track of which vertices we have visited, and a queue to store the vertices we have yet to visit. We start by visiting the startVertex, marking it as visited, and adding it to the queue. We then repeatedly dequeue a vertex from the queue, print it, and enqueue all its unvisited neighbors. We continue until the queue is empty.

Kotlin

fun bfs(startVertex: Int) {
    val visited = BooleanArray(numVertices) { false }
    val queue: Queue<Int> = LinkedList<Int>()
    visited[startVertex] = true
    queue.add(startVertex)

    while (!queue.isEmpty()) {
        val currentVertex = queue.poll()
        print("$currentVertex ")

        val neighbors = adjacencyList[currentVertex]
        for (neighbor in neighbors) {
            if (!visited[neighbor]) {
                visited[neighbor] = true
                queue.add(neighbor)
            }
        }
    }
}
}

In the main function, we create a Graph with six vertices and add some edges. We then perform BFS starting from vertex 0 and print the traversal.

Kotlin

import java.util.*

class Graph(val numVertices: Int) {
    private val adjacencyList = Array(numVertices) { mutableListOf<Int>() }

    fun addEdge(src: Int, dest: Int) {
        adjacencyList[src].add(dest)
        adjacencyList[dest].add(src)
    }

    fun bfs(startVertex: Int) {
        val visited = BooleanArray(numVertices) { false }
        val queue: Queue<Int> = LinkedList<Int>()
        visited[startVertex] = true
        queue.add(startVertex)

        while (!queue.isEmpty()) {
            val currentVertex = queue.poll()
            print("$currentVertex ")

            val neighbors = adjacencyList[currentVertex]
            for (neighbor in neighbors) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true
                    queue.add(neighbor)
                }
            }
        }
    }
}

fun main() {
    val g = Graph(6)
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 2)
    g.addEdge(1, 4)
    g.addEdge(2, 3)
    g.addEdge(3, 4)

    println("BFS traversal starting from vertex 0:")
    g.bfs(0)
}

Leave a Comment Cancel reply