What is the BFS traversal of the directed graph below when traversal starts at…
2021
What is the BFS traversal of the directed graph below when traversal starts at A and each vertex’s outgoing neighbours are examined from top to bottom as drawn?
Answer: C. A B D C F — ConceptBreadth-First Search (BFS) explores a directed graph level by level from a chosen source. A FIFO queue preserves discovery order: visit the source,…
- A.
A F D B C E
- B.
C B A F D
- C.
A B D C F
- D.
F D C B A
- E.
Question not attempted
Attempted by 478 students.
Show answer & explanation
Correct answer: C
Concept
Breadth-First Search (BFS) explores a directed graph level by level from a chosen source. A FIFO queue preserves discovery order: visit the source, enqueue its outgoing neighbours, and then process each queued vertex once. Only vertices reachable by a directed path from the source can appear in the traversal.
Application
Start at A. Visit A and enqueue its outgoing neighbours B and D in the order shown.
Dequeue B. Its outgoing edge reaches C, so enqueue C. The queue is now D, C.
Dequeue D. Its outgoing edge reaches F, so enqueue F. The edge joining E and D points from E to D, so it does not make E reachable from A.
Dequeue C and then F. Neither contributes a new reachable vertex, so the queue becomes empty.
Cross-check
The reachable levels from A are {A}, then {B, D}, then {C, F}. E is excluded because its edge points into D and there is no directed path from A to E.
Therefore, the BFS traversal is A, B, D, C, F.