21.1.1. Depth First Search (DFS)

Try these first

1. 1.

   What does DFS stand for?

   Hint

   Think about how we explore data structures.

2. 2.

   What is the primary data structure used in DFS?

   Hint

   Remember the Last In First Out concept.

3. 3.

   What is the time complexity of DFS using an adjacency list?

   • O(n^2)
   • O(n + m)
   • O(n)

   Hint

   Consider both vertices and edges.

4. 4.

   True or False: Depth First Search guarantees the shortest path in a graph.

   • True
   • False

   Hint

   Review the primary goals of each algorithm.

5. 5.

   Implement a DFS algorithm to detect cycles in a directed graph.

   Hint

   Consider how backtracking helps identify cycles.

6. 6.

   Given a large graph, analyze how changing from adjacency list to adjacency matrix affects DFS performance.

   Hint

   Reflect on efficiency and data representation.