# Pseudo code for constructing a spanning tree using breadth-first search

empty spanning tree T
mark root as visited
add root to visit queue
while (queue not empty) {
   v = head of queue

   find unvisited neighbor w of v
   if (w exists) {
       mark w as visited
       add edge [ v, w ] to T
       add w to visit queue
       }
    else {
       # no unvisited neighbours of head of queue
       remove head of queue
       }
    }