Related Books
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.
