The breadth first search algorithm is used for traversing all the nodes of a given graph.
1) Initialize an empty queue and pick any node of the graph to be the starting current node.
2) Insert all the adjacent nodes of the current vertex and put them into the queue.
3) Next visit the node on top of the queue, and that will be the new current vertex.
Pop the current vertex from the queue
4) Repeat step 2 on the new current vertex.
5) If no more unvisited adjacent vertices to the current node exist, move on to the next element of the queue.
6) Keep repeating steps 2 to 5 until all the nodes of the given graph have been visited.
Test yourself
Consider the following graph..
Which of the following is a valid order node visiting order generated using bfs ? (beginning from A)
If the tie-breaker in deciding which unvisited adjacent edge should be inserted into the queue first is reverse alphabetical order, in what order will the vertices be inserted (A is the start node).