CS607P Quiz 2

VU TOOLKIT · CS607P - Quiz No.02 · Date: 01 May 2026

Q1. On the given graph, if we perform DFS starting from node A. Which of the following could be a valid DFS traversal order? Graph (Adjacency List): A → B, C B → (no outgoing edges) C → (no outgoing edges)

1. A, B, C
2. C, B, A
3. C, A, B
4. B, C, A

Correct answer: A, B, C

Q2. ___________ condition is sufficient to detect cycle in a directed graph.

1. There is an edge from currently being visited node to an already visited node
2. There is an edge from currently being visited node to an ancestor of currently visited node in DFS forest
3. Every node is seen twice in DFS
4. Every edge is seen twice in DFS

Correct answer: There is an edge from currently being visited node to an ancestor of currently visited node in DFS forest

Q3. What will be the time complexity of the iterative depth first search traversal code , where V = No. of Vertices, E = No. of Edges ?

1. O(V+E)
2. O(V)
3. O(E)
4. O(V*E)

Correct answer: O(V+E)

Q4. On the given graph, if DFS starts from A and visits C first, what is the traversal order? Graph (Adjacency List): A → B, C B → C C → (no outgoing edges)

1. B, C, A
2. A, B, C
3. B, A, C
4. A, C, B

Correct answer: A, C, B

Q5. If DFS starts from A on the given graph, which node will NOT be visited? Graph (Adjacency List): A → B, C B → C D → A

1. B
2. D
3. A
4. C

Correct answer: D