Stop When All Nodes Are Visited
The standard BFS algorithm can be tweaked for connected graphs for better performance. Instead of waiting for the queue to be empty to terminate, keep track of whether all nodes are visited or not and exit when no unvisited nodes are left.
In the case of a fully connected graph, this means that the algorithm terminates after 1 iteration vs a traditional BFS which does much more unneeded work.
See this Drill Bits article which details this modification.