3.7.3.1 Breadth-First Search (BFS)
Algorithms and Problem Solving
Breadth-First Search (BFS) is a graph traversal algorithm that explores all the nodes of a graph level by level, starting from a given node (often called the root). It uses a queue to keep track of the nodes that need to be explored.
Process:
- Start from the root node and enqueue it.
- Dequeue a node, process it, and enqueue all its unvisited neighbors.
- Repeat the process until the queue is empty.
Example: In a social network graph, where each node represents a person and edges represent friendships, BFS can be used to find the shortest path between two people (e.g., finding the degree of separation between two users).
Complexity: The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges. This makes it efficient for exploring large graphs.