Books / Graph Algorithms / Chapter 10

Graph Traversals - Breadth First Search Algorithm

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.

Licenses and Attributions

Speak Your Mind