Breadth-first search starts at a given vertex h, which is at level 0. In the first stage, we go toall the vertices that are at the distance of one edge away. When we go there, we markedas "visited," the vertices adjacent to the start vertex s - these vertices are placed into level 1.In the second stage, we go to all the new vertices we can reach at the distance of two edgesaway from the source vertex h. These new vertices, which are adjacent to level 1 vertex and notpreviously assigned to a level, are placed into level 2. The BFS traversal ends when each vertexhas been finished.The BFS(G, a) algorithm creates a breadth-first search tree with the source vertex, s, as its root.The predecessor or parent of any other vertex in the tree is the vertex from which it was firstdeveloped. For every vertex, v, the parent of v is marked in the variable π[v]. Another variable,d[v], calculated by BFS has the number of tree edges on the way from s tov. The breadth-firstsearch needs a FIFO queue, Q, to store red vertices.Algorithm: Breadth-First Search TraversalBFS(V, E, a)1.2. do color[u] ← BLACK3. d[u] ← infinity4. π[u] ← NIL5. color[s] ← RED ? Source vertex find6. d[a] ← 0 ? Start7. π[a] ← NIL ? Stat8. Q ← {} ? Empty queue Q9. ENQUEUE(Q, a)10 while Q is non-empty11. do u ← DEQUEUE(Q) ? That is, u = head[Q]12.13. do if color[v] ← BLACK ? if color is black you've never seen it before14. then color[v] ← RED15. d[v] ← d[u] + 116. π[v] ← u17. ENQUEUE(Q, v)18. DEQUEUE(Q)19. color[u] ← BLACK