One unique attribute of BFS is that with only a few extra lines of code, it can be used to calculate the degrees of separation between nodes. This is only valid for non-weighted graphs.
$O(m + n)$
G = input graph q = queue data structure v = starting vertex side effects: marks all vertices with the degrees of seperation from v conquer(v) + v->distance = 0 q->enqueue(v) while q is not empty: v = q->dequeue for each edge in v: w = edge->head if w is NOT conquered: conquer(w) + w->distance = v->distance + 1 q->enqueue(w)
Click here for build and run instructions