rule if you can' carry out rule because the queue is emptyyou're done thusyou first visit all the vertices adjacent to ainserting each one into the queue as you visit it now you've visited abcdand at this point the queue (from front to rearcontains bcde there are no more unvisited vertices adjacent to aso you remove from the queue and look for vertices adjacent to it you find fso you insert it in the queue there are no more unvisited vertices adjacent to bso you remove from the queue it has no adjacent unvisited verticesso you remove and visit has no more adjacent unvisited verticesso you remove now the queue is fg you remove and visit hand then you remove and visit now the queue is hibut when you've removed each of these and found no adjacent unvisited verticesthe queue is emptyso you're done table shows this sequence table event visit visit visit visit visit remove visit remove remove visit remove remove visit remove visit remove remove done queue contents during breadth-first search queue (front to rearb bc bcd bcde cde cdef def ef efg fg gh hi at each momentthe queue contains the vertices that have been visited but whose neighbors have not yet been fully explored (contrast this breadth-first search with the depth-first searchwhere the contents of the stack is the route you took from the starting point to the current vertex the nodes are visited in the order abcdefghi