Depth First Search

1. If there are 10 edges in a graph, in the worst case how many edges can DFS examine?

a: 0 Explanation

Explanation

b: 1 Explanation

Explanation

c: 5 Explanation

Explanation

d: 10 Explanation

Explanation

2. Which one of the following statements correctly compares DFS and BFS?

a: DFS uses a queue, while BFS uses a stack. Explanation

Explanation

b: In DFS, all neighbors are always traversed before any deeper vertex is explored. Explanation

Explanation

c: DFS is a vertex-based algorithm while BFS is an edge-based algorithm. Explanation

Explanation

d: BFS can find a shortest path in an unweighted graph, whereas DFS does not guarantee a shortest path. Explanation

Explanation

3. What is the primary goal of DFS when it is started from a particular source vertex?

a: To explore reachable vertices by going as deep as possible before backtracking. Explanation

Explanation

b: To visit only the immediate neighbors of the source. Explanation

Explanation

c: To sort all vertex labels. Explanation

Explanation

d: To remove all edges from the graph. Explanation

Explanation

4. What happens when DFS reaches a vertex whose adjacent vertices have already been visited?

a: DFS creates a new vertex. Explanation

Explanation

b: DFS backtracks to an earlier vertex to continue exploring another available path. Explanation

Explanation

c: DFS deletes the current vertex. Explanation

Explanation

d: DFS changes the graph from directed to undirected. Explanation

Explanation

5. Which data structure is commonly used to implement iterative DFS?

a: Queue Explanation

Explanation

b: Heap Explanation

Explanation

c: Stack Explanation

Explanation

d: Priority queue Explanation

Explanation

6. Why can recursion be used to implement DFS?

a: Recursion automatically sorts the graph. Explanation

Explanation

b: Recursion removes the need to mark vertices as visited. Explanation

Explanation

c: Recursion converts the graph into a tree. Explanation

Explanation

d: The function call stack naturally stores the pending vertices and supports backtracking. Explanation

Explanation

7. For an adjacency-list representation, why is the DFS complexity

O(V + E)

rather than

O(V^2)

in general?

a: DFS ignores edges that are not part of the DFS tree. Explanation

Explanation

b: DFS visits only half of the vertices. Explanation

Explanation

c: The adjacency list allows DFS to examine the actual edges associated with each visited vertex instead of checking every possible vertex pair. Explanation

Explanation

d: DFS never examines an edge more than once in either direction. Explanation

Explanation

8. Which property of DFS makes it useful for detecting cycles in a graph?

a: DFS records traversal relationships and can identify an edge leading to a vertex that is already active in the current traversal path. Explanation

Explanation

b: DFS always visits every vertex exactly twice. Explanation

Explanation

c: DFS removes every edge after examining it. Explanation

Explanation

d: DFS requires the graph to contain no cycles before it starts. Explanation

Explanation

9. A DFS is started from vertex

A

in a connected graph. If the graph contains 8 vertices, how many vertices will be visited by the DFS?

a: 1 Explanation

Explanation

b: 4 Explanation

Explanation

c: 7 Explanation

Explanation

d: 8 Explanation

Explanation