Hands-On Data Structures and Algorithms with Python - Second Edition

Breadth-first traversal

Breadth-first traversal algorithms work breadth-wise in the graph. A queue data structure is used to store the information of vertices that are to be visited in the graph. We begin with the starting node, the A node. Firstly, we visit that node, and then we look up all of its neighboring, or adjacent, vertices. We first visit these adjacent vertices one by one, while adding their neighbors to the list of vertices that are to be visited. We follow this process until we have visited all the vertices of the graph, ensuring that no vertex is visited twice.

Let's consider an example to better understand breadth-first traversal for graphs, using the following diagram:

In the preceding diagram, we have a graph of five nodes ...