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.
\(O(m + n)\)
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)
Click here for build and run instructions