Consider the following undirected graph with vertices a, b, c, f, g, h and edges:
a–b, a–c, a–f, b–c, b–f, b–h, c–g, f–g, f–h, g–h
The following depth-first search (DFS) 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) a-b-c-g-h-f, (C) a-b-f-h-g-c and (D) a-f-g-h-b-c follow edges and backtrack correctly. In (B), after a-b-f the DFS must go to an unvisited neighbour of f (g or h); c is not adjacent to f.More Data Structures and Algorithms questions
- Consider the following algorithms and their running times. Which one of the following is correct?List I List II A. Breadth-first search I.…
- Consider the following statements on approximation algorithms: Statement I: APPROX-VERTEX-COVER is a polynomial-time 2-approximation algori…
- Which of the following is used to determine the cost performance index?
- Software project manager is responsible for the following task: (A) Project planning (B) Project status tracking (C) Resources management (…
- Fill in the blanks: "An ________ chart is a project schedule representation that presents the project plan as a directed graph. The critica…
- Which of the following are the primary objectives of risk monitoring in software project tracking? P: To assess whether predicted risks do,…