Last reviewed
Correct answer: C. Depth-first goes as deep as possible before backtracking; breadth-first visits all nodes at the current level first
Explanation
Both algorithms pull a vertex from a pending set, visit it, and push its undiscovered neighbours back in. The only thing separating them is which pending vertex comes out next, and that is decided by the container. Depth-first takes the most recently discovered one, through an explicit stack or through recursion, so it drives to the end of one branch and backtracks only when it runs out of edges. Breadth-first takes the oldest pending vertex from a queue, so every vertex at distance k from the start is visited before any vertex at distance k plus one.
That single ordering choice is where the practical differences come from. On an unweighted graph, breadth-first finds a path with the fewest edges and depth-first offers no such guarantee. Memory trades the other way: depth-first holds one root-to-current path, breadth-first holds an entire level, which on a wide graph is far larger. Neither is limited by structure. Preorder, in-order and postorder tree walks are all depth-first searches, and breadth-first over a tree is exactly level-order traversal.
Sources
“Extremes are searched first. This is easily implemented with recursion.”
“Extremes are searched last. This is typically implemented with a queue.”
“Process all nodes of a tree by depth: first the root, then the children of the root, etc. Equivalent to a breadth-first search from the root.”
Practise 3 questions on this topic
Take Trees & Graphs — Timed Test (3 questions) — scored instantly, explanation for every question, no login.