For the graph shown, the following depth-first search sequences are given: (A) abcghf (B) abfchg (C) abfhgc (D) afghbc. Which of the following is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. (A), (C) and (D) only
Explanation
A sequence is a valid DFS if each new vertex is adjacent to the most recent vertex that still has unvisited neighbours. Checking each sequence against the figure's edges, the official key accepts (A), (C) and (D); in (B), the step after f to c is not possible by DFS.
More Data Structures and Algorithms questions
- Match each algorithm with its running time. (A) Breadth-first search, (B) Rabin–Karp algorithm, (C) Depth-first search, (D) Heap sort (wors…
- Statement I: Vertex cover has a polynomial-time 2-approximation algorithm. Statement II: TSP-tour is a polynomial-time 3-approximation algo…
- The postfix form of the expression (A + B) * (C * D - E ) * F /G is _______
- A double‐ended queue (dequeue) supports adding and removing items from both the ends of the queue. The operations supported by dequeue are…
- Two balanced binary trees are given with m and n elements, respectively. They can be merged into a balanced binary search tree in ____ time.
- A data structure is required for storing a set of integers such that each of the following O(log n) operations can be done in time, where n…