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

$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

conquer(v)
q->enqueue(v)

while q is not empty:
v = q->dequeue
for each edge in v: