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.

Applications

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

Asymptotic Complexity

Pseudo Code

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

conquer(v)
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)
            q->enqueue(w)

Source Code

Full Repo

Relevant Files:

Click here for build and run instructions