22.4.2.1. Types of Edges in Directed Graphs

Try these first

1. 1.

   What is a directed graph?

   Hint

   Think about how edges connect the vertices.

2. 2.

   Define a backward edge.

   Hint

   It 'backs' up the tree.

3. 3.

   What type of edge connects a vertex to one of its descendants in a DFS tree?

   • Tree Edge
   • Forward Edge
   • Backward Edge

   Hint

   This edge helps in traversing downward.

4. 4.

   If a traversal reveals a backward edge, what does this indicate?

   • True
   • False

   Hint

   Think about the relationship to ancestors.

5. 5.

   Create your own directed graph with at least 6 vertices, and label all edge types found in a DFS traversal. Identify any cycles.

   Hint

   Draw the graph and trace your DFS path!

6. 6.

   Given a directed graph, how can you determine the number of strongly connected components? Write a pseudocode for this process.

   Hint

   Think about how you can utilize DFS both ways to uncover hidden connections.