Breadth first search (BFS)

Breadth First Search (BFS)

BFS (Breadth-First Search) is a graph traversal algorithm used to traverse the graph data structure in a breadth-first manner, visiting all the vertices at the same depth level before moving on to the next level. The algorithm starts at a source vertex and visits all the vertices at a distance of one edge from the source, then all the vertices at a distance of two edges, and so on, until all vertices have been visited.

Usage

BFS is useful in many graph-related problems, such as finding the shortest path between two vertices, testing for graph connectivity, finding the connected components of an undirected graph etc

Illustration

Example

  • This sample code performs a BFS on the graph above.

BFS (Queue based implementation)

import java.util.*

fun main() {
    val adjacencyMap = mutableMapOf(
        0 to listOf(1, 2),
        1 to listOf(0, 2),
        4 to listOf(5, 8),
        2 to listOf(7, 1, 0, 3),
        5 to listOf(8, 4),
        6 to listOf(3, 9, 10),
        3 to listOf(2, 6),
        11 to listOf(),
        7 to listOf(2, 5),
        8 to listOf(4, 5),
        10 to listOf(6, 11),
        9 to listOf(6, 11)
    )

    breadthFirstSearchQueue(adjacencyMap)
}

//sampleStart
fun breadthFirstSearchQueue(adjacencyMap: Map<Int, List<Int>>) {
    // click + to see full script

    if (adjacencyMap.isEmpty()) {
        return
    }

    // store a boolean value for each vertex, true if visited false otherwise
    val visitedVertices = BooleanArray(adjacencyMap.size)

    fun bfs(vertex: Int) {
        val queue: Deque<Int> = LinkedList()
        queue.offer(vertex)
        // mark start vertex as visited
        visitedVertices[vertex] = true

        while (queue.isNotEmpty()) {
            val currentVertex = queue.poll()
            // print visited
            print(" $currentVertex")
            adjacencyMap[currentVertex]?.forEach { adjacentVertex ->
                if (visitedVertices[adjacentVertex].not()) {
                    visitedVertices[adjacentVertex] = true
                    queue.offer(adjacentVertex)
                }
            }
        }
    }


    /**
     * Iterate over all the vertices and start BFS if vertex
     * is not already visited
     */
    for (vertex in adjacencyMap.keys) {
        if (visitedVertices[vertex].not()) {
            bfs(vertex)
        }
    }
}
//sampleEnd

BFS (Recursive)

import java.util.*

fun main() {
    val adjacencyMap = mutableMapOf(
        0 to listOf(1, 2),
        1 to listOf(0, 2),
        4 to listOf(5, 8),
        2 to listOf(7, 1, 0, 3),
        5 to listOf(8, 4),
        6 to listOf(3, 9, 10),
        3 to listOf(2, 6),
        11 to listOf(),
        7 to listOf(2, 5),
        8 to listOf(4, 5),
        10 to listOf(6, 11),
        9 to listOf(6, 11)
    )

    breadthFirstSearchRecursive(adjacencyMap)
}

//sampleStart
fun breadthFirstSearchRecursive(adjacencyMap: Map<Int, List<Int>>) {
    // click + to see full script
    if (adjacencyMap.isEmpty()) {
        return
    }

    // store a boolean value for each vertex, true if visited false otherwise
    val visitedVertices = BooleanArray(adjacencyMap.size)

    fun bfs(queue: Deque<Int>) {
        if (queue.isEmpty()) {
            return
        }

        val currentVertex = queue.poll()

        // print visited
        print(" $currentVertex")
        adjacencyMap[currentVertex]?.forEach { adjacentVertex ->
            if (visitedVertices[adjacentVertex].not()) {
                visitedVertices[adjacentVertex] = true
                queue.offer(adjacentVertex)
            }
        }
        bfs(queue)
    }


    /**
     * Iterate over all the vertices and start BFS if vertex
     * is not already visited
     */
    for (vertex in adjacencyMap.keys) {
        if (visitedVertices[vertex].not()) {
            val queue = LinkedList<Int>().apply {
                visitedVertices[vertex] = true
                offer(vertex)
            }
            bfs(queue)
        }
    }
}
//sampleEnd

top