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:
        w = edge->head
        if w is NOT conquered:
            conquer(w)
+           w->distance = v->distance + 1
            q->enqueue(w)

Source Code

Full Repo

Relevant Files:

BFS_ShortestPath.h
BFS_ShortestPath.c
BRS_ShortestPathTests.c

Click here for build and run instructions