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:
w = edge->head
if w is NOT conquered:
conquer(w)
q->enqueue(w)
Source Code
Relevant Files:
Click here for build and run instructions