22.4.2.2. Classifying Non-Tree Edges

Try these first

1. 1.

   Define a tree edge.

   Hint

   Think about the edges used during BFS or DFS.

2. 2.

   What is a cycle in a graph?

   Hint

   Consider the structure of a loop in a path.

3. 3.

   What is a tree edge in graph traversal?

   • An edge that connects any two nodes.
   • An edge used to visit a vertex.
   • An edge not used in traversal.

   Hint

   Think about the edges that allow you to explore new vertices.

4. 4.

   Does a directed graph have cycles if a back edge exists?

   • True
   • False

   Hint

   Recall the definition of a back edge presented in class.

5. 5.

   Given a directed graph defined by edges: (1, 2), (2, 3), (3, 1), (4, 5), and (5, 4), identify the cycles present.

   Hint

   Look for edges that link back to previously visited nodes.

6. 6.

   Using a BFS algorithm, identify if the graph contains cycles and classify the edges in a graph presenting: (A, B), (B, C), (C, A), (D, E).

   Hint

   Trace the graph traversal to see if any nodes revisit earlier nodes.