BFS Algorithm
The Breadth-First Search (BFS) algorithm is a graph traversal technique used to explore all the vertices and edges of a graph in a systematic and organized manner. It is particularly useful for searching through tree-like data structures or finding the shortest path between two nodes in a graph. BFS operates by visiting all the neighboring vertices of a starting node, before moving on to their respective neighbors. This approach ensures that vertices at the same level (or distance from the starting node) are visited before those at the next level, providing a breadthwise exploration of the graph.
The BFS algorithm begins by initializing a queue with the starting node, marking it as visited. It then proceeds by repeatedly dequeuing the next vertex in the queue, examining its unvisited neighbors, marking them as visited, and enqueueing them. This process is repeated until the queue becomes empty, indicating that all reachable vertices from the starting node have been visited. BFS has a wide range of applications in various domains, including route planning, social network analysis, and artificial intelligence. Its time complexity is O(V+E), where V is the number of vertices in the graph and E is the number of edges.
/*
* Copyright (c) 2017 Kotlin Algorithm Club
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in all
* copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*/
package com.algorithmexamples.graphs
import com.algorithmexamples.datastructures.Queue
class BFS {
companion object Implementations {
fun iterative(graph: Graph, levelOrder: ((Int) -> Unit)? = null) {
val visited = BooleanArray(graph.V)
val queue = Queue<Int>()
for (i in 0 until graph.V) {
if (!visited[i]) {
queue.add(i)
visited[i] = true
levelOrder?.invoke(i)
while (!queue.isEmpty()) {
val v = queue.poll()
for (w in graph.adjacentVertices(v)) {
if (!visited[w]) {
queue.add(w)
visited[w] = true
levelOrder?.invoke(i)
}
}
}
}
}
}
}
}
