21.1.7. Applications of DFS Numbers

Try these first

1. 1.

   What is the main strategy of Depth First Search?

   Hint

   Consider how the search prioritizes depth.

2. 2.

   What do pre and post numbers indicate in DFS?

   Hint

   Think about the order of operations.

3. 3.

   What does DFS stand for?

   • Depth First Search
   • Dynamic Factor Supply
   • Direct Face Study

   Hint

   Think about graph traversal techniques.

4. 4.

   True or False: The pre-number of a vertex indicates the time it is fully processed.

   • True
   • False

   Hint

   Consider how we track visitation versus completion.

5. 5.

   Given a graph, use DFS to find and list all the articulation points. Explain your approach.

   Hint

   Check how removal impacts connectivity.

6. 6.

   Devise a way to modify the DFS algorithm to output both pre and post numbers for each vertex without using a natural stack.

   Hint

   Think about how you might keep track of entry and exit timings recursively.