Depth First Search

1. Which one of the following steps is incorrect when performing DFS?

a: STEP 1: Start by putting any one of the graph's vertices on top of a stack (acts as source node of DFS). b: STEP 2: Take the top item of the stack and set its visited as 1. c: STEP 3: Create a list of that vertex's adjacent nodes. Add the ones whose visited is 1 to the top of the stack. d: STEP 4: Keep repeating steps 2 and 3 until the stack is empty.

2. What is the time complexity of DFS? V is the number of vertices & E is the number of edges

a: O(V^2) b: O(V+E) c: O(E^2) d: O(VlogV)

3. Pick the incorrect option

a: BFS consumes more memory & DFS consumes less memory b: DFS goes deeper & deeper until the node has no children c: BFS involves traversing neighbors before other nodes d: DFS uses queue

4. Which one of the following are applications of DFS?

a: Topological Sorting b: Minimum Spanning Tree c: Finding connected components d: All of the above

5. DFS can only be applied on Trees & not on Graphs.

a: True b: False

6. Pick the incorrect option

a: DFS uses exhaustive traversal along one path before exploring other options b: DFS can be used to find the shortest path between two nodes c: DFS uses stack or recursion d: DFS can be used in topological sorting

When we apply DFS on the above graph, which one of the following order of traversal is not possible?

a: 2,7,2,6,5,11,5,9,4 b: 2,7,5,2,6,9,5,11,4 c: 2,7,6,5,11,2,5,9,4 d: 2,5,9,4,7,2,6,5,11

Community Links Sakshat Portal Outreach Portal FAQ: Virtual Labs

AGPL 3.0 & Creative Commons (CC BY-NC-SA 4.0)