Breadth First Search (BFS)

BFS examines each edge of a particular vertex before following any edges of connected vertices. The key to this is the use of a Queue as shown in the pseudo below.


  • Connectivity - In a network, ensure that every node is reachable.

Asymptotic Complexity

\(O(m + n)\)

Pseudo Code

G = input graph
q = queue data structure
v = starting vertex
side effects: marks all vertices conquered that are reachable from v


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

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions