Shortest Path using BFS (Non-Weighted)

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.

Asymptotic Complexity

$O(m + n)$

Pseudo Code

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: