QUESTION 21

Which data structure distinguishes ordinary BFS from iterative DFS?

2 marks

Answer

BFS uses a FIFO queue; iterative DFS uses a stack. Recursive DFS uses pending function calls with stack-like order.

Compare DFS and BFS with the same graph.

5 marks

Answer in brief

DFS and BFS both explore reachable vertices, but their pending-work order differs.

Shared requirements

Both need a graph representation, a starting rule and visited tracking. Both must restart at unvisited vertices if the task requires every component. State neighbour order when giving one exact printed sequence.

DFS

It follows a branch before backtracking. On the common five-vertex example with ascending neighbours, it gives 0, 1, 3, 2, 4. An explicit stack or recursion keeps unfinished work. The maximum active depth can reach V.

BFS

It explores level by level using a queue. The same example gives 0, 1, 2, 3, 4. Mark on enqueue to avoid duplicate pending entries. It naturally supports unweighted edge-distance calculations when distances are recorded.

Complexity

Both have O(V + E) time with standard adjacency lists and O(V²) with a matrix full traversal. Both can need O(V) auxiliary storage, although their practical pending-work patterns differ. The choice does not automatically reduce the representation’s own storage.

Choosing

Use BFS for level-order reachability or shortest numbers of unweighted edges. DFS is useful for deep exploration and as a base for analyses that require entering and finishing vertices. Neither basic traversal performs all possible graph applications without additional state or rules.

Reference table

↔ Scroll horizontally on a small screen

Traversal comparison
Feature	DFS	BFS
Pending work	Stack/calls	Queue
Exploration	Depth first	Level first
List time	O(V + E)	O(V + E)
Matrix time	O(V²)	O(V²)
Auxiliary space	O(V) worst case	O(V) worst case

Diagram or flowchart

CodeBhavya illustration of graph — Compare DFS and BFS with the same graph. · Download diagram