Understanding breadth first traversal

The depth-first traversal algorithm that we learned earlier uses the depth-first search algorithm that relies on the function call stack, and may not be the best solution for some graph exploration use cases. The breadth-first traversal is another fundamental graph traversal algorithm that uses breadth-first search to explore all nodes at a fixed distance (depth) before moving to nodes at the next greater distance (depth). It can be visualized as moving outwards from the centre of concentric circles, covering one full circle at a time.

Just like depth-first search is the generalization of preorder, inorder, and postorder traversals, breadth-first search is the generalization of level traversal. The only difference between the level order traversal of a tree and the breadth-first search of a graph is that we maintain map to keep track of nodes that are already scheduled to visit, as graphs can have cycles.