Breadth-First Search (BFS)
Breadth-First Search (BFS) is an algorithm used to explore nodes and edges in a graph. It systematically explores the vertices in layers, expanding each vertex's neighbors before moving on to the next layer. BFS is particularly useful for finding the shortest path in an unweighted graph or for traversing graphs level by level.
Key Concepts:
Graph: BFS can be applied to both directed and undirected graphs, as well as connected or disconnected graphs.
Queue: BFS uses a queue data structure to explore nodes in a breadthward motion (FIFO order).
Visited List: A list or set to keep track of already visited nodes to avoid re-exploring them.
Steps:
Start by visiting a given source node.
Visit all its immediate neighbors (i.e., its adjacent vertices).
For each neighbor, visit their unvisited neighbors.
Repeat this process until all vertices are visited or a target node is found.
Key Points:
Level Order Traversal: BFS explores the graph level by level. All vertices at a given level (distance from the source) are visited before moving on to the next level.
Shortest Path in Unweighted Graph: BFS can be used to find the shortest path between two nodes in an unweighted graph because it explores all possible paths level by level.
Disconnected Graphs: If the graph is disconnected, BFS only explores the connected component that contains the source node.
Example Usage:
Finding Shortest Path in an unweighted graph.
Level-Order Traversal of a tree.
Exploring Connected Components of a graph.