###### Books / Graph Algorithms / Chapter 10

# Graph Traversals - Breadth First Search Algorithm

## Breadth-first Search

In the previous chapter, we looked at the Depth-first search or *DFS* algorithm. A DFS is implemented using a Stack. Put simply, if we implement DFS using a queue instead of a stack, we get Breadth-first search or BFS. Queues support insertions (push) and deletions (pull) in O(1) time each, so the algorithm runs in *O(V + E)* time. In this case, the breadth-first spanning tree formed by the parent edges contains shortest paths from the start vertex s to every other vertex in its component.

BFS searches all nodes at the **current** depth prior to moving on to the nodes at the next depth level. DFS on the other hand explores the node branch as far as possible before backtracking and expanding other nodes.