Breadth-First Search
Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level. Starting from a given source node, it visits all the neighbors of the source node first, then the neighbors of those neighbors, and so on. This process continues until all reachable nodes have been visited. BFS uses a queue data structure to maintain the order of nodes to visit. Nodes are enqueued as they are discovered and dequeued to be explored.
Consider a social network where you want to find all friends of a friend (2nd-degree connections). Starting with you as the source node, BFS would first visit all your direct friends (1st-degree connections). Then, for each of your friends, it would visit their friends, effectively finding your 2nd-degree connections. This is useful for suggesting new connections or finding people with similar interests within a network.BFS guarantees finding the shortest path (in terms of the number of edges) from the source node to any other reachable node in an unweighted graph. The algorithm's time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because each vertex and edge are visited at most once. BFS is complete, meaning that if a path exists between the source node and any other node, BFS will find it.