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

+ v->distance = 0

while q is not empty:
    v = q->dequeue
    for each edge in v:
        w = edge->head
        if w is NOT conquered:
+           w->distance = v->distance + 1

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions