Skip to content
GATETECH
Official PYQ · 2000Q1.13Graph Traversals (BFS, DFS)MCQ1 mark

GATE CS 2000 Q1.13 — Graph Traversals (BFS, DFS)

Explain with AI

The most appropriate matching for the following pairs

X: depth first search1: heap Y: breadth first search2: queueZ: sorting3: stack\begin{array}{|l|l|}\hline \text{X: depth first search} & \text{1: heap } \\ \hline \text{Y: breadth first search} & \text{2: queue} \\ \hline \text{Z: sorting} & \text{3: stack} \\ \hline \end{array}

is:

Choose one option
View worked solution

Answer: C

We can match the algorithms with their primary associated data structures as follows:

  • X: Depth First Search (DFS) explores as deep as possible along each branch before backtracking. This backtracking behavior is naturally implemented using a Stack (LIFO structure), either explicitly or implicitly via recursion.
      ⟹  X→3\implies \text{X} \to \text{3}
  • Y: Breadth First Search (BFS) explores the neighbor nodes first before moving to the next level of neighbors. This level-order traversal is implemented using a Queue (FIFO structure).
      ⟹  Y→2\implies \text{Y} \to \text{2}
  • Z: Sorting can be efficiently performed using a Heap data structure (specifically, Heapsort, which has a time complexity of O(nlog⁡n)\mathcal{O}(n \log n)).
      ⟹  Z→1\implies \text{Z} \to \text{1}

Therefore, the correct matching is X - 3, Y - 2, Z - 1, which corresponds to Option C.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Graph Traversals (BFS, DFS) questions