Breadth first search (BFS)
Algorithms #algorithms #bfs #graphsBreadth 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