In breadth first search, we visit nodes in the graph along the edges by storing all of the nodes connected to our starting node in a FIFO queue and subsequently enqueuing each unseen additional node. Proceed through the queue until all nodes have been visited. For each visited node, store the parent, the depth at that node, and a boolean for whether it was already seen (to avoid visiting the same node twice). The result of a breadth first search is a breadth first tree representation of the graph. Breadth first search is guaranteed to return the shortest distance between two nodes. ``` queue = {s} s.d = 0 s.seen = True s.pi = NIL while queue is not empty: u = dequeue(queue) for all v in u.get_neighbors(): if ! v.seen: v.d = u.d + 1 v.pi = u v.seen = TRUE enqueue(queue, v) ```