This traversal algorithm uses a queue to store the nodes of each level of the graph as and when they are visited. These nodes are then taken one by one and their adjacent nodes are visited and so on until all nodes have been visited. The algorithm terminates when the queue becomes empty.

Algorithm for Breadth First Traversal is as follows: 

clearq (q) 

visited (v) = TRUE 

while not empty (q) do

for all vertices w adjacent to v do 

if not visited then

{

insert (w , q) 

visited (w) = TRUE

}

delete (v, q);

Here each node of the graph is entered in the queue only once. Thus the while loop is executed n times, where n is the order of the graph. If the graph is represented by adjacency list, then only those nodes that are adjacent to the node at the front of the queue are checked therefore, the for loop is executed a total of E times, where E is the number of edges in the graph. Therefore, breadth first algorithm is O (N*E) for linked expression. If the graph is represented by an adjacency matrix, the for loop is executed once for each other node in the graph because the entire row of the adjacency matrix must be checked. Therefore, breadth first algorithm is O (N² ) for adjacency matrix representation.