21.1.5. DFS Numbering Technique

Try these first

1. 1.

   What does DFS stand for?

   Hint

   Think about different types of search strategies in graph theory.

2. 2.

   What is a pre-number in the context of DFS?

   Hint

   Recall the sequence of actions taken when visiting a vertex.

3. 3.

   What does DFS stand for?

   • Depth First Search
   • Depth First State
   • Depth Search First

   Hint

   Remember the traversal style it represents.

4. 4.

   True or False: Pre numbers assigned in DFS indicate the exit time of a vertex.

   • True
   • False

   Hint

   Consider the definitions of pre versus post numbers.

5. 5.

   Given a directed graph, perform a DFS starting from vertex A and describe the changes in pre and post numbering.

   Hint

   Make sure to carefully track when you enter and exit each vertex.

6. 6.

   Analyze a graph with cycles using DFS. How do the pre and post numbers reveal the presence of cycles?

   Hint

   Look carefully at how your exit times relate to your entry times for detecting cycles.