Breadth first search
Breadth first search or BFS explores a graph in expanding rings around a start vertex. It visits every vertex at distance one, then every vertex at distance two, and so on. This makes it the natural tool for finding the fewest edges path in an unweighted graph.
The queue drives it
BFS uses a queue, a first in first out structure.
- Put the start vertex in the queue and mark it visited.
- Repeatedly remove the front vertex and look at its neighbors.
- Any unvisited neighbor gets marked visited and pushed to the back of the queue.
Marking a vertex visited the moment you enqueue it prevents adding the same vertex twice. The order of removal guarantees that closer vertices come out before farther ones.
What it gives you
Because it processes vertices in order of distance, BFS finds the shortest path in edge count from the start to every reachable vertex. Each vertex and edge is touched a constant number of times.
Key idea
BFS uses a queue to fan out level by level, giving the shortest unweighted path in edges from the start.