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 a set to keep track of nodes that are already scheduled to visit, as graphs can have cycles.

Algorithm

The breadth-first traversal algorithm utilises the breadth-first search algorithm to traverse all nodes connected to a given node. The breadth-first search is a simple two-step algorithm in which we maintain a queue of nodes to visit and a visited set to keep track of nodes scheduled for a visit. It can be considered a generalisation of the level order traversal algorithm for trees.

Only applying breadth-first search from any one node in the graph may not be enough, as it may not cover all the nodes of the graph if the graph is disconnected.