Depth-First Search Quiz

Which data structure is used in Depth-First Search (DFS) algorithm?

• Queue

• Stack

• Priority Queue

• Linked List

What is the time complexity of DFS for a graph represented using an adjacency list?

• O(V)

• O(E + V)

• O(V^2)

• O(E^2)

In DFS, how are adjacent vertices of a node typically explored?

• All at once

• One by one

• In reverse order

• Based on vertex values

Which of the following problems can be solved using DFS?

• Finding shortest path in an unweighted graph

• Detecting cycles in a directed graph

• Finding Minimum Spanning Tree

• Dijkstra's algorithm

DFS can be useful for solving which of the following?

• Solving mazes

• Topological sorting

• Finding strongly connected components

• All of the above

Which of the following is NOT a valid application of DFS?

• Topological sorting

• Finding strongly connected components

• Finding shortest path in an unweighted graph

• Detecting cycles in graphs

In a DFS traversal, which vertex is processed after the start vertex?

• The vertex closest to the start vertex

• The vertex farthest from the start vertex

• The vertex reached by the deepest edge first

• The vertex with the smallest number

What is the space complexity of DFS when applied to a graph?

• O(V)

• O(E)

• O(V + E)

• O(V^2)

Which of the following is NOT a property of DFS?

• DFS can be implemented using recursion

• DFS visits vertices level by level

• DFS can be used to detect cycles in a graph

• DFS can traverse disconnected components if applied iteratively

In DFS, if a vertex is visited, what happens to its adjacent unvisited vertices?

• They are pushed onto the stack immediately

• They are ignored

• They are pushed onto the stack later

• They are never explored