A graph traversal algorithm that explores neighbor nodes first, before moving to the next level neighbors.
Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph layer by layer. It starts at a given source vertex and explores all of its immediate neighbors. Then, for each of those neighbors, it explores their unexplored neighbors, and so on. This level-wise traversal is achieved by using a queue. The algorithm begins by putting the source vertex into the queue and marking it as visited. Then, in a loop, it dequeues a vertex, processes it, and enqueues all of its unvisited neighbors, marking them as visited. This continues until the queue is empty. BFS is particularly useful for finding the shortest path between two nodes in an unweighted graph. The first time BFS visits a target node, it is guaranteed to have found a shortest path to it from the source, where 'shortest' is defined as the minimum number of edges. This property makes it invaluable in various applications, such as finding the shortest route in a GPS system (if all road segments have equal length), web crawling, and finding all connected components in a graph. The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges, because every vertex and every edge will be explored once.